[알고리즘] 정렬-버블정렬(bubble sort)

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.
참고교재: 쉽게 배우는 알고리즘(문병로)

기본적인 정렬 알고리즘 O(n^2)
1.선택정렬
2.버블정렬
3.삽입정렬

고급 정렬 알고리즘 O(n*logn)
1.병합정렬
2.퀵정렬
3.힙정렬

특수 정렬 알고리즘 O(n)
1.계수정렬
2.기수정렬

 

버블정렬이란

기본 정렬 알고리즘 중 하나인 버블정렬에 대해 알아보겠습니다.

버블 정렬(Bubble Sort)은 가장 간단하고 직관적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 리스트를 반복하면서 인접한 두 원소를 비교하고, 필요에 따라 위치를 바꿔가며 정렬을 수행합니다. 버블 정렬의 이름은 더 큰 값의 원소가 리스트의 끝으로 '거품(bubble)'처럼 서서히 올라가는 모습에서 유래했습니다.

버블정렬이 수행되는 모습,출처: 위키백과

버블 정렬의 기본적인 작동 방식은 다음과 같습니다:

1. 리스트의 첫 번째 원소부터 시작하여 인접한 원소끼리 비교합니다.
2. 만약 앞의 원소가 뒤의 원소보다 크다면, 두 원소의 위치를 바꿉니다. (오름차순 정렬의 경우)
3. 리스트의 끝까지 이 과정을 반복하며, 가장 큰 원소가 리스트의 마지막으로 이동합니다.
4. 이미 정렬된 마지막 원소를 제외하고, 나머지 리스트에 대해 같은 과정을 반복합니다.
5. 모든 원소가 정렬될 때까지 이 과정을 반복합니다.

버블 정렬은 구현이 매우 쉽지만, 평균적으로 O(n^2)의 시간 복잡도를 가지고 있어 데이터의 양이 많은 경우 비효율적입니다. 하지만, 데이터가 이미 거의 정렬된 상황에서는 상대적으로 빠르게 동작할 수 있으며, 안정적인 정렬 방법입니다.

 

버블정렬 코드 

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

 

테스트 코드 

int main() {
    int arr[] = {20, 30,10,21,5,39,2};
    int len = sizeof(arr)/ sizeof(arr[0]);

    cout<<"before bubble  :"<<endl;
    for(int i=0; i<len; i++){
        cout << arr[i] <<" ";
    }

    bubble_sort(arr, len);
    
    cout<<"\nafter bubble  :"<<endl;
    for(int i=0; i<len; i++){
        cout << arr[i] <<" ";
    }

    return 0;
}

 

테스트 결과

before bubble  :
20 30 10 21 5 39 2
after bubble  :
2 5 10 20 21 30 39

 

개선된 버블정렬

버블정렬은 이미 정렬이 되어있는 배열의 경우에도 계속 정렬하기 때문에 이러한 경우에 비효율적일 수 있습니다. 이를 해결하기 위해 bool 변수를 하나 만들어서 검사해주는 로직을 추가하면 이를 방지할 수 있습니다.

void improved_bubble_sort(int arr[], int len){
    int temp;
    for(int i=0; i<len; i++){
        bool sorted = true; //검사를 위한 flag
        for(int j=0; j< len-1-i; j++){
            if(arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                sorted = false; //원소가 교환되는 경우에 flag를 false로 바꾼다
            }
        }
        if(sorted) return; //flag가 true일 경우 리턴함
    }
}