Sort/정렬 - Bubble Sort/거품 정렬

배열을 정렬하기 위한 다양한 알고리즘이 있다 이 글은 정렬의 기초 중의 기초인 버블 소트에 대해 작성한다.

버블 소트는 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복한다.

예를 들어 배열 안에 원소가 { 5, 4, 3, 6, 2 }가 있을 때 배열의 크기를 n을 5라고 하면

배열의 끝 부분인  n - 1부터 배열 안의 모든 원소를 비교하여 교환해주는 방식이다.

이를 나타내면 { 5, 4, 3, 6, 2 } -> { 2, 5, 4, 3, 6 } -> { 2, 3 ,5, 4, 6 } -> { 2, 3, 4, 5, 6 } 이 순서대로 정렬을 마친다.

보면 알 수 있듯이 버블 소트는 원소를 한 개씩 정렬해 나가는 걸 알 수가 있다.

 

알고리즘

요소의 개수를 size라 할때

1. 배열의 처음 인덱스부터 size - 1 인덱스까지의 각각의 인덱스에 대해

2. 끝에서부터 앞쪽으로 스캔하면서 이웃하는 두 요소를 비교하고 교환한다.

 

글로 설명하는 것보단 코드를 보는 게, 이해가 빠를 것이다.

코드

void Bubble_Sort(int arr[], int size){ // 기본적인 버블정렬
    for(int i = 0; i < size - 1; i++){ // i번째 원소까지는 정렬이 완료
        for(int j = size - 1; j > i; j--){
            if(arr[j - 1] > arr[j]){ // arr[j - 1]의 수가 더 크면 arr[j]와 Swap
                arr[j - 1] ^= arr[j] ^= arr[j - 1] ^= arr[j]; // XOR SWAP 
            }
        }
    }
}

주석을 달아놓았듯이 i번째 원소 까지는 정렬이 끝났다는 것이니 j는 size - 1에서  i보다 클 때까지만 반복해주면 된다.

두 변수의 SWAP은 XOR SWAP을 한 줄로 작성한 것인데 컴파일러에 따라 오류가 발생할 수도 있으니

권장하는 방법은 아니고, 그냥 변수를 SWAP 해준다는 뜻으로 이해하면 좋을 거 같다.

 

조금 변형한 알고리즘 1

배열이 이미 정렬을 마친 상태면 더 그 이후에는 교환을 하지 않는다 따라서 교환을 더 이상 하지 않는다는 걸 알면

이미 정렬된 상태이니 정렬 작업을 멈추면 된다.

ex) 배열 안의 원소가 { 5 ,2 ,3 ,4 ,1 } 일 때 한 번만 반복하면 { 1 ,2 ,3 ,4 ,5 }가 되어서 정렬된 상태가 된다.

다음에 반복을 해도 이미 정렬된 상태이니 요소를 비교해봐야 교환은 일어나지 않는다.

그렇기 때문에 교환이 일어났는지 아닌지 확인하는 변수를 두고 이미 정렬이 완료된 경우 작업을 중단시켜줘서

쓸 때 없는 작업을 안 할 수 있다.

 

코드

void Improved_Bubble_Sort_1(int arr[], int size){ // 개선1 교환 횟수에 따라 정렬작업을 멈춤
    for(int i = 0; i < size - 1; i++){ // i번째 원소까지는 정렬이 완료
        bool change = false; // 교환작업을 확인하는 변수
        for(int j = size - 1; j > i; j--){ // 계속 비교하면서  더 작은 수를 Swap
            if(arr[j - 1] > arr[j]){
                arr[j - 1] ^= arr[j] ^= arr[j - 1] ^= arr[j]; // XOR SWAP 
                change = true; // 교환이 있어나면 true
            }
        }               
        if(!change) break; // 교환이 일어 나지 않았으면
    }                     // 이미 정렬된 것이니 break
}

 

조금 변형한 알고리즘 2

배열의 원소가 { 1, 2, 5, 9, 10, 7 } 일 때  1, 2 ,5는 정렬을 마친 상태이다. 이걸 보고 알 수 있는 건 원소를 교환해주다,

어느 시점부터 교환이 일어나지 않는다면 이미 정렬된 상태라고 생각해도 좋다. 그래서 다음 반복에서는 

1, 2, 5를 제외한 9, 10, 7만 비교, 교환을 해주면 된다.

 

코드

void Improved_Bubble_Sort_2(int arr[], int size){ // 개선2 스캔 범위를 제한
// 각각 구간에서 비교, 교환을 하다가 어떤 시점이후 교환을 하지 않으면 앞쪽 요소는 이미 정렬을 마친상태라고 생각해도 좋음.
    int k = 0; // 처음반복에는 배열의 모든 원소를 비교해야 하기 때문에 0으로 초기화               
    while(k < size - 1){
        int last = size - 1; // 마지막으로 교환을 한 위치를 저장하는 변수
        for(int j = size - 1; j > k; j--){
            if(arr[j - 1] > arr[j]){
                arr[j - 1] ^= arr[j] ^= arr[j - 1] ^= arr[j];
                last = j; // 마지막으로 교환을 한 위치.
            }
        }
        k = last; // arr[k] 앞의 원소는 정렬을 마침
    }
}

 

전체 코드

#include <iostream>
using namespace std;

void Bubble_Sort(int arr[], int size){ 
    for(int i = 0; i < size - 1; i++){ 
        for(int j = size - 1; j > i; j--){ 
            if(arr[j - 1] > arr[j]){
                arr[j - 1] ^= arr[j] ^= arr[j - 1] ^= arr[j]; // XOR SWAP 
            }
        }
    }
}

void Improved_Bubble_Sort_1(int arr[], int size){
    for(int i = 0; i < size - 1; i++){
        bool judge = false; 
        for(int j = size - 1; j > i; j--){ 
            if(arr[j - 1] > arr[j]){
                arr[j - 1] ^= arr[j] ^= arr[j - 1] ^= arr[j]; // XOR SWAP 
                judge = true;
            }
        }               
        if(!judge) break;
    } 
}

void Improved_Bubble_Sort_2(int arr[], int size){
    int k = 0;                    
    while(k < size - 1){
        int last = size - 1;
        for(int j = size - 1; j > k; j--){
            if(arr[j - 1] > arr[j]){
                arr[j - 1] ^= arr[j] ^= arr[j - 1] ^= arr[j];
                last = j;
            }
        }
        k = last;
    }
}

int main(){
    int arr[] = {32,12,54,99,76};
    cout << "Before sorting : ";
    for(auto i : arr){
        cout << i << ' ';
    }
    cout << '\n';
    Bubble_Sort(arr,5);
    cout << "After  sorting : ";
    for(auto i : arr){
        cout << i << ' ';
    }
    return 0;
}

버블 정렬에 대해 알아봤다.

버블 정렬은 정렬 알고리즘 중에 기초적인 정렬로 교육용으로 자주 사용되는 정렬이지만 시간 복잡도가 O(n^2)이라는

매우 큰 단점이 있어서 프로그래밍 대회나 개발에서 실제로는 잘 사용되지 않는다.

그래도 버블 정렬의 장점이라면 중복된 값의 순서를 유지해주는 안정 정렬이라는 점이 있다.