보통 배열이 정렬되어 있으면 정렬되지 않은 배열보다 더 쉽게 탐색할 수 있다.
정렬을 위한 알고리즘 중 선택 정렬은 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를
찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다.
선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.
다음과 같은 정렬되지 않은 숫자들을 오름차순 정렬해보자.
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) 이다. 버블 정렬과 동일하다.
Ref.
- Edwith_boost course
- https://www.zerocho.com/category/Algorithm/post/57f728c85141fc5fe4f4ca89
Front-end developer