오늘은 버블 정렬에 대하여 알아보도록 하겠습니다.

개요

인접한 두개의 원소를 비교하여 자리를 교환하는 방식을 버블 정렬이라고 하며, 첫번째 원소부터 마지막 원소까지 반복하면서 가장 큰 원소가 마지막 자리로 정렬되게 됩니다.

첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하게되면서 물 속에서 물 위로 올라오는 물방울 모양같다고 하여 버블 정렬이라고 불린다고 합니다.

알고리즘

bubbleSort(arr[],n){
    for(i<-n-1;i>=0;i<-i-1){
        for(j<-0;j<i;j<-j+1){
            if(arr[j]>a[j+1])then{
                swap(arr[j],arr[j+1]);
            }
        }
    }
}

이 버블 정렬에서 사용하는 메모리의 크기는 정렬할 원소의 갯수인 n개가 됩니다.

가장 빨리 연산될 경우는 이미 정렬되있는 상태이며, 이럴 경우에는 i번째 원소는 n-i번 비교하게 되므로 평균 비교 획수는 n(n-1)/2가 됩니다.

당연하겠지만, 이미 정렬되있는 상황에는 자리의 교환이 일어나지 않습니다.

버블 정렬에 연산 시간이 최대가 되는 경우에는 원소들이 역순으로 정렬되있는 경우에는 원소들이 완전히 역순으로 정렬되있는 경우일 것입니다.

이 경우에도 i번째 원소는 n-i번 교환이 일어나므로 평균 비교횟수는 똑같습니다.

하지만 자리교환은 n(n-1)/2번 일어가게 됩니다.

그래서 버블 정렬에서의 시간 복잡도는 O(n^2)입니다.