[알고리즘] 버블 정렬

버블 정렬

버블 정렬. 인접한 두 원소의 교환을 통해 정렬을 수행합니다.

버블 정렬은 상당히 느린 정렬이지만 코드가 단순하기 때문에 정렬해야하는 대상의 개수가 많지 않을때 자주 사용합니다. 버블 정렬의 시간복잡도는 O(n²) 입니다.

 

EX) 2, 7, 4, 9, 1, 5 를 오름차순으로 정렬하라.

앞에서 부터 두 원소를 차례대로 비교하여 작은수가 왼쪽, 큰수가 오른쪽으로 가게 합니다.

2, 7, 4, 9, 1, 5 -> 7이 2보다 크므로 교환하지 않습니다.

2, 7, 4, 9, 1, 5 -> 4는 7보다 작으므로 교환합니다.

2, 4, 7, 9, 1, 5 -> 9는 7보다 크므로 교환하지 않습니다.

2, 4, 7, 9, 1, 5 -> 1은 9보다 작으므로 교환합니다.

2, 4, 7, 1, 9, 5 -> 5는 9보다 작으므로 교환합니다.

2, 4, 7, 1, 5, 9 -> 가장 큰 수인 9가 가장 오른쪽에 위치합니다.

이제 마지막 요소인 9를 제외한 나머지 부분을 같은 방식으로 정렬합니다.

 

C++로 된 간단한 샘플 소스입니다.

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

 

 

[참고자료]

https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC