[CS50] 알고리즘: 선택 정렬
❄️ David Malan 교수의 모두를 위한 컴퓨터 과학(CS50 2019)을 바탕으로 정리한 내용입니다.
선택 정렬
보통 배열이 정렬되어 있으면 정렬되지 않은 배열보다 더 쉽게 탐색할 수 있습니다.
정렬을 위한 알고리즘 중 선택정렬을 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬입니다.
선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가합니다.
예시 1
다음과 같은 정렬되지 않은 숫자들을 오름차순 정렬해보도록 하겠습니다.
먼저 아래 숫자들 중에서 가장 작은 값을 찾습니다.
가장 작은 값인 1은 가장 앞에 있어야 하므로 현재 리스트의 첫 번째 값인 6과 교환합니다.
그리고 정렬되어 있는 1은 제외하고, 두 번째 숫자부터 시작해서 또 가장 작은 값을 찾습니다.
가장 작은 값인 2는 정렬되지 않는 숫자들 중에서 가장 앞에 있어야 하므로 3과 교환합니다.
이 과정을 더 이상 교환이 일어나지 않을때까지 반복하면, 아래와 같이 오름차순 정렬이 완료됩니다.
예시 2
이러한 정렬 방법을 ‘선택 정렬’ 이라고 합니다. 의사 코드로 아래와 같이 표현할 수 있습니다.
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) 입니다. 버블 정렬과 동일합니다.
생각해보기
선택정렬을 좀 더 효율적으로 어떻게 바꿀 수 있을까요?
- 최댓값과 최솟값을 동시에 처리함으로써 개선할 수 있지만 시간복잡도는 여전히 O(n^2)입니다.
1. 가장 큰 값과 가장 작은 값을 찾는다.
6 3 8 5 2 7 4 1
2. 배열의 양 끝에 둔다. (최소값은 왼쪽, 최대값은 오른쪽끝으로)
1 6 3 5 2 7 4 8
3. 최소값과 최대값 사이에 있는 남은 숫자들에서 또 최소값과 최대값을 찾는다. 2번 처럼 정리한다. => 반복
1 ( 6 3 5 2 7 4 ) 8 => 1 2 6 3 5 4 7 8 => 반복
💛 개인 공부 기록용 블로그입니다. 👻