[Swift] 버블 정렬, 선택 정렬, 삽입 정렬

버블 정렬(Bubble Sort)은 첫 번째 와 두 번째를, 두 번째와 세 번째를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째와 마지막을 비교하여 교환하면서 자료를 정렬하는 방식이다.

func bubbleSort(array: [Int]) -> [Int]{
    var array = array
    var cnt = array.count
    
    for i in 0..<cnt{
        for j in 0..<cnt-i-1{
            // 값이 크면 바꾸기
            if(array[j] > array[j+1]){
                array.swapAt(j, j+1)
            }
        }
    }
    
    return array
}

 

첫 번째 for문에서 시간복잡도 O(N), 두 번째 for문에서도 시간복잡도 O(N) 만큼 소요되어 최종 시간복잡도는 O(N^2)이다.

---

선택 정렬(Selection Sort)는 특정 값(최소값)을 선택하여 그 값을 기준으로 정렬하는 방식이다.

func selectionSort(array: [Int]) -> [Int] {
    var array = array
    let n = array.count
    
    for i in 0..<n-1{
        var minIndex = i
        for j in 0..<n-i{
            if(array[i + j] < array[minIndex]){
                minIndex = i + j
            }
        }
        array.swapAt(i, minIndex)
    }
    
    return array
}

 

버블정렬과의 차이점이라면 최소값의 인덱스를 가지고 비교하여 정렬하는 방식이다. 이것도 결국 for문 두개를 사용하므로 최종 시간 복잡도는 O(N^2)이다.

---

삽입 정렬은 정렬된 것들은 제외하고 정렬이 필요한 것들만 비교하여 위치를 변경하여 정렬하는 방식입니다.

func insertionSort(array: [Int]) -> [Int] {
    var array = array
    let n = array.count
    
    for i in 1..<n{
        for j in 0..<i{ // 앞의 원소와 비교
            if(array[i - j] < array[i - j - 1]){    // 앞과 비교해서 더 크면 swap
                array.swapAt(i-j, i-j-1)
            }
            else{
                // 이미 정렬 되어있는 경우
                break
            }
        }
    }
    
    return array
}

 

이 삽입 정렬 또한 시간 복잡도는 O(N^2)이지만, 빅오메가로 표기시에는 이미 정렬되어 있는 경우가 있어 Ω(1)이다. 왜냐하면 별도의 배열을 만들지 않고,이미 정렬되어 있을 때는 작업을 건너 뛰기 때문에 시간복잡도와 공간복잡도가 다르다.