버블 정렬 (Bubble Sort)

버블 정렬(Bubble Sort)란?

인접한 2개의 데이터를 비교하며 정렬하는 방식이다.

데이터를 비교하는 방식이 버블과 비슷하다고 해서 지어진 이름이라고 한다.

버블 정렬의 특징

시간복잡도 O(n^2)

 

구현이 간단해서 테스트용으로 정렬할 때 주로 사용한다.

버블 정렬 원리

임의의 숫자 배열을 만들고, 오름차순으로 정렬하는 과정을 PPT로 만들어보았다.

위 과정을 한번 반복하게 되면, 맨 끝에 확정된 숫자가 생긴다.

그 다음은 확정된 숫자를 제외한 나머지 숫자들로 위 과정을 반복한다. 

 

위 그림에 나타나 있는 과정을 반복해서 인덱스로 나타내보면,

(0,1) (1,2) (2,3) (3,4) (4,5) (5,6) (6,7) (7,8)> 8번 인덱스 값 확정

(0,1) (1,2) (2,3) (3,4) (4,5) (5,6) (6,7)> 7번 인덱스 값 확정

(0,1) (1,2) (2,3) (3,4) (4,5) (5,6)> 6번 인덱스 값 확정

(0,1) (1,2) (2,3) (3,4) (4,5)> 5번 인덱스 값 확정

(0,1) (1,2) (2,3) (3,4)> 4번 인덱스 값 확정

(0,1) (1,2) (2,3)> 3번 인덱스 값 확정

(0,1) (1,2)> 2번 인덱스 값 확정

(0,1) > 0, 1번 인덱스 값 확정

 

위 그림에 있는 데이터 값으로 나타내보면,

i = length-1(9-1=8), j = 0~i(0~8) 까지 비교하면, 데이터 값 9 확정

i = 7, j = 0~i 까지 비교하면, 데이터 값 8 확정

i = 6, j = 0~i 까지 비교하면, 데이터 값 7 확정

i = 5, j = 0~i 까지 비교하면, 데이터 값 6 확정

i = 4, j = 0~i 까지 비교하면, 데이터 값 5 확정

i = 3, j = 0~i 까지 비교하면, 데이터 값 4 확정

i = 2, j = 0~i 까지 비교하면, 데이터 값 3 확정

i = 1, j = 0~i 까지 비교하면, 데이터 값 1, 2 확정

 

 

결국에는 확정된 숫자들로 이루어진 오름차순 정렬이 완성된다.

버블 정렬 구현 (C++)

#include <iostream>
#include <ctime>

void BubbleSort(int* arr, int length)
{
    for (int i = length - 1; i > 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main()
{
    std::cout << "----------Random Value Array----------\n";
    srand((unsigned int)time(0));
    int arr[10];
    int arrLength = 10;
    for (int i = 0; i < arrLength; i++)
    {
        arr[i] = rand() % 100;
        std::cout << arr[i] << " ";
    }

    std::cout << "\n----------Bubble Sort----------\n";
    BubbleSort(arr, arrLength);
    for (int i = 0; i < arrLength; i++)
    {
        std::cout << arr[i] << " ";
    }
}

출력

----------Random Value Array----------
79 25 95 0 41 55 90 15 36 74
----------Bubble Sort----------
0 15 25 36 41 55 74 79 90 95