선택 정렬(Selection Sort)이란?
선택 정렬은 배열 전체를 훑으면서 가장 작은 숫자를 찾아 첫 번째 위치에 배치하는 정렬 알고리즘입니다. 가장 작은 값이 배치된 위치의 다음 인덱스부터 새로운 탐색 범위가 시작되며, 이 과정을 반복하여 전체 배열을 오름차순으로 정렬합니다.
선택 정렬의 기본 절차
목록에 있는 요소들 중 가장 작은 요소를 찾아 첫 번째 위치에 배치합니다.
나머지 요소들에 대해서도 동일한 과정을 반복하며, 모든 요소가 정렬될 때까지 진행합니다.
다음과 같은 배열이 있다고 가정해 보겠습니다.
30 50 40 10 20
첫 번째 패스(First Pass)
Sm = a[0] = 30
a[1] < sm → 50 < 30 (거짓) → sm = 30 유지
a[2] < sm → 40 < 30 (거짓) → sm = 30 유지
a[3] < sm → 10 < 30 (참) → sm = 10으로 갱신
a[4] < sm → 20 < 10 (거짓) → sm = 10 유지
탐색이 끝나면 최솟값(sm)인 10과 a[0]의 값을 교환합니다.
10 50 40 30 20
두 번째 패스(Second Pass)
Sm = a[1] = 50
a[2] < sm → 40 < 50 (참) → sm = 40으로 갱신
a[3] < sm → 30 < 40 (참) → sm = 30으로 갱신
a[4] < sm → 20 < 30 (참) → sm = 20으로 갱신
최솟값 20과 a[1]의 값을 교환합니다.
10 20 40 30 50
세 번째 패스(Third Pass)
Sm = a[2] = 40
a[3] < sm → 30 < 40 (참) → sm = 30으로 갱신
a[4] < sm → 50 < 30 (거짓) → sm = 30 유지
최솟값 30과 a[2]의 값을 교환합니다.
10 20 30 40 50
네 번째 패스(Fourth Pass)
Sm = a[3] = 40
a[4] < sm → 50 < 40 (거짓) → sm = 40 유지
교환이 발생하지 않으며, 이 시점에서 배열은 완전히 정렬된 상태가 됩니다.
10 20 30 40 50
선택 정렬 알고리즘(의사코드)
선택 정렬의 핵심 로직은 아래와 같습니다. 바깥 루프는 정렬되지 않은 영역의 시작점을, 안쪽 루프는 그 영역에서의 최솟값 탐색을 담당합니다.
for (i=0; i<n-1; i++){
sm = i;
for (j=i+1; j<n; j++){
if (a[j] < a[sm])
sm = j;
}
t = a[i];
a[i] = a[sm];
a[sm] = t;
}C 언어로 구현한 선택 정렬 예제
다음은 선택 정렬 기법을 구현한 완전한 C 프로그램입니다.
#include<stdio.h>
int main(){
int a[50], i, j, n, t, sm;
printf("enter the No: of elements in the list:\n"); // 요소 개수 입력 안내
scanf("%d", &n);
printf("enter the elements:\n"); // 요소 입력 안내
for(i=0; i<n; i++){
scanf("%d", &a[i]);
}
/* 선택 정렬 수행 */
for (i=0; i<n-1; i++){
sm = i; // 현재 위치를 최솟값 인덱스로 초기화
for (j=i+1; j<n; j++){ // 나머지 요소 탐색
if (a[j] < a[sm]){
sm = j; // 더 작은 값 발견 시 인덱스 갱신
}
}
t = a[i]; // 최솟값과 현재 위치의 값 교환
a[i] = a[sm];
a[sm] = t;
}
printf("after selection sorting the elements are:\n");
for (i=0; i<n; i++)
printf("%d\t", a[i]);
return 0;
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
enter the No: of elements in the list: 4 enter the elements: 45 12 37 68 after selection sorting the elements are: 12 37 45 68
마무리: 선택 정렬의 특징
선택 정렬은 구현이 간단하고 직관적이라는 장점이 있지만, 데이터 크기와 관계없이 항상 O(n²)의 시간 복잡도를 가지므로 데이터 양이 많을 때는 비효율적일 수 있습니다. 반면 제자리(in-place) 정렬 방식으로 추가 메모리가 거의 필요 없고, 각 패스마다 교환 횟수가 최대 한 번뿐이라는 점이 특징입니다. 학습용으로는 물론, 소규모 데이터를 다룰 때 유용하게 활용할 수 있습니다.