<버블 정렬 구현>
[BubbleSort.c]
/*
* 알고리즘 - 버블 정렬(Bubble Sort)
* 파일명: BubbleSort.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-26
* 이전 버전 작성 일자:
* 버전 내용: 간단한 버블 정렬 구현
* 이전 버전 내용:
*/
#include <stdio.h>
void BubbleSort(int arr[], int n)
{
int i, j; // 반복문에 쓰일 변수 i, j
int temp; // 변수 swap에 사용할 임시 변수
for (i = 0; i < n - 1; i++) // 데이터가 n개라면 n-1만큼의 반복을 수행하여 정렬 진행
{
for (j = 0; j < (n - i) - 1; j++) // 교환이 이뤄지는 부분. 정렬되어 가면서 비교할 인덱스의 수가 줄어가므로 조건식은 j<(n-i)-1
{
if (arr[j] > arr[j + 1])
{
// 데이터 정렬
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main()
{
int arr[4] = { 3, 2, 1, 4 };
int i;
BubbleSort(arr, sizeof(arr) / sizeof(int));
for (i = 0; i < 4; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
[정렬 알고리즘을 배우기에 앞서]
우선순위 큐까지 학습하고 나서 자료구조에서 알고리즘으로 넘어가게 되었다.
자료구조를 공부하면서 갑자기 왜 알고리즘, 그것도 정렬에 관련된 것을 배우는가?
예전에는 이걸 공부하면서도 느닷없이 왜 이렇게 가는지에 대해서는 깊이 생각하질 않았었다.
그냥 가르쳐주니까 맹목적으로 배우기만 했었지, 그 이유를 생각하지는 않았던 것이다.
정렬 알고리즘을 배우는 이유는 자료구조에서의 '탐색'을 이해하기 위해서 배우는 것이다.
자료구조의 3대 연산은 [삽입, 삭제, 탐색(조회)]에 있다.
자료구조마다 어떻게 탐색하고 데이터를 조회하느냐는 성능과 연관이 있다.
그리고 여기서 탐색을 할 때 '정렬이 된 대상'을 탐색하게 된다.
그래서 탐색을 배우기 이전에 정렬이 선행되는 이유인 것이다.
[버블 정렬의 이해]
가장 단순한 정렬 알고리즘인 버블 정렬.
C에서도, C++에서도, 어지간한 언어들에서는 한 번씩은 봤던 정렬 알고리즘이다.
버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다.
그리고 정렬 순서 상 바뀌어야 하는 경우에는 두 데이터의 위치를 바꿔나가게 된다.
정렬의 기준을 토대로 우선순위가 가장 낮은, 제일 큰 값을 맨 뒤로 보내는 것이 해당 정렬의 특징이다.
버블 정렬인 이유는 앞에서부터 비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 같아서 그렇다고 한다.
[성능 평가]
정렬 알고리즘의 성능 평가는 두 가지를 근거로 평가를 하게 된다.
1) 비교의 횟수 → 비교 연산이 얼마나 수행되는가 → 대부분 빅-오 결정은 여기서
2) 이동의 횟수 → 위치의 변경을 위한 데이터의 이동 횟수 → 빅-오의 복잡도를 갖는 알고리즘간의 세밀한 비교 가능
버블 정렬의 경우, 위에 있는 for문이 중첩된 부분에 의해 비교연산이 수행된다.
위의 예시는 4개의 데이터를 총 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)$이다.
그리고 데이터 이동 횟수는 데이터가 이미 정렬이 다 되어있는 상태라면 데이터의 이동(교환)이 한 번도 발생하지 않는다.
하지만 최악의 경우에는 비교연산 횟수와 이동의 횟수가 일치하므로 $O(n^2)$이다.
엄밀히 따지면 3배 더 많지만, 빅-오를 판단하는 과정에서는 이를 고려하지 않는다.
