2016. 12. 8. 13:56

안녕하세요. 게임 개발자 놀이터입니다.


이번 포스팅에선 버블 정렬에 대하여 설명해보려고 합니다.




버블 정렬 ( Bubble Sort )


버블 정렬 ( Bubble Sort )은 인접한 두 수 를 비교하여 큰 수를 뒤로 보내는 간단한 정렬 알고리즘입니다.

시간 복잡도는 O(N²)을 가지고 있습니다. 속도는 느린 편 이지만, 코드가 단순 해서 자주 언급됩니다.


원소의 이동이 꼭 거품이 수면으로 올라오는듯한 모습을 보이기 때문에 Bubble sort 라는 이름을 가지게 되었다고 합니다.



정렬 과정


간단하게 버블 정렬의 예시를 보여드리겠습니다.


아래와 같이 5개의 숫자가 주어졌다고 했을때,  Bubble Sort로 정렬 해보겠습니다.


9 5 1 3 7


먼저 첫번째 인덱스와 두번째 인덱스를 비교합니다.


9와 5, 9가 더 크므로 두 수 의 자리를 바꿉니다.


교제 전 : 9 5 1 3 7


교체 후 : 5 9 1 3 7


다음 인덱스를 하나 늘려서 두번째 인덱스와 세번째 인덱스를 비교합니다.


9와 1, 9가 더 크므로 두 수의 자리를 바꿉니다.


교체 전 : 5 9 1 3 7


교체 후 : 5 1 9 3 7


계속해서 인덱스를 늘려가며 값을 비교하고 자리를 바꿔줍니다.


교체 전 : 5 1 9 3 7

교체 후 : 5 1 3 9 7


교체 전 : 5 1 9 7

교체 후 : 5 1 3 7 9


이렇게 한번의 순회가 끝났습니다. 한바퀴의 순회가 끝나니까 가장 큰 수인 9는 자리 자리를 찾아갔습니다.


그럼 다음 순회에선 맨 마지막 원소는 방문할 필요가 없어졌네요.


맨 마지막 원소인 9는 고정하고 나머지 원소도 진행 해봅시다.


교체 전 : 5 1 3 8 9

교체 후 : 1 5 3 7 9


교체 전 : 1 5 3 7 9

교체 후 : 1 3 5 7 9


교체 전 : 1 3 5 7 9

교체 후 : 1 3 5 7 9


두번째 순회가 끝났네요. 예시로 랜덤하게 적은 숫자가 2번의 순회 만으로 정렬이 완료되어버렸네요.


그래도 어느정도 느낌을 잡힐꺼라 생각합니다.


이런게 바로 버블 정렬입니다! 하하


원소들이 큰 순서대로 뒤로 밀려가서 거품처럼 정렬되는 모습이었습니다.



예제 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void BubbleSort(int arrays[], int length)
{
    for(int i=0; i<length; ++i)
    {
        forint j=0; j < length-i-1 ; ++j)
        {
            if(arrays[j] > arrays[j+1])
            {
                int swap = arrays[j];
                arrays[j] = arrays[j+1];
                arrays[j+1= swap;
            }
        }
    }
}
cs


간단하게 구현했습니다.



알고리즘 분석


정렬 알고리즘은 분석을 할 필요가 있습니다.


제가 위에 시간 복잡도가 O(N²)라고 적어두긴 했지만 어떻게 구하는지도 알아야 합니다.


비교 횟수


버블 정렬은 한번의 순회를 마칠때마다 비교 대상이 하나씩 줄어듭니다.

전체 원소 갯수를 n개 라고 하면 총 n-1번의 순회를 돌면 정렬이 끝나게 됩니다.

5개의 원소 배열을 정렬한다면 4+3+2+1 = 10번 비교 하게 됩니다.

이를 수식화 하게되면


(n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1 = ( n-1 ) * n / 2 = n(n-1)/2


이렇게 됩니다.


자리 교환 횟수


최선의 경우, 그러니까 이미 정렬된 원소 배열일 경우, 정렬 과정중 자리 교환이 한번도 일어나지 않을겁니다.

최악의 경우, 원소들을 비교할때마다 자리교환이 일어나므로, 자리교환 횟수 또한 비교횟수와 같아질 것입니다.


최선의 경우 교환 횟수 : 0

최악의 경우 교환 횟수 : n(n-1)/2


비교 횟수 와 자리 교환 횟수를 더하면 n²-n 이 되는데 시간 복잡도는 상수는 생략하고 최고차항만 생각합니다.


따라서 시간 복잡도는 빅 오 표기법으로 O(N²) 이 됩니다.





밑의 자료는 제가 버블정렬에 대한 자료를 찾다가 발견한 자료들입니다.

버블 정렬의 이미지 예시 




버블 정렬의 동영상 예시

출처 ( 유투브 동영상(클릭) )





감사합니다.

Posted by 시리시안