버블 정렬은 간단하고 기본적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 인접한 두 요소를 비교하고 필요한 경우 서로 교환하면서 리스트를 반복적으로 훑어 정렬합니다. 버블 정렬은 원소를 왼쪽부터 차례로 비교하면서 가장 큰(또는 작은) 원소를 찾아가는 과정으로 작동합니다.

버블 정렬의 기본 원리

간단한 예시를 들어보겠습니다. [5, 2, 9, 1, 5] 라는 리스트를 정렬해 보겠습니다.

1. 먼저, 첫 번째 원소와 두 번째 원소를 비교합니다. 만약 두 번째 원소가 더 작다면, 두 원소는 교환됩니다.
2. 이어서 두 번째 원소와 세 번째 원소를 비교합니다. 이런 식으로 리스트의 마지막까지 비교가 이루어집니다. 이 과정을 완료하면 리스트의 가장 큰(또는 작은) 원소가 맨 오른쪽으로 이동합니다.
3. 이렇게 가장 큰(또는 작은) 원소를 맨 오른쪽으로 옮기고 나면, 다음 회전에서는 리스트의 마지막 요소는 정렬이 됐다고 가정합니다. 그리고 나면 마지막에서 두 번째 원소까지 비교가 이루어집니다.

위의 과정을 리스트의 길이-1번 반복하면, 정렬이 완료됩니다.

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

시간 복잡도

버블 정렬의 시간 복잡도는 O(n^2)입니다. 이는 모든 경우에 대해 두 요소를 비교하기 때문에 낮은 효율을 보입니다. 그러나 리스트의 크기가 작을 때는 효율적입니다.

그러나 리스트의 크기가 매우 크거나 이미 거의 정렬이 되어있을 때에는 효율적이지 않기 때문에 실제로는 잘 사용되지 않습니다.

버블 정렬은 간단하고 이해하기 쉬운 정렬 알고리즘인 만큼, 정렬 알고리즘에 대한 이해를 높이고자 하는 초보 프로그래머들에게는 좋은 학습 도구일 수 있습니다.

참고자료

• GeeksforGeeks: Bubble Sort

이상으로 버블 정렬 알고리즘에 대한 간략한 소개였습니다. 파이썬의 버블 정렬로 실제로 리스트를 정렬하는 과정을 더 자세히 알고 싶으시다면, 위의 참고자료로 들어가보시기를 추천드립니다.