[CS] 알고리즘 03 : 버블 정렬 (Bubble Sort)

버블 정렬 (Bubble Sort)

버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법입니다.

정렬이 필요한 이유
어떤 배열이 주어졌을 때, 그 배열이 미리 정렬되어 있다면 훨씬 빠른 속도 로 검색이 가능하다.

버블 정렬의 동작 과정

STEP3를 보면 이미 정렬된 배열을 한번 더 돌게 되는데,
조금 더 효율적으로 코드를 짜기 위해서 한번도 Swap되지 않았을 경우에는
이미 정렬 된 상태이므로 바로 배열을 반환해주면 좋을 것 같다.

버블 정렬의 시간복잡도

버블 정렬의 시간복잡도는 O(n²)이다.

버블 정렬 코드 (Swift)

func bubbleSort(_ arr: [Int]) -> [Int] {
    var arr = arr
    let n = arr.count
    for i in 0..<n-1 {
        for j in 0..<n-i-1 {
            if arr[j] > arr[j+1] {
                arr.swapAt(j, j+1)
            }
        }
    }
    return arr
}
let arr = [3, 1, 4, 2]
print(bubbleSort(arr))
//[1, 2, 3, 4]

위에서 설명한것처럼 STEP2에서 이미 정렬됐음에도 불구하고
STEP3에서 종료가 된다.

STEP1: [1, 3, 2, 4]
STEP2: [1, 2, 3, 4]
STEP3: [1, 2, 3, 4]

버블 정렬 개선 코드 (Swift)

func bubbleSort(_ arr: [Int]) -> [Int] {
    var arr = arr
    let n = arr.count
    for i in 0..<n-1 {
        var didSwap = false
        for j in 0..<n-i-1 {
            if arr[j] > arr[j+1] {
                arr.swapAt(j, j+1)
                didSwap = true
            }
        }
        if !didSwap { return arr }
        print("STEP\(i+1):", arr)
    }
    return arr
}
let arr = [3, 1, 4, 2]
print(bubbleSort(arr))

이렇게 didSwap 변수를 생성해 swap이 일어나지 않았을 경우
바로 반환해주도록 개선해보았다.

STEP1: [1, 3, 2, 4]
STEP2: [1, 2, 3, 4]