Definition
- '선택정렬 (= Selection Sorting)'이란?
정렬 알고리즘의 하나로, 처리되지 않은 데이터 중에서 '가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복'하는 것
ps. '정렬 (= Sorting)' : 데이터를 특정한 기준에 따라 순서대로 나열하는 것
Process
-
주어진 리스트 중에 최솟값을 찾는다.
-
그 값을 맨 앞에 위치한 값과 교체한다. (이 과정을 '패스 (= Pass)' 라고 한다.)
-
맨 처음 위치를 제외한 나머지 리스트를 같은 방법으로 교체한다.
Implementation
[3, 2, 1, 6, 5] 라는 배열이 있다고 하자.
이 배열을 선택정렬 알고리즘을 이용하여 오름차순 (= Ascending)으로 정렬하려고 한다.
결과는 [1, 2, 3, 5, 6]이 나와야 한다.
#include <stdio.h>
void printArray(int arr[], int cnt);
void findMinValue(int arr[], int cnt);
void selection_sort_ver1(int arr[], int cnt);
void selection_sort_ver2(int arr[], int cnt);
void main()
{
int iArr[5] = {3, 2, 1, 6, 5}; // 배열 선언 및 초기화
int iSize = sizeof(iArr) / sizeof(iArr[0]); // 배열 내 요소의 갯수 (= 배열의 전체 크기 / 0번째 Index의 크기)
// Array 출력
printArray(iArr, iSize);
// Step 1. 최솟값 찾기
findMinValue(iArr, iSize);
// Step 2. 선택정렬 (ver.1)
selection_sort_ver1(iArr, iSize);
// 개선된 선택정렬 (ver.2)
selection_sort_ver2(iArr, iSize);
}Array 출력
void printArray(int arr[], int cnt) {
for (int i = 0; i < cnt; i++) {
printf("%5d", arr[i]);
}
}Step 1. 최솟값 찾기
void findMinValue(int arr[], int cnt) {
for (int i = 1; i < cnt; i++) {
if (arr[0] > arr[i]) {
int temp;
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
}
}
printArray(arr, cnt);
}먼저 최솟값을 찾는 방법을 원시적인 방법으로 구하려고 한다.
0번째 Index의 값을 기준값으로 잡고 1번째 Index부터 배열의 마지막 Index까지 '비교를 하면서 기준값이 더 크면 교체를 하는 작업'으로 최솟값을 구한다.
Debug
iArr[5] = {3, 2, 1, 6, 5}
| i값 | arr[0] > arr[i] | T / F | Result |
|---|---|---|---|
| 1 | 3 > 2 | True | {2, 3, 1, 6, 5} |
| 2 | 2 > 1 | True | {1, 3, 2, 6, 5} |
| 3 | 1 > 6 | False | {1, 3, 2, 6, 5} |
| 4 | 1 > 5 | False | {1, 3, 2, 6, 5} |
Pass 1의 결과 : {1, 3, 2, 6, 5}
Step 2. 선택정렬 (ver. 1)
void selection_sort_ver1(int arr[], int cnt) {
for (int i = 0; i < (cnt - 1); i++) {
for (int j = (i + 1); j < cnt; j++) {
if (arr[i] > arr[j]) {
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
printArray(arr, cnt);
}이제는 최솟값을 구하는 과정을 4번 진행하여 오름차순으로 정렬을 하려고 한다.
즉, 비교하고 교체해서 최솟값을 찾고, 그 작업을 4번만 할 것이다.
(최솟값을 4번만 구하면 배열의 마지막 요소는 알아서 정렬이 될것이기에,
굳이 5번까지 할 필요가 없다.)
Debug
iArr[5] = {3, 2, 1, 6, 5}
| i값 | j값 | arr[i] > arr[j] | T / F | Result |
|---|---|---|---|---|
| 0 | 1 | 3 > 2 | True | {2, 3, 1, 6, 5} |
| 0 | 2 | 2 > 1 | True | {1, 3, 2, 6, 5} |
| 0 | 3 | 1 > 6 | False | {1, 3, 2, 6, 5} |
| 0 | 4 | 1 > 5 | False | {1, 3, 2, 6, 5} |
| 1 | 2 | 3 > 2 | True | {1, 2, 3, 6, 5} |
| 1 | 3 | 1 > 6 | False | {1, 2, 3, 6, 5} |
| 1 | 4 | 1 > 5 | False | {1, 2, 3, 6, 5} |
| 2 | 3 | 3 > 6 | False | {1, 2, 3, 6, 5} |
| 2 | 4 | 3 > 5 | False | {1, 2, 3, 6, 5} |
| 3 | 4 | 6 > 5 | True | {1, 2, 3, 5, 6} |
Pass 1의 결과 : {1, 3, 2, 6, 5}
Pass 2의 결과 : {1, 2, 3, 6, 5}
Pass 3의 결과 : {1, 2, 3, 6, 5}
Pass 4의 결과 : {1, 2, 3, 5, 6}
'selection_sort_ver1()'의 경우, 선택정렬 알고리즘 이론에 충실히 반영된 코드이다.
그러나 계속 비교하고 교체하여 최솟값을 찾아내는 과정을 4번이나 하기에 효율성이 떨어진다.
그래서 나온 방식이 'selection_sort_ver2()' 이다.
개선된 선택정렬 (ver. 2)
void selection_sort_ver2(int arr[], int cnt) {
for (int i = 0; i < (cnt - 1); i++) {
int iMinIdx;
iMinIdx = i;
for (int j = (i + 1); j < cnt; j++) {
if (arr[iMinIdx] > arr[j]) { // 비교하여
iMinIdx = j; // 조건이 만족하면 iMinIdx에 j의 index번호를 저장하여
// 최솟값의 위치를 기억함.
}
}
if (iMinIdx != i) {
int temp;
temp = arr[iMinIdx];
arr[iMinIdx] = arr[i];
arr[i] = temp;
}
}
printArray(arr, cnt);
}'selection_sort_ver2()'는 ver1의 단점을 보완하기 위해 개선된 방식으로,
비교, 교체를 반복하여 최솟값을 찾아내는게 아니라 '비교'만 하여 최솟값의 '위치'를 기억해
교체는 한번만 이루어지도록 할 것이다.
Debug
iArr[5] = {3, 2, 1, 6, 5}
| i값 | iMinIdx | j값 | arr[iMinIdx] > arr[j] | T / F | iMinIdx | Result |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 3 > 2 | True | 1 | |
| 0 | 1 | 2 | 2 > 1 | True | 2 | |
| 0 | 2 | 3 | 1 > 6 | False | 2 | |
| 0 | 2 | 4 | 1 > 5 | False | 2 | {1, 2, 3, 6, 5} |
| 1 | 1 | 2 | 2 > 3 | False | 1 | |
| 1 | 1 | 3 | 2 > 6 | False | 1 | |
| 1 | 1 | 4 | 2 > 5 | False | 1 | {1, 2, 3, 6, 5} |
| 2 | 2 | 3 | 1 > 6 | False | 2 | |
| 2 | 2 | 4 | 1 > 5 | False | 2 | {1, 2, 3, 6, 5} |
| 3 | 3 | 4 | 6 > 5 | True | 4 | {1, 2, 3, 5, 6} |
Pass 1의 결과 : {1, 2, 3, 5, 6}
ps. 배열을 내림차순 (= Descending)으로 정렬하려면
오름차순 정렬을 수행하는 알고리즘에서 크기 비교를 반대로 수행하면 된다.
Reference
한빛미디어) 이것이 C언어다 - 서현우의 C 프로그래밍 정복
한빛미디어) 이것이 취업을 위한 코딩테스트다 with 파이썬