Bubble Sort

class BubbleSort {
    func sort(_ array: [Int]) -> [Int] {
        var arr = array
        let n = arr.count
        for i in 0..<n-1 {
            for j in 0..<n-i-1 {
                if arr[j] > arr[j+1] {
                    // swap
                    let temp = arr[j]
                    arr[j] = arr[j+1]
                    arr[j+1] = temp
                }
            }
        }
        
        return arr
    }
}

let bubbleSort = BubbleSort()
bubbleSort.sort([5, 4, 3, 2, 1])
// [1, 2, 3, 4, 5]

버블 정렬은 옆에있는 수와 크기를 비교해서 작은 값을 앞으로 보내어 정렬하는 알고리즘이다. for문이 중첩되어있기 때문에 O(n^2)의 시간 복잡도를 가진다.

Merge Sort

병합 정렬은 배열을 가장 작은 단위가 될때까지 계속 반으로 나눈 다음 각각의 원소들을 병합하면서 정렬하는 알고리즘. 배열을 반으로 나눌때 O(log n), 병합할때 O(n)의 시간 복잡도가 생기기 때문에 O(n log n)의 시간 복잡도를 가진다.

Quick Sort

배열에서 기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽이라는 배열에, 큰 데이터는 오른쪽이라는 배열에 저장하고 왼쪽, 오른쪽 배열의 갯수가 1개 이하가 될때 까지 재귀함수로 리턴(순서는 왼쪽 + 기준점 + 오른쪽)한다. 병합 정렬과 마찬가지로 O(n log n)의 시간 복잡도를 가지지만 병합 정렬보다 빠르다.

참고

https://babbab2.tistory.com/101