선택 정렬(Selection Sort)이란?
선택 정렬은 정렬되지 않은 영역에서 최소 요소를 반복적으로 찾아 맨 앞으로 이동시키는 방식으로 배열을 정렬하는 알고리즘입니다. 매 반복마다 정렬되지 않은 하위 배열에서 가장 작은 요소를 선택하여 정렬된 하위 배열의 끝으로 옮기는 과정을 거칩니다.
문자열 배열을 정렬할 때는 숫자 비교 대신 strcmp() 함수로 문자열을 사전순으로 비교하고, strcpy() 함수로 문자열을 복사·교환한다는 점이 일반적인 선택 정렬과의 차이점입니다.
C++ 구현 예제
#include <iostream>
#include <string.h>
using namespace std;
#define MAX_LEN 50
void selectionSort(char arr[][50], int n){
int i, j, mIndex;
// 정렬되지 않은 하위 배열의 경계를 하나씩 이동
char minStr[50];
for (i = 0; i < n-1; i++){
// 정렬되지 않은 배열에서 최소 요소 탐색
int mIndex = i;
strcpy(minStr, arr[i]);
for (j = i + 1; j < n; j++){
// 현재 최솟값이 arr[j]보다 큰지 확인
if (strcmp(minStr, arr[j]) > 0){
// arr[j]를 새로운 최솟값으로 설정하고 인덱스 갱신
strcpy(minStr, arr[j]);
mIndex = j;
}
}
// 최솟값을 첫 번째 요소와 교환
if (mIndex != i){
char temp[50];
strcpy(temp, arr[i]); // item[pos]와 item[i] 교환
strcpy(arr[i], arr[mIndex]);
strcpy(arr[mIndex], temp);
}
}
}
int main(){
char arr[][50] = {"Tom", "Boyaka", "Matt", "Luke"};
int n = sizeof(arr)/sizeof(arr[0]);
int i;
cout<<"Given String is:: Tom, Boyaka, Matt, Luke\n";
selectionSort(arr, n);
cout << "\nSelection Sorted is::\n";
for (i = 0; i < n; i++)
cout << i << ": " << arr[i] << endl;
return 0;
}
코드 동작 원리
위 C++ 프로그램은 먼저 배열 전체에서 가장 작은(사전순으로 앞선) 요소를 찾아 첫 번째 요소와 교환합니다. 이어서 두 번째로 작은 요소를 찾아 두 번째 위치의 요소와 교환하는 식으로 진행됩니다. 즉, 매 패스마다 가장 작은 요소가 선택되어 올바른 자리에 배치되며, 이 과정이 배열 전체가 정렬될 때까지 반복됩니다. 최종적으로 주어진 문자열 배열은 다음과 같이 오름차순으로 정렬됩니다.
- 1회전: 전체 배열에서 최소 문자열을 찾아 0번째 위치와 교환합니다.
- 2회전: 나머지 구간에서 최소 문자열을 찾아 1번째 위치와 교환합니다.
- n-1회전 반복: 모든 요소가 제자리에 놓일 때까지 위 과정을 반복합니다.
실행 결과
Given string is:: Tom, Boyaka, Matt, Luke Selection Sorted:: Boyaka Luke Matt Tom
시간 복잡도
선택 정렬의 시간 복잡도는 최선·평균·최악의 모든 경우에서 O(n²)로 동일합니다. 데이터 양이 적거나 교환 횟수를 최소화해야 하는 환경에서 유용하지만, 대용량 데이터를 처리할 때는 퀵 정렬이나 병합 정렬 같은 고성능 알고리즘이 더 적합합니다.