[CS50] 4.5 선택 정렬
선택정렬은
배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아
첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환하는 방식의 정렬이다.
교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.
선택정렬의 예시
정렬되지 않은 숫자들을 오름차순 정렬한다고 하자.
프로그램은 배열 속 다른 값을 전부 보기 전 까지는 알 수 없기 때문에,
①첫 번째 값을 제일 작은 숫자로 기억하고 다음 값을 탐색한다.
②탐색하다가 현재 기억하는 숫자보다 작은 값이 발견되면 발견된 값으로 다시 기억한다.
③배열을 다 탐색하고 나면 기억한 숫자를 맨 앞으로 정렬한다.
④정렬한 숫자를 제외하고 두 번째 숫자부터 시작해서 똑같이 탐색한다.
⑤또 가장 작은 값을 찾았으면 정렬된 숫자를 제외하고 맨 앞에 정렬한다.
이를 교환이 일어나지 않을 때까지 반복한다.
선택정렬의 의사코드는 다음과 같다.
For i from 0 to n–1
Find smallest item between i'th item and last item
Swap smallest item with i'th item
버블정렬과 마찬가지로 두 번의 루프를 돌아야 한다.
바깥 루프에서는 숫자들을 처음부터 순서대로 방문하고, 안쪽 루프에서는 가장 작은 값을 찾는다.
가장 작은 수를 찾기 위해 걸리는 시간을 계산해보면 모든 항목을 봐야 하기 때문에 n번의 과정이 필요하다.
계속 정렬을 해나가면 n, n-1, n-2, n-3...번씩 반복하게 되고 마지막엔 하나만 남게 된다.
그렇다면 총 몇 번의 과정일까?
n + (n-1) + (n-2) + ... + 1 = n(n + 1)/2 = n^2 + n/2 = n^2/2 + n/2
n^2은 Big O 표기법에서 n이 커질수록 가장 빠르게 증가하는 항이다.
따라서 실행 시간의 상한은 O(n^2), 하한도 마찬가지로 Ω(n^2)이다.