<선택 정렬 구현>
[SelectionSort.c]
/*
* 알고리즘 - 선택 정렬(Selection Sort)
* 파일명: SelectionSort.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-26
* 이전 버전 작성 일자:
* 버전 내용: 간단한 선택 정렬 구현
* 이전 버전 내용:
*/
#include <stdio.h>
void SelectionSort(int arr[], int n)
{
int i, j;
int maxIdx; // 우선 순위가 가장 높은 인덱스 값
int temp;
for (i = 0; i < n - 1; i++)
{
maxIdx = i; // 인덱스 값은 i로. 맨 처음이라면 0부터
for (j = i + 1; j < n; j++)
{
if (arr[j] < arr[maxIdx]) // 오름차순 기준 정렬
maxIdx = j; // 만약 비교하는 값이 더 작다면 해당 인덱스로 바꾼다.
}
// 데이터 교환
temp = arr[i];
arr[i] = arr[maxIdx];
arr[maxIdx] = temp;
}
}
int main()
{
int arr[4] = { 3, 4, 2, 1 };
int i;
SelectionSort(arr, sizeof(arr)/sizeof(int));
for (i = 0; i < 4; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
[선택 정렬의 이해]
선택 정렬은 정렬 순서에 맞게 하나씩 ‘선택’해서 옮기는 알고리즘.
쉽게 말해서 처음부터 끝까지 쭉 훑어보면서 우선순위가 가장 앞서는 데이터를 찾아 가장 왼쪽부터 채운다.
"정렬 순서상 가장 앞서는 것을 선택하여 가장 왼쪽으로 이동 시키고,
원래 그 자리에 있던 데이터는 빈 자리에 가져다 놓는다."
위의 코드를 예시로 든다면, 맨 처음에는 3과 1을 교환하게 된다.
1이 이동하게 되면 1의 자리가 사실상 비는 것이므로 해당 자리에 3을 갖다 놓는 것.
그래서 실제로 보이기에는 교환하는 것처럼 보이게 된다.
[성능 평가]
버블 정렬과 마찬가지로 데이터가 $n$개가 있다면 $n-1$단계를 거쳐서 정렬을 수행하게 된다.
선택 정렬에서도 데이터 갯수가 $n$개일 때, 진행이 되는 비교의 횟수는 다음과 같아진다.
$(n-1) + (n-2) + … + 2 + 1$
이는 등차수열의 합으로 표현할 수 있으며, 다음과 같이 계산된다.
$$
\sum_{i=1}^{n-1}i = \frac{n(n-1)}{2} = \frac{n^2-n}{2}
$$
그래서 선택 정렬 또한 비교 연산에 대한 빅-오는 최악의 경우나 최선의 경우 구분 없이 $O(n^2)$이다.
그렇다면 데이터 이동 횟수는 버블 정렬과 같을까? 그렇지는 않다.
버블 정렬과 달리 데이터의 이동은 바깥쪽의 for문에서만 이뤄진다.
그래서 데이터의 이동 횟수의 경우에는 $(n-1)$회의 교환이 이뤄지게 된다.
최악이나 최선의 경우와 상관 없이 $3(n-1)$회 만큼의 이동 연산이 이뤄진다.
그래서 데이터 이동 연산(대입연산)에 대한 빅-오는 최악의 경우와 최선의 경우 구분 없이 $O(n)$이다.
<선택 정렬 구현>
[SelectionSort.c]
/*
* 알고리즘 - 선택 정렬(Selection Sort)
* 파일명: SelectionSort.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-26
* 이전 버전 작성 일자:
* 버전 내용: 간단한 선택 정렬 구현
* 이전 버전 내용:
*/
#include <stdio.h>
void SelectionSort(int arr[], int n)
{
int i, j;
int maxIdx; // 우선 순위가 가장 높은 인덱스 값
int temp;
for (i = 0; i < n - 1; i++)
{
maxIdx = i; // 인덱스 값은 i로. 맨 처음이라면 0부터
for (j = i + 1; j < n; j++)
{
if (arr[j] < arr[maxIdx]) // 오름차순 기준 정렬
maxIdx = j; // 만약 비교하는 값이 더 작다면 해당 인덱스로 바꾼다.
}
// 데이터 교환
temp = arr[i];
arr[i] = arr[maxIdx];
arr[maxIdx] = temp;
}
}
int main()
{
int arr[4] = { 3, 4, 2, 1 };
int i;
SelectionSort(arr, sizeof(arr)/sizeof(int));
for (i = 0; i < 4; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
[선택 정렬의 이해]
선택 정렬은 정렬 순서에 맞게 하나씩 ‘선택’해서 옮기는 알고리즘.
쉽게 말해서 처음부터 끝까지 쭉 훑어보면서 우선순위가 가장 앞서는 데이터를 찾아 가장 왼쪽부터 채운다.
"정렬 순서상 가장 앞서는 것을 선택하여 가장 왼쪽으로 이동 시키고,
원래 그 자리에 있던 데이터는 빈 자리에 가져다 놓는다."
위의 코드를 예시로 든다면, 맨 처음에는 3과 1을 교환하게 된다.
1이 이동하게 되면 1의 자리가 사실상 비는 것이므로 해당 자리에 3을 갖다 놓는 것.
그래서 실제로 보이기에는 교환하는 것처럼 보이게 된다.
[성능 평가]
버블 정렬과 마찬가지로 데이터가 $n$개가 있다면 $n-1$단계를 거쳐서 정렬을 수행하게 된다.
선택 정렬에서도 데이터 갯수가 $n$개일 때, 진행이 되는 비교의 횟수는 다음과 같아진다.
$(n-1) + (n-2) + … + 2 + 1$
이는 등차수열의 합으로 표현할 수 있으며, 다음과 같이 계산된다.
$$
\sum_{i=1}^{n-1}i = \frac{n(n-1)}{2} = \frac{n^2-n}{2}
$$
그래서 선택 정렬 또한 비교 연산에 대한 빅-오는 최악의 경우나 최선의 경우 구분 없이 $O(n^2)$이다.
그렇다면 데이터 이동 횟수는 버블 정렬과 같을까? 그렇지는 않다.
버블 정렬과 달리 데이터의 이동은 바깥쪽의 for문에서만 이뤄진다.
그래서 데이터의 이동 횟수의 경우에는 $(n-1)$회의 교환이 이뤄지게 된다.
최악이나 최선의 경우와 상관 없이 $3(n-1)$회 만큼의 이동 연산이 이뤄진다.
그래서 데이터 이동 연산(대입연산)에 대한 빅-오는 최악의 경우와 최선의 경우 구분 없이 $O(n)$이다.
