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

버블 정렬(Bubble Sort)

 

버블 정렬이란?

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 이다
• 시간복잡도는 O(n^2)를 가지게 된다.
• 정렬 알고리즘 중에 연산 수가 많아 가장 느리고 효율성이 떨어진다.

버블 정렬 과정

 

- 첫번 째 루프 -

• 첫 번째 4 와 두 번째 3 을 비교 후 왼쪽의 숫자가 크니 서로 바꾼다.  4 3 2 1 5 -> 3 4 2 1 5
• 두 번째 4 와 세 번째 2 를 비교 후 왼쪽의 숫자가 크니 서로 바꾼다.  3 4 2 1 5 -> 3 2 4 1 5
• 세 번째 4 와 네 번째 1 을 비교 후 왼쪽의 숫자가 크니 서로 바꾼다.  3 2 4 1 5 -> 3 2 1 4 5
• 네 번째 4 와 다섯 번째 5 를 비교 후 왼쪽의 숫자가 작으니 그대로 둔다. 3 2 1 4 5

- 두번 째 루프 -

• 첫 번째 3 과 두 번째 2 를 비교 후 왼쪽의 숫자가 크니 서로 바꾼다.  3 2 1 4 5 -> 2 3 1 4 5
• 두 번째 3 과 세 번째 1 을 비교 후 왼쪽의 숫자가 크니 서로 바꾼다.  2 3 1 4 5 -> 2 1 3 4 5
• 세 번째 3 과 네 번째 4 를 비교 후 왼쪽의 숫자가 작으니 그대로 둔다. 2 1 3 4 5

- 세번 째 루프 -

• 첫 번째 2 와 두 번째 1 을 비교 후 왼쪽의 숫자가 크니 서로 바꾼다.  2 1 3 4 5 -> 1 2 3 4 5
• 두 번째 2와 세 번째 3 을 비교 후 왼쪽의 숫자가 작으니 그대로 둔다. 1 2 3 4 5

버블 정렬 정리

1. 위에 과정을 통해 오름차순 정렬을 하였다.

2. 첫 번째 숫자와 인접한 오른쪽의 두 번째 숫자를 비교 후 왼쪽의 숫자가 크면 서로 바꾼다.

3. 그렇게 제일 큰 숫자를 오른쪽 끝에 배치하게 된 후 그 숫자는 다음부턴 검사를 안하게 된다. 이때는 O(n)

4. 한번의 루프가 끝난 후 다시 처음부터 제일 큰 숫자 전까지 검사를 하게 된다.  이때부터 O(n^2)이 된다

 

 

버블 정렬 코드

#include <iostream>

int main()
{
    int Array[5] = { 4,3,2,1,5 };

    int Count = 5;

    for (int i = 0; i < Count - 1; ++i)
    {
        for (int j = 0; j < Count - 1; ++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 < Count; ++i)
    {
        std::cout << Array[i] << " ";
    }
}