[Algorithm] Bubble Sort(거품 정렬) : 순차적으로 두 인접한 원소를 비교하여 정렬

알고리즘에서의 Bubble Sort(거품 정렬)에 대하여 Swift를 기반으로 하여 살펴봅니다.

 

 

#. 구독 대상

• 컴퓨터 및 소프트웨어 공학과 관련자
• 소프트웨어 관련 종사자 
• 기타 컴퓨터 공학에 관심이 있으신 분
• 알고리즘의 개념을 잡고 싶으신 분
• 기타 소프트웨어 개발과 지식에 관심이 있으신 모든 분들
• Swift 언어를 활용하여 알고리즘을 공부해보고 싶으신 분들

 

 

---

 

Bubble Sort(거품 정렬)

 

Bubble Sort는 배열을 순차적으로 두 인접한 원소를 검사하여 정렬하는 정렬 알고리즘입니다.

 

시간복잡도는 O(n^2)으로 높으나 코드가 단순하기 때문에 많이 사용됩니다.

 

원소의 이동이 거품이 수면위로 올라가는 듯한 모습을 보여서 붙여진 이름이라고 합니다.

 

 

 

 

---

 

 

 

기본 동작

 

기본적인 알고리즘의 컨셉을 살펴보면 아래와 같습니다.

 

 

1. 정렬하고자 하는 배열의 첫번째 인덱스 값부터 인접한 다음 인덱스의 값을 비교합니다.

2. 두 값을 비교 후 자리를 교체합니다.(오름차순일 시에는 오른쪽 값이 더 작을 경우 교체, 내림차순일 경우는 반대)

3. 인덱스를 한 칸 씩 이동하여 n-1번째 인덱스까지 교체 작업을 반복합니다.

4. 한번 라운드를 거치고 나면 가장 크거나 작은 값이 배열 맨 뒤로 이동되게 됩니다.

5. 모든 배열의 인덱스를 기준으로하여 비교를 마치면 최종 정렬을 마무리합니다.

 

[ 5, 2, 8, 1, 10, 4 ] 인 배열을 정렬한다고 생각해봅니다.

 

Bubble Sort 알고리즘을 통하여 정렬을 하면 아래와 같은 순서대로 정렬이 이루어집니다.

 

 

위의 과정을 토하여 1 라운드(Round)가 종료되었습니다. 

 

2라운드에서도 마찬가지로 배열의 첫번째 요소부터 다시 한번씩 계속 인덱스를 이동하면서 마지막 값까지 비교한 후 교체합니다.

 

마지막 라운드까지 진행하면 결국 [ 1, 2, 4, 5, 10 ] 로 정렬된 배열을 얻을 수 있습니다.

 

 

 

 

 

---

 

 

 

 

특징

 

버블 정렬(Bubble Sort)은 아래와 같은 특징을 가진 알고리즘입니다.

 

1. 배열 요소 첫 인덱스부터 순차적으로 인접한 요소끼리 비교하면서 교체하는 알고리즘

2. 이중 루프로서 구현이 됨에 따라서 시간 복잡도가 O(n^2)이다.

3. 선택 정렬과 비슷하게 이중 루프로서 요소를 비교하지만 매 라운드마다 처음부터 다시 비교하며 교환 또한 계속 이루어진다.

 

 

 

 

---

 

 

 

 

 

Implementation

 

Swift를 활용하여 버블 정렬 알고리즘을 살펴보겠습니다.

 

func bubbleSort<T: Comparable>(_ array: [T]) -> [T] {
    var sort = array
    
    for _ in 0..<sort.count {
        for j in 1..<sort.count {
            if sort[j-1] > sort[j] {
                sort.swapAt(j-1, j)
            }
        }
    }
    
    return sort
}

func bubbleSort<T: Comparable>(_ array: [T], _ isAscending: (T, T) -> Bool) -> [T] {
    var sort = array
    
    for _ in 0..<sort.count {
        for j in 1..<sort.count {
            if isAscending(sort[j-1], sort[j]) {
                sort.swapAt(j-1, j)
            }
        }
    }
    
    return sort
}

 

 

Fibonacci(피보나치)

public func fibonacci(n: Int) -> Int {
    if n == 0 || n == 1 {
        return n
    } else {
        return fibonacci(n: n-1) + fibonacci(n: n-2)
    }
}

// 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...
print("재귀 호출에서 피보나치 수열의 3번째 값은 \(fibonacci(n: 3))") // 재귀 호출에서 피보나치 수열의 3번째 값은 2

let numbers = [-1, 0, 1, 2, 5, 13, 15, 20, 68, 59, 51, 45, 77]

print(bubbleSort(numbers)) // [-1, 0, 1, 2, 5, 13, 15, 20, 45, 51, 59, 68, 77]
print(bubbleSort(numbers, <)) // [77, 68, 59, 51, 45, 20, 15, 13, 5, 2, 1, 0, -1]
print(bubbleSort(numbers, >)) // [-1, 0, 1, 2, 5, 13, 15, 20, 45, 51, 59, 68, 77]

 

 

 

---

 

 

 

이상으로 Swift를 기반으로하여 Bubble Sort(거품 정렬) 에 대하여 설명하였습니다.

 

 

 

 

감사합니다.

 

 

 

 

 

 

 

 

---

[참고 자료(References)]

 

 

[1] Swift3 ) Swift로 버블정렬(Bubble Sort)짜보기 : https://zeddios.tistory.com/67

[2] 버블 정렬 bubblesort with swift : https://hyerios.tistory.com/68

[3] [Swift]BubbleSort : http://minsone.github.io/programming/bubble-sort-in-swift

[4] 정렬 알고리즘(선택,삽입,버블) : https://hyunable.github.io/2017/10/21/sort-selection-insertion/

[5] What is Bubble Sort? : https://www.codingame.com/playgrounds/506/sorting-in-swift/bubble-sort

[6] Sorting Algorithms: Implementing Bubble Sort Using Swift : https://medium.com/swlh/sorting-algorithms-implementing-bubble-sort-using-swift-f21aafeb3fb0

[7] [알고리즘] 버블 정렬 bubble sort / flag : https://ppomelo.tistory.com/76

[8] Bubble Sort in Swift : https://big-o.io/examples/bubble-sort/swift/

[9] [알고리즘] 정렬 알고리즘 - 선택,버블,삽입 : https://baked-corn.tistory.com/114

[10] Bubble Sort in Swift : http://everythingswift.com/blog/2017/08/02/bubble-sort-in-swift/