선택 정렬(Selection Sort)은 리스트를 두 부분으로 나누어 정렬하는 기법입니다. 한쪽 부분에는 정렬된 요소들이, 다른 쪽 부분에는 아직 정렬되지 않은 요소들이 위치합니다. 처음에는 배열에서 최댓값 또는 최솟값을 찾습니다. 예를 들어 최솟값을 찾았다면, 그 값을 리스트의 맨 앞에 있는 데이터와 교환하여 리스트의 시작 부분에 배치합니다. 이 과정이 반복될수록 정렬해야 할 배열의 크기는 점점 작아지며, 이러한 방식으로 전체 정렬이 완성됩니다.
선택 정렬의 시간 복잡도
- 시간 복잡도(Time Complexity): O(n²)
- 공간 복잡도(Space Complexity): O(1)
선택 정렬은 모든 경우(최선, 평균, 최악)에서 O(n²)의 시간 복잡도를 가집니다. 배열 내에서 제자리(in-place) 정렬이 이루어지므로 추가 메모리가 거의 필요하지 않다는 장점이 있습니다.
입력 및 출력 예시
입력: 정렬되지 않은 리스트: 5 9 7 23 78 20 출력: 정렬 전 배열: 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
EndC++ 구현 예제
#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