버블 정렬 : 이해와 구현
버블 정렬은 정렬의 대명사로 알려져 있는 만큼 이해하기도 구현하기도 쉽다.
하지만.. 그런만큼 성능에는 아쉬움이 있다.
우선 버블 정렬의 과정을 보자 !
이렇듯 버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다.
즉!
"정렬의 우선순위가 가장 낮은, 제일 큰 값을 맨 뒤로 보내기 ! "
를 반복하는 것이다.
왜 이름이 버블 정렬일까?
간단하다. 그냥 앞에서부터 순서대로 비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 비유되어 버블정렬 이라 이름이 지어졌다.
버블정렬 구현의 예
//
// main.c
// Sort
//
// Created by 서희찬 on 2021/04/12.
//
#include <stdio.h>
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])
{
//change data
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
int main(void)
{
int arr[4] = {3,2,4,1};
int i;
BubbleSort(arr, sizeof(arr)/sizeof(int));
for(i=0;i<4;i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
{3,2,4,1}이 오름차순으로 정렬 됐음을 확인 할 수 있다.
버블정렬의 구현은 버블 정렬을 구성하는 두 for문의 반복조건이 핵심이다.
따라서 대충이해가 아닌 정확한 이중 for문을 이해해야한다 !
나의 이해를 바탕으로 설명해보겠다..!
우선 i for문안에 j for문이 있다.
n = 4 로 주어졌다 !
그러므로 i는 0부터 3까지 반복한다!
이 말은 즉슨 ! i는 4번 반복한다는 말이다.
i가 커질수록 j의 반복횟수는 줄어든다.
왜냐하면 j는 (4-i)-1 만큼 반복하는데
i가 0,1,2,3 이되면 3,2,1,0 이된다.
즉, 위의 사진 처럼 처음에는 3번 비교연산을하고 다음은 두번 그 다음은 한번하고 나면 끝 이라는 말이다!
이렇게 돌리고 나면 오름차순 끝 !!
버블 정렬 : 성능 평가
정렬 알고리즘의 성능은 다음 두 가지를 근거로 판단하는 것이 일반적이다.
- 비교의 횟수 : 두 데이터간의 비교연산의 횟수
- 이동의 횟수 : 위치의 변경을 위한 데이터의 이동횟수
비교연산과 데이터 이동을 위한 대입연산이 정렬과정의 핵심 연산이기 때문 !!
실제로 시간 복잡도에 대한 빅-오를 결정하는 기준은 비교의 횟수이지만 이동의 횟수까지 살펴보면 동일한 빅-오의 복잡도를 갖는 알고리즘간의 세밀한 비교가 가능하다.
버블 정렬의 비교횟수는 반복문 안에 위치한 if문의 실행 횟수를 기준으로 계산할 수 있다.
그렇다면 버블 정렬의 비교 횟수는 얼마겠는가?
3+2+1 = 6이다.
이렇듯 버블 정렬에서 데이터의 수가 n개일 때 진행이 되는 비교의 횟수는
(n-1)+(n-2)+....2+1 이다 !
어랏.. 이건 등차수열!?
그러므로 시그마 i는 1부터 n-1까지의 합은
(n^2-n)/2이다 .
그러므로 !
버블 정렬의 비교연산에 대한 빅-오는
최악 최선 구분없이 O(n^2)이다.
어떤기.. 실제 활용하기 부담스러운 정도의 성능아닌가..
그렇다면 데이터의 이동횟수는 어떨까?
데이터가 이미 정렬되어있는 최선일 경우 교환이 한번도 일어나지 않지만 반대로 정렬기준의 역순으로 저장된 상태라면 비교의횟수와 이동의 횟수가 동일해져
O(n^2)이다.
(사실 3배 많지만 빅-오 판단하는 과정에서 이를 무시한다.)
이렇듯.. 버블정렬은 꾸진거같당~!
