들어가기 전에
앞서 배운 버블 정렬은 직관적이지만 O(n^2)의 시간이 소요됩니다. 이 방법이 최선일까요? 이번에는 다른 정렬 알고리즘인 선택 정렬을 배워보겠습니다.
학습 목표
선택 정렬의 원리와 실행 시간을 설명하고 구현할 수 있습니다.
핵심 단어
- 선택 정렬
선택 정렬
보통 배열이 정렬되어 있으면 정렬되지 않은 배열보다 더 쉽게 탐색할 수 있습니다.
정렬을 위한 알고리즘 중 선택정렬을 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬입니다.
선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가합니다.
다음과 같은 정렬되지 않은 숫자들을 오름차순 정렬해보도록 하겠습니다.
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) 입니다. 버블 정렬과 동일합니다.
생각해보기
선택정렬을 좀 더 효율적으로 어떻게 바꿀 수 있을까요?
나의 생각 : ...음 최소값과 최대값을 우선적으로 찾는다?
출처 : https://www.boostcourse.org/cs112/lecture/119023?isDesc=false 네이버커넥트재단