선택 정렬(Selection Sort) 알고리즘
선택 정렬(Selection Sort) 알고리즘은 데이터 중 하나를 기준으로 나머지 데이터와 비교하여 가장 작거나 큰 데이터와 위치를 바꾸는 과정을 반복하여 정렬하는 방식입니다. 데이터의 개수가 n개일 경우, 전체 반복 횟수는 n - 1번입니다. 오름차순 기준으로 배열을 정렬할 때, 선택 정렬은 배열의 처음부터 가장 작은 데이터를 차례대로 채워 나갑니다.
반면, 거품 정렬(Bubble Sort) 알고리즘은 오름차순으로 정렬할 때, 연속된 두 데이터를 비교하여 큰 값을 뒤로 이동시키며 가장 큰 값을 오른쪽으로 밀어 정렬하는 방식을 사용합니다.
선택 정렬 회전수
배열 data[5]에 다음과 같이 데이터가 입력되어 있다고 할 때 선택 정렬을 사용해서 오름차 순으로 정렬시키는 단계를 간단히 표현해 보겠습니다. 지면상 모든 단계를 표현하는 게 아닌 왼쪽에 가장 작은 값이 들어올 때까지만 표현합니다.
data[5]
| data[0] | data[1] | data[2] | data[3] | data[4] |
|---|---|---|---|---|
| 46 | 32 | 11 | 24 | 55 |
1회전:
data[0]을 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복하면 data[0]에는 가장 작은 값이 들어갑니다.
| data[0] | data[1] | data[2] | data[3] | data[4] |
|---|---|---|---|---|
| 46 | 32 | 11 | 24 | 55 |
| 32 | 46 | 11 | 24 | 55 |
| 11 | 46 | 32 | 24 | 55 |
2회전:
data[1]을 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복합니다. 2회전이 끝나면 data[1]에 두 번째로 작은 값이 들어갑니다.
| data[0] | data[1] | data[2] | data[3] | data[4] |
|---|---|---|---|---|
| 11 | 46 | 32 | 24 | 55 |
| 11 | 32 | 46 | 24 | 55 |
| 11 | 24 | 46 | 32 | 55 |
3회전:
data[2]을 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복합니다. 3회전이 끝나면 data[2]에 세 번째로 작은 값이 들어갑니다.
| data[0] | data[1] | data[2] | data[3] | data[4] |
|---|---|---|---|---|
| 11 | 24 | 46 | 32 | 55 |
| 11 | 24 | 32 | 46 | 55 |
4회전:
data[3]을 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복합니다. 4회전이 끝나면 data[3]에 네 번째로 작은 값이 들어갑니다.
| data[0] | data[1] | data[2] | data[3] | data[4] |
|---|---|---|---|---|
| 11 | 24 | 32 | 46 | 55 |
| 11 | 24 | 32 | 46 | 55 |
참고: 선택 정렬 관련 정보처리기사 필기 문제
코드를 작성하기 전에 선택 정렬 알고리즘의 흐름을 조금 더 정리하는 차원에서, 정보처리기사 필기 시험에 여러 해에 걸쳐서 출제된 선택 정렬 관련 문제를 참고용으로 풀어보겠습니다.
문제: 자료가 다음과 같이 주어졌을 때 선택 정렬(selection sort)을 적용하여 오름차순으로 정렬할 경우 pass 2를 진행한 후의 정렬된 값으로 옳은 것은?
자료: 9, 4, 5, 11, 8
가. 4, 5, 9, 8, 11 나. 4, 5, 9, 11, 8
다. 4, 5, 8, 11, 9 라. 4, 5, 8, 9, 11
정답: 나
해설: 가장 작은 데이터를 왼쪽으로 하나씩 채우는 형태로 각 회전이 끝난 후의 배열 모양은 다음과 같습니다.
1. pass 1: 4, 9, 5, 11, 8
2. pass 2: 4, 5, 9, 11, 8
3. pass 3: 4, 5, 8, 11, 9
4. pass 4: 4, 5, 8, 9, 11
선택 정렬 알고리즘 순서도
다음은 선택 정렬로 오름차순으로 정렬할 때의 순서도입니다.
오름차순 정렬
다음은 선택 정렬로 내림차순으로 정렬할 때의 순서도입니다.
내림차순 정렬
[실습] 정렬(Sort) 알고리즘 사용하기
주어진 데이터를 오름차순 또는 내림차순으로 정렬하는 정렬 알고리즘 중 가장 학습하기 편한 선택 정렬 알고리즘을 적용해 보겠습니다. 다음 내용을 입력한 후 실행해 보세요. 정렬 알고리즘은 오름차순 기준으로 가장 작은 데이터를 왼쪽으로 순서대로 이동합니다.
예제: 데이터를 순서대로 정렬
다음 예제를 작성 후 실행해 보세요.
selection_sort.c
//[?] 무작위 데이터를 순서대로 [오름차순|내림차순] 정렬
#include <stdio.h>
#define N 5
// 정렬 알고리즘(Sort Algorithm): 가장 [작은|큰] 데이터를 왼쪽으로 순서대로 이동
int main(void)
{
//[1] Input: Data Structure(Array, List, Stack, Queue, Tree, DB, ...)
int data[] = { 3, 2, 1, 5, 4 };
int i, j, temp;
//[2] Process: Selection Sort(선택 정렬) 알고리즘
for (i = 0; i < N - 1; i++) // i = 0 to N - 1
{
for (j = i + 1; j < N; j++) // j = i + 1 to N
{
if (data[i] > data[j]) // 부등호 방향: 오름차순(>), 내림차순(<)
{
// 3단계 코드에 의해서 데이터 교환
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}
//[3] Output
for (int i = 0; i < N; i++)
{
printf("%d\t", data[i]);
}
printf("\n");
return 0;
}
1 2 3 4 5
코드: 알고리즘_정렬.c
/*
정렬(Sort) 알고리즘 : 데이터를 순서대로 정렬
*/
#include <stdio.h>
int main(void)
{
//[1] Input
int intNum[5] = { 2, 3, 1, 5, 4 };
int i, j, temp;
//[2] Process : Selection Sort(선택 정렬)
for (i = 0; i < 5 - 1; i++)
{
for (j = i + 1; j < 5; j++)
{
if (intNum[i] > intNum[j])
{
temp = intNum[i];
intNum[i] = intNum[j];
intNum[j] = temp;
}
}
}
//[3] Output
for (i = 0; i < 5; i++)
{
printf("%d\n", intNum[i]);
}
return 0;
}
함수로 구현한 C 언어 선택 정렬 알고리즘 예제
예제: 선택 정렬 알고리즘
코드: selection_sort.c
#include <stdio.h>
void selection_sort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
int main() {
int arr[] = {34, 12, 45, 8, 21, 17};
int size = sizeof(arr) / sizeof(arr[0]);
selection_sort(arr, size);
printf("선택 정렬 후 배열: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
예제: 함수와 포인터를 사용한 선택 정렬 구현
코드: selection_sort.c
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_index = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
swap(&arr[min_index], &arr[i]);
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Unsorted array: ");
printArray(arr, n);
selectionSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
정렬 알고리즘은 현업에서도 굉장히 많이 사용하는 알고리즘입니다. 많은 정렬 알고리즘 중에서도 선택 정렬 알고리즘은 익혀 두어야 하는 필수 알고리즘 중의 하나이므로 꼭 기억하길 권장합니다. 물론 현업에서 일할 때는 선택 정렬 알고리즘보다 훨씬 빠르게 사용할 수 있는 C 언어를 예를 들어 qsort() 함수, C#을 예를 들어 Sort() 메서드와 OrderBy() 등의 메서드가 이미 준비되어 있으니 그걸 사용해도 좋습니다.