선택 정렬(Selection Sort)이란?
선택 정렬은 배열에서 가장 작은 숫자를 찾아 첫 번째 위치에 배치하는 방식으로 동작하는 정렬 알고리즘입니다. 가장 작은 수가 배치된 위치의 다음 인덱스부터 다시 탐색을 시작하며, 이 과정을 배열 전체가 정렬될 때까지 반복합니다.
개념을 더 쉽게 이해하기 위해 예를 들어 보겠습니다.
배열 {6, 3, 8, 12, 9}가 있다고 가정해 봅시다. 이 배열에서 가장 작은 요소는 3입니다. 따라서 3을 첫 번째 위치에 놓으면 배열은 {3, 6, 8, 12, 9}가 됩니다. 이제 다시 가장 작은 수를 찾되, 이번에는 이미 제자리에 있는 3은 탐색 대상에서 제외합니다. 그다음으로 작은 요소인 6을 찾아 두 번째 위치에 배치하고, 배열이 완전히 정렬될 때까지 이 과정을 계속 반복합니다.
선택 정렬 알고리즘의 동작 과정
선택 정렬 알고리즘은 다음과 같은 단계를 따릅니다.
배열 {20, 12, 23, 55, 21}을 예로 들어 살펴보겠습니다.
배열의 첫 번째 요소를 최솟값(minimum)으로 설정합니다.
Minimum = 20
최솟값을 다음 요소와 비교하여, 더 작은 값이 있으면 해당 값을 새로운 최솟값으로 지정합니다. 배열의 끝까지 이 과정을 반복합니다.
12와 비교 : 20 > 12, minimum = 12
23과 비교 : 12 < 23, minimum = 12
55와 비교 : 12 < 55, minimum = 12
21과 비교 : 12 < 21, minimum = 12
찾은 최솟값을 배열의 첫 번째 위치(인덱스 0)에 배치합니다.
Array = {12, 20, 23, 55, 21}
다음 반복에서는 정렬되지 않은 첫 번째 요소, 즉 최솟값이 배치된 위치 바로 다음 요소부터 정렬을 시작합니다.
Array = {12, 20, 23, 55, 21}
최솟값이 배치된 위치 다음 요소인 20부터 탐색을 시작합니다.
반복 2 :
Minimum = 20
23과 비교 : 20 < 23, minimum = 20
55와 비교 : 20 < 55, minimum = 20
21과 비교 : 20 < 21, minimum = 20
최솟값이 이미 제자리에 있으므로 변경 없음,
Array = {12, 20, 23, 55, 21}
반복 3 :
Minimum = 23
55와 비교 : 23 < 55, minimum = 23
21과 비교 : 23 > 21, minimum = 21
최솟값이 인덱스 2로 이동됨
Array = {12, 20, 21, 55, 23}
반복 4 :
Minimum = 55
23과 비교 : 23 < 55, minimum = 23
최솟값이 인덱스 3으로 이동됨
Array = {12, 20, 21, 23, 55}
C 언어 선택 정렬 예제 코드
#include <stdio.h>
int main() {
int arr[10]={6,12,0,18,11,99,55,45,34,2};
int n=10;
int i, j, position, swap;
for (i = 0; i < (n - 1); i++) {
position = i;
for (j = i + 1; j < n; j++) {
if (arr[position] > arr[j])
position = j;
}
if (position != i) {
swap = arr[i];
arr[i] = arr[position];
arr[position] = swap;
}
}
for (i = 0; i < n; i++)
printf("%d\t", arr[i]);
return 0;
}실행 결과
0 2 6 11 12 18 34 45 55 99
마무리
선택 정렬은 구현이 간단하지만 시간 복잡도가 O(n²)이므로 데이터 개수가 많은 경우에는 퀵 정렬이나 병합 정렬 같은 효율적인 알고리즘을 사용하는 것이 좋습니다. 다만 정렬 로직의 기본기를 익히기에는 가장 적합한 알고리즘 중 하나입니다.