[Sort] Bubble Sort

Bubble Sort 의 시간 복잡도는 상당히 높다. - worst case 일 경우에 O(n²)
그러나 이 엄청나게 느린 알고리즘을 사용하는 이유가 무엇일까...

시간 복잡도가 높다 하더라도 우리에게 주는 혜택은 당연 존재한다.

로직이 상대적으로 단순하여 프로그램상 구현하기가 쉽다.

그렇다면 그 실체는 어떤것일까,

Sort 대상 : 8 5 1 9 2

이렇게 5개의 숫자가 있다고 가정했을 경우 다음은 Bubble Sort 과정을 보여준다.

8 5 1 9 2        => 맨 처음 item과 그 다음에 존재하는 item을 비교한다.
5 8 1 9 2        => 첫번째 아이템이 다음의 아이템 보다 크므로 두 숫자를 바꿔준다.
5 8 1 9 2        => 그럼 인덱스를 한칸 옮겨 2번 아이템과 3번 아이템을 비교 한다.
5 1 8 9 2        => 역시 앞에 있는 아이템이 크므로 다음 아이템과 바꿔준다.
5 1 8 9 2        => 다시 인덱스를 한칸 옮겨 3번 아이템과 4번 아이템을 비교한다.
5 1 8 9 2        => 이번엔 뒤에 나온 아이템이 더 큰 수이므로 바꿀 필요가 없다.
5 1 8 9 2        => 인덱스를 한칸 옮겨 4번 아이템과 5번 아이템을 비교한다.
5 1 8 2 9        => 뒤에 나온 아이템이 더 작은 수이므로 앞의 아이템과 바꿔준다.

이렇게 Bubble Sort는 순차적으로 배열을 앞, 뒤로 비교를 하며 다음 인덱스로 넘어가면서 동일한 작업을 반복하게 된다.

아직 완벽하게 정렬되지 않았는데 저렇게 여러번 같은 작업을 반복하게 되면 끝내 정렬이 완료된다.

다음을 프로그램을 직접 돌려 과정을 출력한 것이다.

8 , 5 , 1 , 9 , 2
5 , 8 , 1 , 9 , 2
5 , 1 , 8 , 9 , 2
5 , 1 , 8 , 9 , 2

/////////////// 1차 정렬 종료

5 , 1 , 8 , 2 , 9
1 , 5 , 8 , 2 , 9
1 , 5 , 8 , 2 , 9
1 , 5 , 2 , 8 , 9

//////////////  2차 정렬 종료

1 , 5 , 2 , 8 , 9
1 , 5 , 2 , 8 , 9
1 , 2 , 5 , 8 , 9
1 , 2 , 5 , 8 , 9

///////////// 3차 정렬 종료

1 , 2 , 5 , 8 , 9
1 , 2 , 5 , 8 , 9
1 , 2 , 5 , 8 , 9
1 , 2 , 5 , 8 , 9

//////////// 완료

PHP로 구현한 예.

[code php]
<?php

     function BubbleSort($array , $call_reference = FALSE)
    {
        /* $array 값이 array인지 체크 */
        if(is_array($array))
        {
             /* 가장 마지막 아이템은 비교 하지 않기 때문에 -1 을 합니다. */
             $loop_count = count($array) - 1;
       
             do{
                  /* flag는 정렬이 제대로 되었을 경우 루프를 빠지기 위한 확인 값이다. */
                 $flag = false;
           
                 for($i = 0 ; $i < $loop_count ; $i++)
                 {
                     if($array[$i] > $array[$i + 1])
                     {
                         swap(& $array[$i] , & $array[$i + 1]);
                         $flag = true;    /* 정렬이 되었으면 루프를 진행하기 위하여 true로 변경 */
                     }
                 }
              }while($flag);    /* flag가 false가 될 때까지 루프 */
       
              if($call_reference === FALSE)
                 return($array);
        }
    }
       
    /* 스왑 함수 */
    function swap($a , $b)
    {
        $tmp = $b;
        $b = $a;       
        $a = $tmp;               
    }
?>

[/code]

C++ 로 구현한 예
[code cpp]
#include <iostream>
using namespace std;

void swap(int *a , int *b)
{
    int *tmp = b;   
    b = a;
    a = tmp;
}

int main()
{
    int a[5] = {8 , 5 , 1 , 9 , 2};

    int loop_count = (sizeof(a) / sizeof(a[0])) - 1;
    bool flag = false;   
   
    do{       
        flag = false;
       
        for(int i = 0 ; i < loop_count ; i++)
        {
            if(a[i] > a[i +1])
            {
                swap(a[i] , a[i + 1]);
                flag = true;
            }
        }
                   
    }while(flag);   
   
    return 0;
}
[/code]