[CS50] 알고리즘 - 선택 정렬

정렬된 배열이 정렬되지 않은 배열보다 탐색하기 쉽다.

 

선택 정렬(Selection Sort)은 배열에서 가장 작은 값을 찾아 첫 번째 위치의 값과 교환하는 방식의 정렬이다.

교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.

동작 원리

정렬되지 않은 숫자들을 오름차순으로 정렬해보자.

6 3 8 5 2 7 4 1

1단계:

• 가장 작은 값인 1을 찾는다
• 첫 번째 값인 6과 교환한다
• 결과: 1 3 8 5 2 7 4 6

2단계:

• 정렬된 1을 제외하고 두 번째부터 가장 작은 값을 찾는다
• 가장 작은 값인 2를 두 번째 값인 3과 교환한다
• 결과: 1 2 8 5 3 7 4 6

3단계 이후:

• 이 과정을 더 이상 교환이 일어나지 않을 때까지 반복한다
• 최종 결과: 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²)
• 하한 (최선의 경우): Ω(n²)

 

연습 문제

Q. 선택 정렬을 좀 더 효율적으로 어떻게 바꿀 수 있을까?

양방향 선택 정렬:

각 반복 실행에서 최솟값과 최댓값을 동시에 찾아 배열의 양 끝으로 이동시킨다.

개선된 알고리즘:

For i from 0 to n/2
        Find smallest item between i'th item and (n-i)'th item
        Find largest item between i'th item and (n-i)'th item
        Swap smallest item with i'th item
        Swap largest item with (n-i)'th item

장점:

• 한 번의 순회에서 양쪽 끝을 동시에 정렬
• 외부 루프 반복 횟수가 절반으로 감소
• 여전히 O(n²)이지만 실제 비교 횟수는 약 절반

단점:

• 코드 복잡도 증가
• 시간 복잡도는 여전히 O(n²)