이 글에서는 C++에서 정렬 알고리즘을 구현하는 방법을 살펴봅니다. 정렬된 배열(sorted array)이란 각 요소가 숫자 크기순이나 알파벳순 등 특정 기준에 따라 일정한 순서로 배치된 배열을 의미합니다.
숫자 배열을 정렬하는 데 사용할 수 있는 알고리즘은 매우 다양합니다. 대표적인 알고리즘으로는 버블 정렬(bubble sort), 삽입 정렬(insertion sort), 선택 정렬(selection sort), 병합 정렬(merge sort), 퀵 정렬(quick sort), 힙 정렬(heap sort) 등이 있으며, 각각의 성능과 구현 난이도가 다릅니다. 이 글에서는 그중에서도 선택 정렬을 사용하여 배열을 정렬하는 방법을 자세히 설명합니다.
선택 정렬(Selection Sort)이란?
선택 정렬은 정렬된 배열을 만들어내는 비교 기반 정렬 방식입니다. 동작 원리는 단순합니다. 정렬되지 않은 부분에서 가장 작은 요소를 반복적으로 찾아, 해당 요소를 정렬되지 않은 부분의 맨 앞에 있는 요소와 서로 교환(swap)하는 것입니다. 이 과정을 배열 전체가 정렬될 때까지 반복하면 최종적으로 오름차순으로 정렬된 배열을 얻을 수 있습니다.
선택 정렬 구현 예제
다음은 C++로 선택 정렬을 구현하여 배열을 오름차순으로 정렬하는 전체 프로그램입니다.
#include<iostream>
using namespace std;
void selectionSort(int a[], int n) {
int i, j, min, temp;
for (i = 0; i < n - 1; i++) {
min = i;
for (j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j;
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
int main() {
int a[] = { 22, 91, 35, 78, 10, 8, 75, 99, 1, 67 };
int n = sizeof(a)/ sizeof(a[0]);
int i;
cout<<"Given array is:"<<endl;
for (i = 0; i < n; i++)
cout<< a[i] <<" ";
cout<<endl;
selectionSort(a, n);
printf("\nSorted array is: \n");
for (i = 0; i < n; i++)
cout<< a[i] <<" ";
return 0;
}실행 결과
Given array is: 22 91 35 78 10 8 75 99 1 67 Sorted array is: 1 8 10 22 35 67 75 78 91 99
코드 상세 분석
selectionSort() 함수
위 프로그램에서 selectionSort()는 선택 정렬 알고리즘을 사용해 배열 a[]를 정렬하는 함수입니다. 이 함수 내부에는 두 개의 for 루프가 존재합니다.
- 외부 루프: 현재 정렬할 위치인 인덱스
i를 결정합니다. 루프는n-1번 반복됩니다. - 내부 루프: 인덱스
i+1부터 배열 끝까지 탐색하며 나머지 부분에서 최솟값의 위치min을 찾습니다.
외부 루프의 각 반복에서 i 이후 남은 배열 중 최소 요소를 찾아, 현재 i 위치에 있는 요소와 교환합니다. 이 과정이 배열 전체가 정렬될 때까지 반복됩니다. 해당 코드는 아래와 같습니다.
void selectionSort(int a[], int n) {
int i, j, min, temp;
for (i = 0; i < n - 1; i++) {
min = i;
for (j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j;
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}main() 함수
main() 함수에서는 먼저 정렬할 배열 a[]를 정의하고, sizeof(a) / sizeof(a[0]) 연산을 통해 배열의 크기 n을 계산합니다. 이후 배열 a[]와 크기 n을 인자로 전달하여 selectionSort() 함수를 호출하고, 마지막으로 정렬이 완료된 배열을 화면에 출력합니다.
int main() {
int a[] = { 22, 91, 35, 78, 10, 8, 75, 99, 1, 67 };
int n = sizeof(a)/ sizeof(a[0]);
int i;
cout<<"Given array is:"<<endl;
for (i = 0; i < n; i++)
cout<< a[i] <<" ";
cout<<endl;
selectionSort(a, n);
printf("\nSorted array is: \n");
for (i = 0; i < n; i++)
cout<< a[i] <<" ";
return 0;
}선택 정렬의 시간 복잡도
선택 정렬은 데이터 초기 상태와 관계없이 항상 전체를 탐색하므로, 최선·평균·최악의 경우 모두 시간 복잡도가 O(n²)입니다. 추가 메모리 사용 없이 제자리(in-place)에서 정렬이 이루어지므로 공간 복잡도는 O(1)입니다. 따라서 구현이 간단하지만 데이터 양이 많은 경우에는 퀵 정렬이나 병합 정렬 같은 O(n log n) 알고리즘이 더 적합합니다.