선택 정렬(Selection Sort)이란?
선택 정렬은 리스트를 두 부분으로 나누어 처리하는 정렬 기법입니다. 한쪽 부분에는 이미 정렬된 요소들이, 다른 쪽 부분에는 아직 정렬되지 않은 요소들이 위치합니다.
먼저 배열에서 최댓값 또는 최솟값을 찾습니다. 예를 들어 최솟값을 찾았다면, 그 값을 리스트의 맨 앞에 있는 데이터와 교환하여 시작 위치에 배치합니다. 이 과정이 반복될수록 정렬해야 할 범위가 점점 줄어들며, 마지막에는 전체 배열이 오름차순으로 정렬됩니다.
동작 과정 요약
- 정렬되지 않은 영역에서 최솟값의 인덱스를 찾습니다.
- 찾은 최솟값을 현재 위치(i번째)의 값과 교환(swap)합니다.
- 정렬된 영역이 하나씩 늘어나고, 정렬할 범위는 하나씩 줄어듭니다.
- 모든 요소가 정렬될 때까지 위 과정을 반복합니다.
선택 정렬의 복잡도
시간 복잡도: O(n2) — 모든 경우(최선·평균·최악)에서 동일합니다.
공간 복잡도: O(1) — 제자리(in-place) 정렬로 추가 메모리가 거의 필요하지 않습니다.
입력 − 정렬되지 않은 리스트: 5 9 7 23 78 20 출력 − 정렬 후 배열: 5 7 9 20 23 78
알고리즘
selectionSort(array, size)
입력: 데이터 배열과 배열의 전체 요소 개수
출력: 정렬된 배열
Begin for i := 0 to size-2 do //i번째 위치부터 끝까지 최솟값 탐색 iMin := i; for j := i+1 to size-1 do if array[j] < array[iMin] then iMin := j done swap array[i] with array[iMin] done End
C++ 예제 코드
#include<iostream>
using namespace std;
void swapping(int &a, int &b) { //a와 b의 내용을 서로 교환
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void selectionSort(int *array, int size) {
int i, j, imin;
for(i = 0; i<size-1; i++) {
imin = i; //최솟값의 인덱스를 구함
for(j = i+1; j<size; j++)
if(array[j] < array[imin])
imin = j;
//올바른 위치로 교환하여 배치
swap(array[i], array[imin]);
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //입력받은 개수만큼 배열 생성
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
selectionSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}실행 결과
Enter the number of elements: 6 Enter elements: 5 9 7 23 78 20 Array before Sorting: 5 9 7 23 78 20 Array after Sorting: 5 7 9 20 23 78
마무리
선택 정렬은 구현이 매우 간단하고 직관적이라 학습용으로 적합하지만, 시간 복잡도가 O(n²)이므로 대량의 데이터를 정렬할 때는 퀵 정렬(Quick Sort)이나 병합 정렬(Merge Sort) 같은 O(n log n) 알고리즘을 사용하는 것이 좋습니다. 반면 스왑 횟수가 최대 n-1회로 적기 때문에, 데이터 교환 비용이 큰 환경에서는 유용하게 활용될 수 있습니다.