선택 정렬(Selection Sort)은 배열을 처음부터 순회하면서 각 위치에 남아 있는 요소 중 가장 작은 값을 찾아 교체하는 방식으로 데이터를 정렬하는 대표적인 정렬 알고리즘입니다. 정렬이 진행될수록 왼쪽 부분은 정렬된 상태가 되고, 오른쪽 부분은 아직 정렬되지 않은 상태로 남습니다. 매 단계마다 교환(swap)을 통해 그다음으로 작은 요소가 현재 인덱스 위치에 배치됩니다.
선택 정렬 알고리즘
int arr[5] = { 5, 4, 2, 1, 3 };
int i, j;
인덱스 i = 0부터 i < 배열 크기 - 1까지 순회합니다.
인덱스 j = i + 1부터 배열 크기 - 1까지 순회합니다.
가장 작은 요소를 찾아 그 인덱스(pos)를 저장합니다.
찾은 인덱스 pos에 있는 요소를 arr[i]와 교환합니다.
종료합니다.
재귀 선택 정렬
최소 요소의 인덱스를 찾습니다.
찾은 최소 요소의 인덱스가 배열 크기와 같다면 종료(return)합니다.
그렇지 않다면 현재 요소와 최소 요소를 교환합니다.
정렬이 완료된 요소를 제외한 나머지 배열에 대해 위 과정을 재귀적으로 수행합니다.
예제
입력 − Arr[] = { 5, 7, 2, 3, 1, 4 }; length = 6
출력 − 정렬된 배열: 1 2 3 4 5 7
설명 −
첫 번째 패스 :- 5 7 2 3 1 4 → 교환 → 1 2 7 3 5 4 1 2 7 3 5 4 → 교환 없음 1 2 7 3 5 4 → 교환 → 1 2 3 7 5 4 1 2 3 7 5 4 → 교환 → 1 2 3 4 5 7 1 2 3 4 5 7 → 교환 없음
입력 − Arr[] = { 1, 2, 3, 3, 2 };
출력 − 정렬된 배열: 1 2 2 3 3
설명 −
1 2 3 3 2 → 교환 없음 1 2 3 2 3 → 교환 없음 1 2 3 2 3 → 교환 → 1 2 2 3 3 1 2 2 3 3 → 교환 없음
프로그램에서 사용된 접근 방식
재귀적 선택 정렬에서 기저 사례(base case)는 '최소 인덱스 = 배열 크기 - 1'입니다. 이 조건이 아니라면 배열에서 최솟값을 찾아 현재 인덱스의 요소와 교환한 뒤, 오른쪽에 남아 있는 정렬되지 않은 부분 배열을 재귀적으로 정렬합니다.
입력 배열 Arr[]와 요소 개수를 나타내는 length를 전달받습니다.
함수 findMin(int arr[], int i, int j)는 배열과 인덱스를 받아 arr[i+1]부터 arr[j] 범위에서 최소 요소의 인덱스를 반환합니다.
변수 minpos를 선언합니다.
i와 j가 같다면 두 위치가 동일하므로 i를 최소 요소의 인덱스로 그대로 반환합니다.
그렇지 않다면 minpos = findMin(arr, i + 1, j)를 호출하여 i+1부터 j까지의 범위를 재귀적으로 탐색합니다.
if(arr[i] < arr[minpos]) 조건이 참이면 minpos = i로 설정한 뒤 minpos를 반환합니다.
함수 recurselectSort(int arr1[], int len1, int pos1)는 입력 배열을 받아 재귀적 선택 정렬 방식으로 오름차순 정렬을 수행합니다.
pos1 == len1이라면 더 이상 찾을 최솟값이 없으므로 그대로 반환합니다.
그렇지 않다면 minpos1 = findMin(arr1, pos1, len1 - 1)을 호출합니다.
현재 인덱스 pos1과 최소 요소의 인덱스 minpos1이 서로 다르면 temp 변수를 이용해 두 인덱스의 요소를 교환합니다.
recurselectSort(arr1, len1, pos1 + 1)을 호출하여 나머지 배열 부분에 대해 재귀적으로 처리합니다.
모든 재귀 호출이 끝나고 길이가 1이 되면 재귀에서 빠져나오며, 이때 배열은 완전히 정렬된 상태가 됩니다.
main 함수 안에서 정렬된 배열을 출력합니다.
예시 코드
#include <iostream>
using namespace std;
int findMin(int arr[], int i, int j){
int minpos;
if (i == j){
return i;
}
minpos = findMin(arr, i + 1, j);
if(arr[i]<arr[minpos]){
minpos=i;
}
return (minpos);
}
void recurselectSort(int arr1[], int len1, int pos1){
int temp;
int minpos1;
if (pos1 == len1){
return;
}
minpos1 = findMin(arr1, pos1, len1-1);
if (minpos1 != pos1){
temp=arr1[pos1];
arr1[pos1]=arr1[minpos1];
arr1[minpos1]=temp;
}
recurselectSort(arr1, len1, pos1 + 1);
}
int main(){
int Arr[] = {1,5,3,0,9,3,5};
int length = sizeof(Arr)/sizeof(Arr[0]);
recurselectSort(Arr,length,0);
cout<<"Sorted Array using recursive Selection sort: "<<endl;
for (int i = 0; i<length ; i++){
cout << Arr[i] << " ";
}
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Sorted Array using recursive Selection sort: 0 1 3 3 5 5 9