자료구조 - 버블 정렬

[버블 정렬(Bubble Sort)]

버블 정렬(Bubble Sort)은 정렬 알고리즘 중 하나로, 리스트의 요소를 순차적으로 비교하고 인접한 두 요소를 교환하여 정렬하는 방식입니다.

가장 큰 요소가 한 번의 반복 후 리스트의 끝으로 "거품"처럼 이동하는 것이 특징입니다.

버블 정렬은 단순하지만 효율성 면에서는 다른 정렬 알고리즘보다 떨어집니다.

시간 복잡도는 최악의 경우 O(n^2)입니다.

 

버블 정렬 과정

1. 리스트의 첫 번째 요소부터 시작하여 인접한 두 요소를 비교합니다.
2. 만약 첫 번째 요소가 두 번째 요소보다 크면, 두 요소를 교환합니다.
3. 리스트 끝까지 이 과정을 반복하여 가장 큰 요소를 리스트의 끝으로 이동시킵니다.
4. 리스트의 끝에서부터 한 요소씩 제외하고 위의 과정을 반복합니다.
5. 리스트가 정렬될 때까지 반복합니다.

 

버블 정렬 의사 코드

함수 bubbleSort(arr):
    n = 배열의 길이(arr)
    for i = 0부터 n-1까지:
        for j = 0부터 n-i-2까지:
            if arr[j] > arr[j + 1]:
                arr[j]와 arr[j + 1] 교환
    반환 arr

 

 

버블 정렬의 예제

예시 리스트: [64, 25, 12, 22, 11]

첫 번째 반복:
    (64, 25) 비교하여 교환 → [25, 64, 12, 22, 11]
    (64, 12) 비교하여 교환 → [25, 12, 64, 22, 11]
    (64, 22) 비교하여 교환 → [25, 12, 22, 64, 11]
    (64, 11) 비교하여 교환 → [25, 12, 22, 11, 64]

두 번째 반복:
    (25, 12) 비교하여 교환 → [12, 25, 22, 11, 64]
    (25, 22) 비교하여 교환 → [12, 22, 25, 11, 64]
    (25, 11) 비교하여 교환 → [12, 22, 11, 25, 64]

세 번째 반복:
    (12, 22) 비교 → 교환하지 않음 → [12, 22, 11, 25, 64]
    (22, 11) 비교하여 교환 → [12, 11, 22, 25, 64]

네 번째 반복:
    (12, 11) 비교하여 교환 → [11, 12, 22, 25, 64]

 

 

버블 정렬 코드

#include <iostream>
#include <vector>

using namespace std;

// 버블 정렬 함수
void bubbleSort(vector<int>& arr) 
{
    int n = arr.size();  // 배열의 길이

    for (int i = 0; i < n - 1; i++) 
    {
        for (int j = 0; j < n - i - 1; j++) 
        {
            if (arr[j] > arr[j + 1]) 
            {
                swap(arr[j], arr[j + 1]);  // 인접한 두 요소를 교환
            }
        }
    }
}

int main() 
{
    vector<int> arr = {64, 25, 12, 22, 11};  // 예제 리스트

    cout << "정렬 전: ";
    for (int i : arr) 
    {
        cout << i << " ";
    }
    cout << endl;

    bubbleSort(arr);  // 버블 정렬 수행

    cout << "정렬 후: ";
    for (int i : arr) 
    {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}