선택 정렬

선택 정렬

보통 배열이 정렬되어 있으면 정렬되지 않은 배열보다 더 쉽게 탐색할 수 있습니다.

정렬을 위한 알고리즘 중 선택정렬을 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬입니다.

선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가합니다.

다음과 같은 정렬되지 않은 숫자들을 오름차순 정렬해보도록 하겠습니다.

6 3 8 5 2 7 4 1

먼저 아래 숫자들 중에서 가장 작은 값을 찾습니다.

6 3 8 5 2 7 4 1

가장 작은 값인 1은 가장 앞에 있어야 하므로 현재 리스트의 첫 번째 값인 6과 교환합니다.

1 3 8 5 2 7 4 6

그리고 정렬되어 있는 1은 제외하고, 두 번째 숫자부터 시작해서 또 가장 작은 값을 찾습니다.

1 3 8 5 2 7 4 6

가장 작은 값인 2는 정렬되지 않는 숫자들 중에서 가장 앞에 있어야 하므로 3과 교환합니다.

1 2 8 5 3 7 4 6

이 과정을 더 이상 교환이 일어나지 않을때까지 반복하면, 아래와 같이 오름차순 정렬이 완료됩니다.

1 2 3 4 5 6 7 8

이러한 정렬 방법을 ‘선택 정렬’ 이라고 합니다. 의사 코드로 아래와 같이 표현할 수 있습니다.

For i from 0 to n–1

    Find smallest item between i'th item and last item

    Swap smallest item with i'th item

여기서도 두 번의 루프를 돌아야 합니다.

바깥 루프에서는 숫자들을 처음부터 순서대로 방문하고, 안쪽 루프에서는 가장 작은 값을 찾아야 합니다.

따라서 소요 시간의 상한은 O(n^2)이 됩니다. 하한도 마찬가지로 Ω(n^2) 입니다. 버블 정렬과 동일합니다.