이번 글에서는 선택 정렬(Selection Sort)을 개선한 양방향 선택 정렬(Two-Way Selection Sort) 알고리즘을 살펴보겠습니다. 기존의 선택 정렬은 배열에서 최솟값 또는 최댓값 하나를 찾아 올바른 위치에 배치하는 방식으로 동작합니다. 반면 이 개선된 방식은 한 번의 순회로 최댓값과 최솟값을 동시에 찾아내고, 배열의 양쪽 끝에서부터 동시에 정렬을 진행합니다. 알고리즘을 단계별로 확인하며 더 자세히 이해해 보겠습니다.
알고리즘
twoWaySelectionSort(arr, n)
시작
i := 0, j := n-1에서 시작하여, i >= j가 될 때까지 i는 1씩 증가, j는 1씩 감소하며 반복
min := 인덱스 i부터 j까지 범위의 최솟값
max := 인덱스 i부터 j까지 범위의 최댓값
i_min := 최솟값의 인덱스
i_max := 최댓값의 인덱스
arr[i]와 arr[i_min]을 교환
만약 arr[i_min]이 max와 같다면
arr[j]와 arr[i_min]을 교환
아니라면
arr[j]와 arr[i_max]를 교환
조건문 종료
반복 종료
종료
핵심 포인트: 최댓값 위치 예외 처리
이 알고리즘에서 주의해야 할 부분은 if (arr[i_min] == max) 조건문입니다. 최솟값을 인덱스 i 위치로 옮기는 과정에서, 최댓값이 원래 인덱스 i에 있었다면 최댓값은 i_min 위치로 이동하게 됩니다. 따라서 최댓값을 뒤쪽 끝(j 위치)으로 보낼 때, 기존의 최댓값 인덱스(i_max)가 아니라 이동된 위치(i_min)를 기준으로 교환해야 합니다. 이 예외 처리를 통해 최댓값이 잘못된 위치로 이동하는 것을 방지할 수 있습니다.
예제 코드 (C++)
#include<iostream>
using namespace std;
void twoWaySelectionSort(int arr[], int n) {
//i는 왼쪽에서, j는 오른쪽에서 이동합니다
for (int i = 0, j = n - 1; i < j; i++, j--) {
int min = arr[i], max = arr[i];
int i_min = i, i_max = i; //i_min과 i_max는 각각 최솟값과 최댓값의 인덱스를 저장합니다
for (int k = i; k <= j; k++) {
if (arr[k] > max) {
max = arr[k];
i_max = k;
} else if (arr[k] < min) {
min = arr[k];
i_min = k;
}
}
swap(arr[i], arr[i_min]); //최솟값을 인덱스 i 위치에 배치
if (arr[i_min] == max)
swap(arr[j], arr[i_min]);
else
swap(arr[j], arr[i_max]);
}
}
main() {
int arr[] = { 25, 45, 14, 10, 23, 29, 65, 21, 78, 96, 30 };
int n = sizeof(arr) / sizeof(arr[0]);
twoWaySelectionSort(arr, n);
cout << "정렬된 배열: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
출력 결과
정렬된 배열: 10 14 21 23 25 29 30 45 65 78 96
정리
양방향 선택 정렬은 한 번의 순회에서 최솟값과 최댓값을 동시에 찾아 배열의 앞쪽과 뒤쪽에 각각 배치함으로써, 정렬에 필요한 순회 횟수를 절반(약 n/2회)으로 줄입니다. 다만 각 순회 내부의 비교 연산은 그대로이므로 전체 시간 복잡도는 여전히 O(n²)입니다. 그럼에도 불구하고 실제 반복 횟수가 줄어들어 기존 선택 정렬보다 약간 더 나은 성능을 기대할 수 있으며, 양방향 정렬이라는 아이디어를 이해하기에 좋은 예제입니다.