[알고리즘] C++로 이해하는 버블 정렬

참고 : Do it! 자료구조와 함께 배우는 알고리즘 입문 (파이썬 편)

---

☑️ C++로 이해하는 버블 정렬

정렬 알고리즘은 데이터를 다루는 모든 프로그램에서 필수적인 요소로 사용된다. 정렬을 구사할 수 있는 다양한 알고리즘 중에서 버블 알고리즘은 간단한 알고리즘에 속하면서 개념을 이해하기가 쉽고 구현이 직관적이다. 하지만 효율성 문제로 실제 프로젝트에서는 많이 사용되지 않는다.

 

☑️ 버블 정렬이란 무엇일까?

버블 정렬은 인접한 두 원소를 비교하여 필요에 따라 위치를 교환한다. 이 과정을 반복하면 큰 값이 배열의 끝으로 천천히 이동하는데, 이러한 모습이 거품이 수면 위로 떠오르는 것과 비슷해서 버블 정렬이라는 이름을 가진다.

 

1️⃣ 버블 정렬 의사코드

1. 배열의 첫 번째 원소부터 시작해서 인접 원소와 비교한다.
2. 현재 원소가 다음 원소보다 크다면, 두 원소의 위치를 교환한다.
3. 다음 원소로 이동해서 같은 작업을 반복한다.
4. 배열의 끝에 도달하면 한 턴이 종료되고 가장 큰 원소가 배열의 마지막에 위치한다.
5. 배열 크기 - 1번 반복한다.

 

2️⃣ 버블 정렬 과정 시각화

 

3️⃣ 버블 정렬 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

void bubbleSort(vector<int>& array)
{
    int t = array.size() - 1;
    for (int i = 0; i < t; ++i) {
        for (int j = 0; j < t - i; ++j) 
        {
            if (array[j] > array[j + 1])
            {
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
            }
        }
    }
}

void printArray(string msg, vector<int>& array) {
    cout << msg << " : ";
    for (int i = 0; i < array.size(); ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}

int main(void) {
    vector<int> numbers = { 2,5,1,8,9 };
    
    printArray("정렬 전", numbers);
    bubbleSort(numbers);
    printArray("정렬 후", numbers);


    return 0;
}

 

☑️ 버블 정렬을 최적화 해보자.

기본적으로 버블 정렬은 배열이 이미 정렬된 상태라고 해도 모든 배열을 순회하기 때문에 비효율적이다. 이를 최적화하기 위해서는 한 번의 순회 동안 교환이 발생하지 않았다면, 배열이 이미 정렬되었다고 판단하고 알고리즘을 종료하는 것이다.

 

1️⃣ 최적화된 버블 정렬 시각화

 

2️⃣ 최적화된 버블 정렬 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

void bubbleSort(vector<int>& array)
{
    int t = array.size() - 1;
    bool isSwap;
    for (int i = 0; i < t; ++i) {
        isSwap = false;
        for (int j = 0; j < t - i; ++j) 
        {
            if (array[j] > array[j + 1])
            {
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;

                isSwap = true;
            }
        }

        if (isSwap == false)
            break;
    }
}

void printArray(string msg, vector<int>& array) {
    cout << msg << " : ";
    for (int i = 0; i < array.size(); ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}

int main(void) {
    vector<int> numbers = { 2,5,1,8,9 };
    
    printArray("정렬 전", numbers);
    bubbleSort(numbers);
    printArray("정렬 후", numbers);


    return 0;
}

 

3️⃣ 개선된 성능

😓 최적화 전

최악의 경우	O(n^2)
평균의 경우	O(n^2)
최선의 경우	O(n^2)

 

😁 최적화 후

최악의 경우	O(n^2)
평균의 경우	O(n^2)
최선의 경우	O(n)