L03 - Basic Sorting Algorithms

 

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한
 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다

 

 

Sorting?

 

정렬(Sorting) : 배열 원소들을 번호 순, 알파벳 순 등 정해진 순서대로 재배치하는 문제

 

3 / 1 / 2 / 5 / 4   ->  1 / 2 / 3 / 4 / 5

 

 

Sorting Algorithms에는 크게

 

• 기본적인 정렬 알고리즘
  • 평균 시간복잡도가 Θ(n^2)인 알고리즘들
  • Selection Sort, Insertion Sort, Bubble Sort
• 고급 정렬 알고리즘
  • 평균 시간복잡도가 Θ(nlogn)인 알고리즘들
  • Merge Sort, Quicksort, Heapsort
• 특수 정렬 알고리즘
  • 특수한 경우 시간복잡도가 Θ(n)인 알고리즘들
  • Radix Sort, Counting Sort

 

로 나눌 수 있음

 

이번 포스팅에서는 기본적인 정렬 알고리즘 3가지를 다룰 예정!

 

=> 각 sort의 복잡도를 살펴볼건데 보통 정렬 알고리즘의 경우 swap 연산과 comparisons 2가지를 따짐

 

Bubble Sort

 

원리는 정렬되지 않은 값 중 최대값을 맨 뒤로 보내는 것을 반복하여 정렬하는 것이다!

 

최댓값 맨 뒤로 보내기

 

=> 최댓값을 맨 뒤로 보내기 위해, 인접한 두 값을 반복하여 비교 및 교환

 

bubble sort pseudocode

 

bubble sort 복잡도

 

 

Best Case 일 때 모든 배열 원소들은 정해진 순서대로 배치되어 있을 것이기 때문에 swap 연산이 일어나지 않는다

=> 0

(인접한 두 값을 if문으로 계속 확인해야 하기 때문에 비교 연산은 Θ(n^2) 으로 볼 수 있음)

 

Worst Case 일 때 모든 배열 원소가 정해진 순서의 반대로 배치되어 있을 것이기 때문에 모든 반복 과정에서 swap 연산이 일어남

=> Θ(n^2)

 

(인접한 두 값을 if문으로 계속 확인해야 하기 때문에 비교 연산은 Θ(n^2) 으로 볼 수 있음)

 

Average Case는 모든 배열 원소가 무작위로 정렬되어 있을 때인데 평균적으로 swap은 절반 정도 발생한다고 생각하면 됨

=> Θ(n^2) 

 

(인접한 두 값을 if문으로 계속 확인해야 하기 때문에 비교 연산은 Θ(n^2) 으로 볼 수 있음)

 

Worst Case에 비해 실제 swap 연산은 Average Case에서 절반 정도 줄 텐데 상수항을 제거하면 결국 Θ(n^2)로 동일함

 

Selection Sort

 

원리는 정렬되지 않은 값들 중에서 최솟값을 찾아 앞에 놓는 걸 반복하는 것이다!

selection sort 원리

 

selection sort pseudocode

 

selection sort 복잡도

 

 

Best Case 일 때 모든 배열 원소들은 정해진 순서대로 배치되어 있을 것이기 때문에 swap 연산이 일어나지 않는다

=> 즉, 찾은 최솟값이 현재 선택된 값과 동일하므로 swap이 발생하지 않기에 0

 

(최솟값이 무엇인지 확인하러 현재 선택된 값을 나머지 부분과 비교해야하기 때문에 비교 연산은 Θ(n^2) 으로 볼 수 있음)

 

Worst Case 일 때 모든 배열 원소가 정해진 순서의 반대로 배치되어 있을 것이기 때문에 모든 반복 과정에서 swap 연산이 일어남

=> 로직상 swap 연산은 최솟값을 탐색하고 나서 한 번 발생하므로 n-1번 즉, Θ(n)

 

(최솟값이 무엇인지 확인하러 현재 선택된 값을 나머지 부분과 비교해야하기 때문에 비교 연산은 Θ(n^2) 으로 볼 수 있음)

 

Average Case는 모든 배열 원소가 무작위로 정렬되어 있을 때인데 보통 swap은 절반 정도 발생한다고 생각하면 됨

 

(최솟값이 무엇인지 확인하러 현재 선택된 값을 나머지 부분과 비교해야하기 때문에 비교 연산은 Θ(n^2) 으로 볼 수 있음)

 

Worst Case에 비해 실제 swap 연산은 Average Case에서 절반 정도 줄 텐데 상수항을 제거하면 결국 Θ(n)로 동일함

 

Insertion Sort

 

(기본 정렬 알고리즘에서 bubble, selection 에 비해 제일 많이 사용되는 sort 방식임)

 

원리는 정렬되지 않은 값들 중 하나를 골라서, 이미 정렬된 값들 사이에 끼워넣기를 반복하는 것이다!

 

insertion sort 원리

 

=> 점점 한 칸씩 옆으로 땅따먹기를 하면서 바로 바로 정렬한다고 생각하면 이해가 쉬움 (정렬된 영역을 확장하는 느낌)

 

 

insertion sort pseudocode

insertion sort 복잡도

 

 

 

Best Case 일 때 모든 배열 원소들은 정해진 순서대로 배치되어 있을 것이기 때문에 swap 연산이 일어나지 않는다

=> 0

 

(정해진 순서대로 배치되어 있으므로 영역을 확장할 때만 한 번씩 바로 인접한 값과 크기를 비교하고 break 문에 의해 더 이상 비교 X)

=> Θ(n)

 

Worst Case 일 때 모든 배열 원소가 정해진 순서의 반대로 배치되어 있을 것이기 때문에 모든 반복 과정에서 swap 연산이 일어남

=> Θ(n^2)

 

(반복문을 돌며 인접한 값과 새로 들어온 값의 크기를 비교할 때 break에 걸리지 않기 때문에 모든 반복 과정에서 비교 연산이 일어남)

=> Θ(n^2)

 

Average Case는 모든 배열 원소가 무작위로 정렬되어 있을 때인데 보통 swap은 절반 정도 발생한다고 생각하면 됨

 

(반복문을 돌며 인접한 값과 새로 들어온 값의 크기를 비교하고 break가 걸리지 않으면 현재 영역에서 정렬이 완료될 때 까지 계속 비교를 하므로 Worst Case에 비해 절반 정도 덜 비교연산이 실행되겠지만 결국 상수를 제외하면 비교 연산은 Θ(n^2) 으로 볼 수 있음)

 

Worst Case에 비해 실제 swap 연산은 Average Case에서 절반 정도 줄 텐데 상수항을 제거하면 결국 Θ(n)로 동일함

 

 

💡 Insertion Sort는 배열이 거의 정렬된 상태일 때(Best Case에 가까울수록) 매우 효율적인 것을 알 수 있음 💡