Bubble Sort With Swift

Bubble Sort

Bubble Sort는, 앞에서부터 2개씩 element 를 잡아서 정렬하는 방법이에요.

1 ~ 5 까지의 숫자가 임의로 배열에 하나씩 있다고 해볼게요.  ( 앞으로 모든 예시는 오름차순을 목표로 정렬하는 것으로 가정할게요 )

 

[4, 3, 5, 2, 1]

 

 

1.       4 과 3 을 비교합니다. 오름차순으로 정렬하는 경우,   4 < 3 이 아니므로 두 element 를 교환합니다.

[4, 3, 5, 2, 1]
// 1.       4 과 3 을 비교합니다. 오름차순으로 정렬하는 경우,   4 < 3 이 아니므로 두 element 를 교환합니다.
[3, 4, 5, 2, 1]
// 2.       4 과 5 을 비교합니다.  4 < 5 이므로 교환하지 않습니다.
// 3.       5 와 2 를 비교합니다. 5 < 2 가 아니므로 교환합니다.
[3, 4, 2, 5, 1]
// 4.       5 와 1 를 비교합니다. 5 < 1 가 아니므로 교환합니다.
[3, 4, 2, 1, 5]

처음부터 끝까지 한번씩 비교 및 교환과정을 마쳤고, 그 결과 행렬의 마지막 element 가 배열 중 가장 큰 값으로 정해졌습니다.

 

 

 

그럼 다시 처음부터 같은 과정을 반복하겠습니다. 마지막 element 는 가장 큰 값으로 정해졌으니 단계가 한번은 줄어들겠죠 ?? 

 

[3, 4, 2, 1, 5]
// 1.       3 과 4 를 비교합니다. 3 < 4 이므로 넘어갑니다.
// 2.       4 와 2 를 비교합니다. 4 < 2 가 아니므로 교환합니다.
[3, 2, 4, 1, 5]
// 3.       4 와 1 을 비교합니다. 4 < 1 이 아니므로 교환합니다.
[3, 2, 1, 4, 5]

이제 4와 5 가 바르게 정렬되었습니다. 

 

 

 

 

다시 한번 정렬을 하겠습니다.

[3, 2, 1, 4, 5]
// 1.       3 과 2 를 비교합니다. 3 < 2 가 아니므로 교환합니다.
[2, 3, 1, 4, 5]
// 2.       3 과 1 을 비교합니다. 3 < 1 이 아니므로 교환합니다.
[2, 1, 3, 4, 5]

3, 4, 5 가 바르게 정렬되었습니다.

 

다시 한번 정렬하겠습니다.

[2, 1, 3, 4, 5]
// 1.       2와 1 을 비교합니다. 2 < 1 이 아니므로 교환합니다.
[1, 2, 3, 4, 5]

 

Bubble 정렬이 끝났습니다! 

행렬에 5개의 element 가 있었고, 처음에는 4번의 정렬을 통해 가장 큰 수 5를 행렬의 마지막으로 옮길 수 있었습니다.

그 다음 으로는 3 번의 정렬, 차례로  2 번, 1 번의 정렬을 통해 행렬의 element 들이 큰 수 부터 차례로 자리를 잡게 되는 것을 확인할 수 있었습니다. 

행렬에 n 개의 element 가 있을 때, 정렬은 총 (n - 1 ) + (n - 2) + ... (2) + 1 번의 정렬을 하게되고, 총 n(n-1) / 2 번의 연산을 하게 됩니다.

 

 

 

 

첫번째 정렬 방법으로 bubbleSortWithFor 을 만들어보았습니다. 

func bubbleWithFor(arr: [Int]) -> [Int] {
    var newArr = arr
    var numOfRepeat = 0
    for _ in 0 ..< newArr.count - 1 {
        for j in 0 ..< newArr.count - numOfRepeat - 1{
            if (newArr[j] > newArr[j + 1]) {
                newArr.swapAt(j, j+1)
            }
        }
        numOfRepeat += 1
    }
    return newArr
}

method   [T].swapAt(j, j+1) 은 j 번째, j + 1 번째 element 를 바꿔줍니다. 

해당 함수가 잘 실행되는지 보기 위해 위에서 사용했던 array 를 그대로 쓰고, 중간중간 print 문을 통해 과정을 확인해봤습니다. 

let numbers = [4,3,5,2,1]

func bubbleWithFor(arr: [Int]) -> [Int] {
    var newArr = arr
    var numOfRepeat = 0
    var numOfTasks = 0
    print("before: \(newArr)")
    for _ in 0 ..< newArr.count - 1 {
        for j in 0 ..< newArr.count - numOfRepeat - 1{
            numOfTasks += 1
            if (newArr[j] > newArr[j + 1]) {
                newArr.swapAt(j, j+1)
                print(newArr)
            }
        }
        numOfRepeat += 1
    }
    print("numOfTest: \(numOfTasks)")
    return newArr
}

bubbleWithFor(arr: numbers)

 

결과

before: [4, 3, 5, 2, 1]
[3, 4, 5, 2, 1]
[3, 4, 2, 5, 1]
[3, 4, 2, 1, 5]
[3, 2, 4, 1, 5]
[3, 2, 1, 4, 5]
[2, 3, 1, 4, 5]
[2, 1, 3, 4, 5]
[1, 2, 3, 4, 5]
numOfTest: 10

 

 

 

 

 

추가로, Int 만이 아닌 다른 type 들에 대해서도 비교하고 싶어서 Generic 을 이용해서도 만들어보았습니다. 

let newArr = ["dba", "cab", "edg", "bgw", "adw"]

