[알고리즘] 버블정렬 (Bubble Sort)

오늘은 버블정렬에 대해서 복습을 했습니다.

복습한 김에 기록합니다.

버블정렬(Bubble Sort) 이란? 

옆에있는 요소와 비교를 해가며 검사하고 정렬하는 방법입니다.

버블정렬의 특징

1.   시간복잡도가 O(n^2) 이기때문에 상당히 느리다.
2.   가장 간단한 알고리즘이다.

버블정렬의 알고리즘

오름차순을 기준으로 하겠습니다.

[3, 9, 2, 5, 6, 7]   이러한 배열이있습니다.

1.  3 > 9 ?  ( X )                    [3, 9, 2, 5, 6, 7]

2. 9 > 2 ?  ( O )                   

    9 와 2의 자리를 바꾼다.     [3, 2, 9, 5, 6, 7]

3. 9 > 5 ? ( O )

    9 와 5의 자리를 바꾼다.     [3, 2, 5, 9, 6, 7] 

4. 9 > 6 ? ( O )

    9 와 6의 자리를 바꾼다.     [3, 2, 5, 6, 9, 7]  

5. 9 > 7 ? ( O )

    9 와 7의 자리를 바꾼다.     [3, 2, 5, 6, 7, 9]  

이렇게 한번의 정렬이 끝났습니다.

그 다음도 똑같은 방법으로 정렬을 시작합니다.

1.  3 > 2 ?  ( O )                    

    3 과 2의 자리를 바꾼다.     [2, 3, 5, 6, 7, 9]  

2.  3 > 5 ? ( X )

3.  5 > 6 ? ( X )

4.  6 > 7 ? ( X )

...

...

...

이렇게 쭉나가게 되는데요 여기서 핵심이있습니다.

맨마지막 값들은 비교할 필요가 있을까요?

거품은 한번올라가면 내려가지않습니다.

다시 얘기하면, 이미 처음 정렬에서 9는 제일 큰수 임을 비교 당했기 때문에

두번째 정렬을 할때는 비교할 필요가 없다는 말이죠.

소스코드로 보겠습니다.

#include <iostream>

int main() {
    int array[10] = {10, 3, 4, 45, 34, 23, 12 ,42, 13, 33}; //초기화
    
    for(int i = 0; i < sizeof(array) / sizeof(int); i++){ //오름차순정렬
        for(int j = 0; j < sizeof(array) / sizeof(int) - 1 - i; j++){
            if(array[j] > array[j + 1]){
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
            }
        }
    }
    
    for(int i = 0; i < sizeof(array) / sizeof(int); i++){ // 출력
        printf("%4d", array[i]);
    }
    std::cout << std::endl;
    return 0;
}

for(int i = 0; i < sizeof(array) / sizeof(int); i++){

        for(int j = 0; j < sizeof(array) / sizeof(int) - 1 - i; j++){

}

}




이러한 형태의 이중 for문이 들어가 있는데요.

sizeof(array) / sizeof(int) 는 배열의 길이를 나타내는 부분입니다.

두번째 for문에서 조건에

sizeof(array) / sizeof(int) - 1 - i

이부분이 이해가 잘 안되실 텐데요

저도 처음에 왜 - 1을 하고 - i 를 해야하는지 의문이었습니다.

차근차근 생각을 해보면

예) (오름차순 기준)

처음에 정렬이 한번 됐다 => 배열의 맨 마지막 값은 최대값이다. [3, 2, 5, 6, 7, 9]  

두번째 정렬이 됐다 => 맨뒤에서 두번째  [3, 2, 5, 6, 7, 9]  

여기서 과연 맨 마지막 값은 비교할 필요가 있을까요 ?

없습니다.

왜냐하면 이미 마지막은 전부 비교를 거쳤기 때문에 고정된 최대 값이기 때문이죠

각 요소들의 싸움에서 서열 1위가 됐는데 굳이 서열정리를 할 필요가 있을까요?

1위는 1위입니다.

다음은 2위를 가립니다.

두번째 정렬이 끝난 뒤에는

1위 뒤에는 2위가 있습니다.

2위는 1위보단 약하지만 변하지않는건 자기보다 아래는 약하다는 사실이죠.

그래서 두번째 정렬이 끝나면 비교를 또 할 필요가 없습니다.

- 1을 하는 이유

for(int j = 0; j < sizeof(array) / sizeof(int) - 1 - i; j++){

            if(array[j] > array[j + 1]){

                int temp = array[j + 1];

                array[j + 1] = array[j];

                array[j] = temp;

            }

        }

여기서 

-1을 하지않는다면

array[0] > array [1] (비교 생략)

array[1] > array [2] (비교 생략)

array[2] > array [3] (비교 생략)

array[3] > array [4] (비교 생략)

array[4] > array [5] (비교 생략)

array[5] > array [6] (비교 생략)

array[6] > array [7] (비교 생략)

array[7] > array [8] (비교 생략)

array[8] > array [9] (비교 생략)

array[9] > array [10] (비교 생략)

이렇게 진행이 되는데요

이상한점이있습니다

소스코드의 array[] 는 

array[0] ~ array[9]까지의 범위인데

맨마지막 비교에서

array[9] > array [10] (비교 생략)

array[10]을 말하고있습니다.

이러면 배열의 인덱스값을 벗어나 원치않은 값을 얻습니다.

- 1을 해주게 된다면 

비교횟수는 1번 줄게 되겠지만

줄어도 됩니다.

왜냐하면

처음 i = 0 의 비교가 끝난다면

마지막은 제일 큰 값이 자동적으로 들어가기 때문입니다.

내림차순으로 하려는 분들은

if(array[j] < array[j + 1])

이렇게 조건을 바꿔주면 됩니다.

이상 버블정렬이었습니다.

알고리즘 두번째 글이네요 ! 

미숙한 점들 지적 부탁드립니다!

알게된점 : 사실 버블정렬을 외우고만 있었는데 다시한번 머릿속에서 정리가 되었다.

알아야할점 : Big - oh(O) 표기법을 자세히 알아야함. 시간복잡도(Time Complexity), 공간복잡도(Space Complexity) 등등