정렬된 배열(Sorted Array)이란 배열의 모든 요소가 숫자 크기 순서나 알파벳 순서와 같은 특정 기준에 따라 오름차순 또는 내림차순으로 배치된 배열을 의미합니다.
숫자 배열을 정렬하는 알고리즘은 매우 다양합니다. 대표적인 예로 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort) 등이 있습니다. 이 글에서는 그중 선택 정렬을 이용해 배열을 정렬하는 방법을 자세히 살펴보겠습니다.
선택 정렬이란?
선택 정렬은 정렬된 배열을 만들어내는 정렬 방식입니다. 동작 원리는 다음과 같습니다.
배열에서 아직 정렬되지 않은 부분 중 가장 작은 요소를 반복적으로 찾아낸 뒤, 그 요소를 정렬되지 않은 부분의 맨 앞에 있는 요소와 서로 교환(swap)합니다. 이 과정을 배열 전체가 정렬될 때까지 반복하면 최종적으로 정렬된 배열을 얻을 수 있습니다.
C++ 구현 예제
다음은 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);
cout<<"Sorted array is:"<<endl;
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
코드 상세 분석
1. selectionSort() 함수
위 프로그램에서 selectionSort() 함수는 선택 정렬 알고리즘을 사용해 배열 a[]를 정렬하는 역할을 합니다. 함수 내부에는 두 개의 for 반복문이 존재합니다.
- 외부 반복문: 각 반복마다 인덱스 i 이후 남은 배열 부분에서 최솟값의 위치를 찾습니다.
- 내부 반복문: 현재 최솟값으로 지정된 위치(min)와 나머지 요소들을 비교하여 더 작은 값이 있으면 min 값을 갱신합니다.
내부 반복문이 끝나면 찾은 최솟값을 현재 위치 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;
}
}2. main() 함수
main() 함수에서는 먼저 정렬할 배열 a[]를 정의하고, sizeof(a)/sizeof(a[0])를 통해 배열의 크기 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);
cout<<"Sorted array is:"<<endl;
for (i = 0; i < n; i++)
cout<< a[i] <<" ";
return 0;
}마무리
선택 정렬은 구현이 간단하고 직관적이라는 장점이 있지만, 시간 복잡도가 O(n²)이므로 데이터 개수가 많은 경우에는 퀵 정렬(O(n log n))이나 병합 정렬 같은 고급 알고리즘보다 성능이 떨어질 수 있습니다. 따라서 학습용이나 소규모 데이터 정렬에 적합한 알고리즘이라고 할 수 있습니다.