선택정렬(Selection Sort)
<예시> 가장 많이 들은 노래 순으로 정렬하기
- 노래 리스트 전체 중에서 가장 감상 수가 높은 노래를 하나 뽑아서 새로운 리스트 첫 줄에 작성한다. 이 때 원래의 리스트에서는 그 곡을 삭제한다.
- 나머지 리스트 전체 중에서 가장 감상 수가 높은 노래를 뽑아서 새로운 리스트 두번 째줄에 작성한다. 이 역시 원래 리스트에서는 삭제한다.
- 이를 계속 반복하면 원래의 리스트가 비워졌을 때에 새로운 리스트에는 감상 수가 높은 순으로 노래가 정렬된다.
이렇게 n개의 노래를 정렬하려면 빅오 표기법으로 O(n^2)만큼의 시간이 걸린다.
첫 번째 실행에서는 n개의 항목을 단순 탐색하므로 O(n)의 시간이 걸린다. 첫 번째 시행 후 원래의 리스트에서 항목이 한 개 지워지므로 다음 탐색은 O(n-1)이 걸린다. 이런 식으로 탐색을 할 때마다 항목이 하나씩 줄어들 것이므로, 한 번 탐색을 할 때의 평균 시간은 O(1/2n)이라고 할 수 있다. 탐색을 n번 수행하므로 전체 걸린 시간은 O(n * 1/2 * n )이 되어야 맞을테지만, 빅오 표기법에서는 1/2과 같은 상수항을 무시한다. 그래서 O(n^2)이 된다.
퀵정렬(Quick Sort)
<예시> 숫자로 이루어진 배열을 순서대로 정렬하기
기본 단계
정렬할 필요가 없는 배열이 있다.
qsort([]) // prints [] qsort([7]) // prints [7]즉 // 비어있거나 원소가 하나인 배열은 정렬할 필요가 없다.또는 정렬이 매우 쉬운 배열이 있다.
qsort([7,1]) // prints [1,7] // 첫 번째 원소가 두 번째 원소보다 크면 교환한다. 아니면 그대로 둔다.
기준 원소 정하기
기준원소(pivot)라는 것을 정한다. 일단 임의로 정한다고 가정하자.
[33, 15, 10] // 기준원소를 33으로 한다.기준원소를 기준으로 이보다 작은 원소들은 왼쪽에, 이보다 큰 원소들은 오른쪽에 배치한다. 이를 분할(partitioning)이라 한다.
[15, 10] [33] [] // 기준원소보다 작은 하위배열, 기준원소, 기준원소보다 큰 하위배열기본단계가 됐으므로 정렬한다.
qsort([15,10]) + [33] + [] // prints [10,15,33]이 방법은 기준원소가 어떠한 것이어도 작동한다.
더 큰 배열에 대해 정렬하기
qsort([3,5,2,1,4]) // 기준원소를 2로 잡는다. [1] [2] [3,5,4] qsort([3,5,4]) // 기준원소를 3으로 잡는다. [3] [5,4] qsort([5,4]) // 기본 단계. prints [4,5] qsort([3,5,4]) // prints [3,4,5] qsort([3,5,2,1,4]) // prints [1,2,3,4,5]