콘텐츠로 이동

11.3   버블 정렬

버블 정렬(bubble sort)은 인접한 원소를 계속 비교하고 교환하여 정렬한다. 이 과정이 거품이 아래에서 위로 올라오는 모습과 비슷하여 버블 정렬이라는 이름이 붙었다.

아래 그림(11-4)과 같이 원소 교환으로 거품이 올라오는 과정을 흉내 낼 수 있다. 배열의 맨 왼쪽부터 오른쪽으로 순회하며 인접한 두 원소를 비교하고, '왼쪽 원소 > 오른쪽 원소'이면 둘을 교환한다. 순회를 마치면 가장 큰 원소가 배열의 맨 오른쪽으로 이동한다.

원소 교환으로 거품의 이동 구현

버블 연산 2단계

버블 연산 3단계

버블 연산 4단계

버블 연산 5단계

버블 연산 6단계

버블 연산 7단계

그림 11-4   원소 교환으로 거품의 이동 구현

11.3.1   알고리즘 과정

배열의 길이가 \(n\)일 때 버블 정렬의 단계는 아래 그림(11-5)과 같다.

  1. 먼저 \(n\) 개 원소에 '버블 연산'을 수행하여 배열에서 가장 큰 원소를 올바른 위치로 옮긴다.
  2. 이어서 남은 \(n - 1\) 개 원소에 '버블 연산'을 수행하여 두 번째로 큰 원소를 올바른 위치로 옮긴다.
  3. 같은 과정을 반복하여 \(n - 1\) 회의 '버블 연산'을 수행하면 큰 순서로 \(n - 1\) 개 원소가 모두 올바른 위치에 놓인다.
  4. 남은 원소 하나는 반드시 가장 작은 원소이므로 정렬할 필요가 없으며, 배열 정렬이 완료된다.

버블 정렬 과정

그림 11-5   버블 정렬 과정

예시 코드는 다음과 같다.

bubble_sort.py
def bubble_sort(nums: list[int]):
    """버블 정렬"""
    n = len(nums)
    # 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for i in range(n - 1, 0, -1):
        # 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for j in range(i):
            if nums[j] > nums[j + 1]:
                # nums[j]와 nums[j + 1]을 교환한다
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
bubble_sort.cpp
/* 버블 정렬 */
void bubbleSort(vector<int> &nums) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for (int i = nums.size() - 1; i > 0; i--) {
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // nums[j]와 nums[j + 1]을 교환한다
                // 여기서는 std::swap() 함수를 사용한다
                swap(nums[j], nums[j + 1]);
            }
        }
    }
}
bubble_sort.java
/* 버블 정렬 */
void bubbleSort(int[] nums) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for (int i = nums.length - 1; i > 0; i--) {
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // nums[j]와 nums[j + 1]을 교환한다
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
            }
        }
    }
}
bubble_sort.cs
/* 버블 정렬 */
void BubbleSort(int[] nums) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for (int i = nums.Length - 1; i > 0; i--) {
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // nums[j]와 nums[j + 1]을 교환한다
                (nums[j + 1], nums[j]) = (nums[j], nums[j + 1]);
            }
        }
    }
}
bubble_sort.go
/* 버블 정렬 */
func bubbleSort(nums []int) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for i := len(nums) - 1; i > 0; i-- {
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for j := 0; j < i; j++ {
            if nums[j] > nums[j+1] {
                // nums[j]와 nums[j + 1]을 교환한다
                nums[j], nums[j+1] = nums[j+1], nums[j]
            }
        }
    }
}
bubble_sort.swift
/* 버블 정렬 */
func bubbleSort(nums: inout [Int]) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for i in nums.indices.dropFirst().reversed() {
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for j in 0 ..< i {
            if nums[j] > nums[j + 1] {
                // nums[j]와 nums[j + 1]을 교환한다
                nums.swapAt(j, j + 1)
            }
        }
    }
}
bubble_sort.js
/* 버블 정렬 */
function bubbleSort(nums) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for (let i = nums.length - 1; i > 0; i--) {
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for (let j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // nums[j]와 nums[j + 1]을 교환한다
                let tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
            }
        }
    }
}
bubble_sort.ts
/* 버블 정렬 */
function bubbleSort(nums: number[]): void {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for (let i = nums.length - 1; i > 0; i--) {
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for (let j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // nums[j]와 nums[j + 1]을 교환한다
                let tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
            }
        }
    }
}
bubble_sort.dart
/* 버블 정렬 */
void bubbleSort(List<int> nums) {
  // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
  for (int i = nums.length - 1; i > 0; i--) {
    // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
    for (int j = 0; j < i; j++) {
      if (nums[j] > nums[j + 1]) {
        // nums[j]와 nums[j + 1]을 교환한다
        int tmp = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = tmp;
      }
    }
  }
}
bubble_sort.rs
/* 버블 정렬 */
fn bubble_sort(nums: &mut [i32]) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for i in (1..nums.len()).rev() {
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for j in 0..i {
            if nums[j] > nums[j + 1] {
                // nums[j]와 nums[j + 1]을 교환한다
                nums.swap(j, j + 1);
            }
        }
    }
}
bubble_sort.c
/* 버블 정렬 */
void bubbleSort(int nums[], int size) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for (int i = size - 1; i > 0; i--) {
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}
bubble_sort.kt
/* 버블 정렬 */
fun bubbleSort(nums: IntArray) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for (i in nums.size - 1 downTo 1) {
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for (j in 0..<i) {
            if (nums[j] > nums[j + 1]) {
                // nums[j]와 nums[j + 1]을 교환한다
                val temp = nums[j]
                nums[j] = nums[j + 1]
                nums[j + 1] = temp
            }
        }
    }
}
bubble_sort.rb
### 버블 정렬 ###
def bubble_sort(nums)
  n = nums.length
  # 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
  for i in (n - 1).downto(1)
    # 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
    for j in 0...i
      if nums[j] > nums[j + 1]
        # nums[j]와 nums[j + 1]을 교환한다
        nums[j], nums[j + 1] = nums[j + 1], nums[j]
      end
    end
  end