func bubbleWithFor<T: Comparable> (arr: [T]) -> [T] {
    var newArr = arr
    var numOfRepeat = 0
    var numOfTasks = 0
    print("before: \(newArr)")
    for _ in 0 ..< newArr.count - 1 {
        for j in 0 ..< newArr.count - numOfRepeat - 1{
            numOfTasks += 1
            if (newArr[j] > newArr[j + 1]) {
                newArr.swapAt(j, j+1)
                print(newArr)
            }
        }
        numOfRepeat += 1
    }
    print("numOfTest: \(numOfTasks)")
    return newArr
}

 

["adw", "bgw", "cab", "dba", "edg"]
numOfTest: 10

이번에는 문자 갯수가 동일한 [String] 에 대해서 적용해보았습니다. 최종 결과는 다음과 같았고 이는 기존 Int 를 반복했을 때와 똑같은 결과가 나왔습니다. 

 

 

 

 

 

 

 

 

Bubble Sort 의 경우, 처음부터 또는 어느 순간 정렬이 완료된 경우 다음 repetition 부터는 elements 간 교체가 이루어지지 않습니다. For statement 를 이용한 구현에서는 이러한 경우에도 같은 수의 반복을 행하기 때문에 비효율적입니다. 따라서, 중간에 정렬이 완료된 경우 정렬 과정을 바로 마칠 수 있도록 다르게 구현해보겠습니다. 

let array = [5, 4, 1, 2, 3]

func bubbleWithRecursion(array: [Int], numOfRep: Int = 0, _ isCompleted: Bool = false) -> [Int] {
    
    if isCompleted { // when sorting is done
        return array 
    }
    
    var isDone = true // turn into false if sorting is not done
    var arr = array

    for i in 0 ..< arr.count - 1 - numOfRep {
        if (arr[i] > arr[i+1]) {
            arr.swapAt(i, i+1)
            isDone = false // when change occur is not done yet !
        }
    }
    
    return bubbleWithRecursion(array: arr, numOfRep: numOfRep + 1, isDone)
}

bubbleWithRecursion(array: array)

(Function 을 처음 호출할 때 sorting 할 target array 만 넣어도 되도록 default Value 를 설정하였습니다.)

논리는 전 함수와 같습니다만, 이번에는 Recursion 을 이용하여 중간에 더이상 sorting 할게 없는 경우 과정을 종료시키도록 함수를 만들어보았습니다. 

 

설명을 단순하게 드리자면, bubbleWithRecursion 함수는 arguments 로 array, numOfRep, isCompleted 를 받습니다. 

각 argument 는 정렬할 배열, 완료된 사이클의 수, 정렬이 완료되었는지의 여부를 의미합니다. (여기서 사이클은 0번 인덱스부터 시작해서 정렬이 아직 완료되지 않은 인덱스 까지 한번씩 비교 및 교환하는 과정이라고 생각해주세요. )

 

함수가 호출된 후, 정렬이 완료된 배열이 parameter 로 올 경우 (isCompleted 의 값이 true 로 오는 경우) Recursion 을 종료합니다. (return array) 만약 함수를 처음 호출할 때 정렬이 완료된 배열이 오는 경우라도 한번은 확인을 위해 비교 과정을 거치고, 그 후에 다시 함수가 호출 될 때는 바로 종료되도록 만들었습니다. 

 

만약 정렬이 완료되지 않은 배열이 들어오는 경우라면 variable 'arr' 에 값을 대입하고 (변형하기 위해), 비교과정을 거친 후 다시 해당 함수를 호출합니다. 호출할 때 numOfRep 값을 1 증가시켜서 호출하는데, 이는 1번의 호출마다 뒤쪽 끝에 있는 elements 가 하나씩 바르게 정렬되기 때문에, 확실히 정렬된 elements 들은 비교과정을 거치지 않게 하기 위함입니다. 

 

아래 코드는 함수가 예상대로 작동하는지 테스트 하기 위한 코드입니다. Target array 를 [5, 4, 1, 2, 3] 으로 하였고, 3 번의 사이클을 끝낸 후 더이상 진행하지 않고 종료됨을 알 수 있습니다. ( 첫 2 번의 사이클에서 값들이 교환되고, 3번째 사이클에서는 정렬이 완료됨을 확인합니다. )

 

let array = [5,4,1,2,3]
var count = 0

func bubbleWithRecursion(array: [Int], numOfRep: Int = 0, _ isCompleted: Bool = false) -> [Int] {
    
    if isCompleted {
        print("ended", count)
        return array // when sorting is done
    }
    
    var isDone = true
    var arr = array

    for i in 0 ..< arr.count - 1 - numOfRep {
        if (arr[i] > arr[i+1]) {
            arr.swapAt(i, i+1)
            isDone = false // when change occur is not done yet !
        }
    }
    
    count += 1
    print("currentArray: \(arr), count: \(count)")
    
    return bubbleWithRecursion(array: arr, numOfRep: numOfRep + 1, isDone) // when it need more rep
}

print(bubbleWithRecursion(array: array))

//currentArray: [4, 1, 2, 3, 5], count: 1
//currentArray: [1, 2, 3, 4, 5], count: 2
//currentArray: [1, 2, 3, 4, 5], count: 3
//ended 3
//[1, 2, 3, 4, 5]

Bubble Sort 는 가장 좋은 경우 (이미 정렬되어 있는 경우) O(n) 을 갖습니다. 또한, 이 정렬은 배열의 앞에 있는 큰 수부터 뒤로 보내는 방식으로 정렬하기 때문에, 배열의 뒤쪽에 작은 수가 있는 경우가 아니라면 다른 기본적인 Sorting (Insertion, Selection) 방법보다 좋은 결과를 낼 수 있습니다. ( [5, 1, 2, 3, 4] 와 같은 경우 Bubble Sort 가 셋 중에서 가장 처리하는 연산의 수가 적습니다 )