거품 정렬(Bubble Sort)

Bubble Sort

정렬 과정에서 원소의 이동이 거품이 수면으로 올라가는 모습을 보이기 때문에 지어진 이름입니다.

서로 인접한 두 원소를 비교하여 주어진 조건에 맞으면(또는 맞지 않으면) 자리를 교환하여 정렬하는 알고리즘입니다.

중요한 것은 Compare(비교) 후  Swap(교환)입니다.

 

Process

1부터 6까지 랜덤으로 들어 있는 배열이 있습니다.

Ascending(오름차순)으로 Bubble Sort 하려고 합니다.

1. 첫 번째 아이템(4)과 두 번째 아이템(6)을 비교합니다.
2. 두 번째 아이템이 더 크기 때문에 아이템을 교환하지 않습니다.
3. 두 번째(6) 세 번째(5) 인덱스의 아이템을 비교합니다.
4. 세 번째 아이템이 더 작기 때문에 아이템을 교환합니다.
5. 위 과정을 마지막 인덱스까지 반복합니다.

여기까지 1 사이클이 되고, 이를 수행하게 되면 가장 마지막 인덱스에는 가장 큰 값이 들어 있습니다.

마지막 인덱스는 정렬이 완료되었기 때문에 2 사이클부터는 sort 과정에서 제외됩니다.

2 사이클에서도 정렬된 마지막 인덱스의 전 인덱스까지 Compare(비교)와 Swap(교환)을 반복합니다.

 

이렇게 정렬을 1 사이클을 수행할 때마다 정렬에서 제외되는 데이터가 나오게 되고, 모든 사이클을 완료하면 정렬이 완료 되게 됩니다.

 

 Code

void bubbleSort(int arr[], int length)
{
    int temp = 0;
    for (int i=0; i < length; i++) { // 정렬이 완료 된 아이템의 수
        for (int j=1; j < length - i; j++) { // 비교 대상 (정렬된 아이템은 정렬을 다시 하지 않는다)
            if (arr[j] < arr[j-1])
            {
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
}

 

Time Complexity of Bubble Sort

Bubble Sort는 반복문이 두 번 있는 케이스이고, 배열의 정렬 여부와 관계없이 2개의 원소를 비교하기 때문에 최악/최선 모두의 시간 복잡도는 O(n^2)가 됩니다.

 

https://www.bigocheatsheet.com

 

참고

• https://blog.chulgil.me/algorithm/
• https://www.bigocheatsheet.com