버블 정렬의 이해
버블 정렬은 아주 쉬운 알고리즘이여서 쉽게 이해하기도 좋고 구현하기도 좋다.
단점으로는 성능이 좋지 못하다는 점이다.
버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다.
한 번 루프를 돌 때 가장 큰 값을 맨 뒤로 보내고 자리를 확정짓는다.
그리고 이를 반복한다.
두 데이터를 비교해서, 정렬 순서상 위치가 바뀌어야 하는 경우에 두 데이터의 위치를 바꾼다.
왜 이름이 버블 정렬일까?
앞에서부터 순서대로 비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 비유되어 버블 정렬이라 이름 지어졌다.
버블 정렬의 구현
void BubbleSort(int arr[], int n)
{
int i, j;
int temp;
for(i = 0; i < n - 1; i++)
{
for(j = 0; j < (n - i) - 1; j++)
{
if(arr[j] > arr[j+1])
{
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
}여기서 헷갈릴 수 있는 부분에 대해 부연 설명하겠다.
바깥 for문의 범위
바깥 for문을 봤을 때 범위가 n-1인데, 왜냐하면 예를 들어 4개의 데이터를 정렬해야 하는 경우에 3번만 돌아도 마지막 하나는 구지 연산할 필요없이 남은 자리에 들어가기 때문에 마지막 하나의 경우를 빼주므로 n - 1의 범위를 갖는 것이다.
안쪽 for문의 범위
안쪽 for문의 범위는 더 헷갈릴 수 있는데 잘 생각해 보면 간단하다.
버블 정렬의 핵심 논리는 가장 큰 값을 맨 뒤로 보내줘서 바깥 for문을 한 번 돌 때마다 맨 뒤에 자리가 확정이 나는 것이다.
따라서 i를 빼주는 것이다. 이미 확정이 난 자리를 반복해서 연산할 필요가 없으니까.
1을 빼주는 이유는 바깥 for문의 범위처럼 마지막 하나의 경우는 구지 연산할 필요가 없기 때문이다.
버블정렬의 성능
알고리즘의 성능을 따질 때는 시간 복잡도와 공간 복잡도를 고려한다.
하지만 알고리즘의 성능에는 시간 복잡도가 공간 복잡도에 비해 더 큰 영향을 미치므로 주로 시간 복잡도만 고려한다.
그럼 시간 복잡도는 어떻게 알 수 있을까 빅오 표기법으로 파악할 수 있다.
데이터의 수에 따른 연산의 횟수를 파악해야 한다.
정렬 알고리즘에서 핵심 연산은 두 가지이다.
1. 비교 연산
2. 이동 연산
두개의 연산 중 중요한 것은 어떤 것일까?
당연히 비교 연산이다.
비교연산은 무조건 하지만 이동 연산은 비교 연산의 결과에 따라 할 수도 있고 안 할 수도 있기 때문이다.
즉 이동 연산은 비교 연산에 종속적이다.
그러므로 비교 연산의 횟수로 시간 복잡도를 파악할 수 있을 것이다.
버블 정렬의 경우 4개의 데이터가 있을 때 3번 -2번 - 1번 이런 식으로 등차 수열 적으로 연산이 진행된다. 그러므로 등차수열의 합 공식으로 연산의 횟수를 알 수 있다.
(n^2 - n) / 2이므로
Big-O 표기법으로 보면
O(N^2)이 된다.
따라서 버블 정렬은 굉장히 성능이 좋지 못한 알고리즘임을 알 수 있다.
하지만 활용과 구현의 용이함이 있기 때문에 의미가 없다고 할 수는 없는 알고리즘이다.