end
코드 시각화

11.3.2   효율 최적화

어느 회의 '버블 연산'에서 교환이 한 번도 일어나지 않았다면 배열은 이미 정렬되어 있으므로 결과를 바로 반환할 수 있다. 따라서 이 상황을 감지하는 플래그 flag를 추가하고, 발생하는 즉시 반환할 수 있다.

최적화 후에도 버블 정렬의 최악 및 평균 시간 복잡도는 \(O(n^2)\)이다. 하지만 입력 배열이 완전히 정렬되어 있으면 최선 시간 복잡도인 \(O(n)\)에 도달한다.

bubble_sort.py
def bubble_sort_with_flag(nums: list[int]):
    """버블 정렬(플래그 최적화)"""
    n = len(nums)
    # 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for i in range(n - 1, 0, -1):
        flag = False  # 플래그를 초기화한다
        # 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for j in range(i):
            if nums[j] > nums[j + 1]:
                # nums[j]와 nums[j + 1]을 교환한다
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                flag = True  # 원소가 교환되었음을 기록한다
        if not flag:
            break  # 이번 버블 과정에서 원소 교환이 없었으므로 바로 종료한다
bubble_sort.cpp
/* 버블 정렬(플래그 최적화)*/
void bubbleSortWithFlag(vector<int> &nums) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for (int i = nums.size() - 1; i > 0; i--) {
        bool flag = false; // 플래그를 초기화한다
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // nums[j]와 nums[j + 1]을 교환한다
                // 여기서는 std::swap() 함수를 사용한다
                swap(nums[j], nums[j + 1]);
                flag = true; // 원소가 교환되었음을 기록한다
            }
        }
        if (!flag)
            break; // 이번 버블 과정에서 원소 교환이 없었으므로 바로 종료한다
    }
}
bubble_sort.java
/* 버블 정렬(플래그 최적화) */
void bubbleSortWithFlag(int[] nums) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for (int i = nums.length - 1; i > 0; i--) {
        boolean flag = false; // 플래그를 초기화한다
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // nums[j]와 nums[j + 1]을 교환한다
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
                flag = true; // 원소가 교환되었음을 기록한다
            }
        }
        if (!flag)
            break; // 이번 버블 과정에서 원소 교환이 없었으므로 바로 종료한다
    }
}
bubble_sort.cs
/* 버블 정렬(플래그 최적화)*/
void BubbleSortWithFlag(int[] nums) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for (int i = nums.Length - 1; i > 0; i--) {
        bool flag = false; // 플래그를 초기화한다
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // nums[j]와 nums[j + 1]을 교환한다
                (nums[j + 1], nums[j]) = (nums[j], nums[j + 1]);
                flag = true;  // 원소가 교환되었음을 기록한다
            }
        }
        if (!flag) break;     // 이번 버블 과정에서 원소 교환이 없었으므로 바로 종료한다
    }
}
bubble_sort.go
/* 버블 정렬(플래그 최적화)*/
func bubbleSortWithFlag(nums []int) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for i := len(nums) - 1; i > 0; i-- {
        flag := false // 플래그를 초기화한다
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for j := 0; j < i; j++ {
            if nums[j] > nums[j+1] {
                // nums[j]와 nums[j + 1]을 교환한다
                nums[j], nums[j+1] = nums[j+1], nums[j]
                flag = true // 원소가 교환되었음을 기록한다
            }
        }
        if flag == false { // 이번 버블 과정에서 원소 교환이 없었으므로 바로 종료한다
            break
        }
    }
}
bubble_sort.swift
/* 버블 정렬(플래그 최적화)*/
func bubbleSortWithFlag(nums: inout [Int]) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for i in nums.indices.dropFirst().reversed() {
        var flag = false // 플래그를 초기화한다
        for j in 0 ..< i {
            if nums[j] > nums[j + 1] {
                // nums[j]와 nums[j + 1]을 교환한다
                nums.swapAt(j, j + 1)
                flag = true // 원소가 교환되었음을 기록한다
            }
        }
        if !flag { // 이번 버블 과정에서 원소 교환이 없었으므로 바로 종료한다
            break
        }
    }
}
bubble_sort.js
/* 버블 정렬(플래그 최적화)*/
function bubbleSortWithFlag(nums) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for (let i = nums.length - 1; i > 0; i--) {
        let flag = false; // 플래그를 초기화한다
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for (let j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // nums[j]와 nums[j + 1]을 교환한다
                let tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
                flag = true; // 원소가 교환되었음을 기록한다
            }
        }
        if (!flag) break; // 이번 버블 과정에서 원소 교환이 없었으므로 바로 종료한다
    }
}
bubble_sort.ts
/* 버블 정렬(플래그 최적화)*/
function bubbleSortWithFlag(nums: number[]): void {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for (let i = nums.length - 1; i > 0; i--) {
        let flag = false; // 플래그를 초기화한다
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for (let j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // nums[j]와 nums[j + 1]을 교환한다
                let tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
                flag = true; // 원소가 교환되었음을 기록한다
            }
        }
        if (!flag) break; // 이번 버블 과정에서 원소 교환이 없었으므로 바로 종료한다
    }
}
bubble_sort.dart
/* 버블 정렬(플래그 최적화)*/
void bubbleSortWithFlag(List<int> nums) {
  // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
  for (int i = nums.length - 1; i > 0; i--) {
    bool flag = false; // 플래그를 초기화한다
    // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
    for (int j = 0; j < i; j++) {
      if (nums[j] > nums[j + 1]) {
        // nums[j]와 nums[j + 1]을 교환한다
        int tmp = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = tmp;
        flag = true; // 원소가 교환되었음을 기록한다
      }
    }
    if (!flag) break; // 이번 버블 과정에서 원소 교환이 없었으므로 바로 종료한다
  }
}
bubble_sort.rs
/* 버블 정렬(플래그 최적화) */
fn bubble_sort_with_flag(nums: &mut [i32]) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for i in (1..nums.len()).rev() {
        let mut flag = false; // 플래그를 초기화한다
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for j in 0..i {
            if nums[j] > nums[j + 1] {
                // nums[j]와 nums[j + 1]을 교환한다
                nums.swap(j, j + 1);
                flag = true; // 원소가 교환되었음을 기록한다
            }
        }
        if !flag {
            break; // 이번 버블 과정에서 원소 교환이 없었으므로 바로 종료한다
        };
    }
}
bubble_sort.c
/* 버블 정렬(플래그 최적화)*/
void bubbleSortWithFlag(int nums[], int size) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for (int i = size - 1; i > 0; i--) {
        bool flag = false;
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
                flag = true;
            }
        }
        if (!flag)
            break;
    }
}
bubble_sort.kt
/* 버블 정렬(플래그 최적화) */
fun bubbleSortWithFlag(nums: IntArray) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
    for (i in nums.size - 1 downTo 1) {
        var flag = false // 플래그를 초기화한다
        // 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
        for (j in 0..<i) {
            if (nums[j] > nums[j + 1]) {
                // nums[j]와 nums[j + 1]을 교환한다
                val temp = nums[j]
                nums[j] = nums[j + 1]
                nums[j + 1] = temp
                flag = true // 원소가 교환되었음을 기록한다
            }
        }
        if (!flag) break // 이번 버블 과정에서 원소 교환이 없었으므로 바로 종료한다
    }
}
bubble_sort.rb
### 버블 정렬(플래그 최적화)###
def bubble_sort_with_flag(nums)
  n = nums.length
  # 바깥쪽 반복문: 정렬되지 않은 구간은 [0, i]이다
  for i in (n - 1).downto(1)
    flag = false # 플래그를 초기화한다

    # 안쪽 반복문: 정렬되지 않은 구간 [0, i]의 최댓값을 교환하여 이 구간의 맨 오른쪽으로 옮긴다
    for j in 0...i
      if nums[j] > nums[j + 1]
        # nums[j]와 nums[j + 1]을 교환한다
        nums[j], nums[j + 1] = nums[j + 1], nums[j]
        flag = true # 원소가 교환되었음을 기록한다
      end
    end

    break unless flag # 이번 버블 과정에서 원소 교환이 없었으므로 바로 종료한다
  end
end
코드 시각화

11.3.3   알고리즘 특성

  • 시간 복잡도 \(O(n^2)\), 적응형 정렬: 각 회의 '버블 연산'에서 순회하는 배열 길이는 차례로 \(n - 1\), \(n - 2\), \(\dots\), \(2\), \(1\)이며, 합은 \((n - 1) n / 2\)이다. flag를 도입하여 최적화하면 최선 시간 복잡도가 \(O(n)\)이 된다.
  • 공간 복잡도 \(O(1)\), 제자리 정렬: 포인터 \(i\)와 \(j\)는 상수 크기의 추가 공간을 사용한다.
  • 안정 정렬: '버블 연산'에서 값이 같은 원소는 교환하지 않는다.
댓글로 의견이나 질문, 제안을 남겨 주세요