[Data Structure] Bubble, Selection, Insertion Sort (Swift)

아주 기본적인 정렬들을 공부해볼게요

대표적으로

거품정렬(Bubble Sort)

선택정렬(Selection Sort)

삽입정렬(Insertion Sort)

이렇게 3가지가 있구요

 

각각 특징과 구현을 해볼거에요

 

거품정렬

정렬과정

인접한 두 원소의 대소를 비교해서 자리를 교환하면서 정렬해요

 

시간복잡도

O(n^2)

 

func bubbleSort(arr: [Int]) -> [Int] {
    var arr = arr
    for i in arr.indices { // i번 시도
        for j in 1..<arr.count-i { // 끝에서 i번째 정렬됌
            if arr[j-1] > arr[j] { // 스왑
                let temp = arr[j]
                arr[j] = arr[j-1]
                arr[j-1] = temp
            }
        }
    }
    return arr
}

 

 

선택정렬

정렬과정

Index 0부터 차례대로 해당 순서에 원소 넣을 위치를 정하고

주어진 배열중 최솟값을 찾고

그 값을 정해둔 위치에 있는값과 교환

...반복...

-> 해당 순서에 원소넣을 위치는 이미 정해져있고 어떤 원소를 넣을지 정하는 과정

 

시간복잡도

O(n^2)

func selectionSort(arr: [Int]) -> [Int] {
    var arr = arr
    for i in arr.indices { // 삽입할 위치 i
        var minIndex = i
        for j in i+1..<arr.count { // 삽입위치 다음부터 비교
            if arr[minIndex] > arr[j] { // 최솟값 저장
                minIndex = j
            }
        }
        // 스왑
        let temp = arr[minIndex]
        arr[minIndex] = arr[i]
        arr[i] = temp
    }
    return arr
}

 

삽입정렬

정렬과정

두번째 원소부터 시작하며

이전의 값과 비교해서 원소를 뒤로 옮기고 지정된 자리에 삽입하여 정렬

 

시간복잡도

O(n^2)

최선의 경우O(n) - 모두 정렬 돼있는 경우 한번씩만 비교

func insertionSort(arr: [Int]) -> [Int] {
    var arr = arr
    for i in 1..<arr.count { // 두번째 원소부터 검사
        for j in stride(from: i, to: 0, by: -1) { // 현재보다 이전의 것과 비교하면서 앞으로 이동
            if arr[j] < arr[j-1] {
                let temp = arr[j]
                arr[j] = arr[j-1]
                arr[j-1] = temp
            }
        }
    }
    return arr
}