정렬 알고리즘: 버블정렬, 선택정렬

버블정렬 🧼

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.

import Foundation

// 수의 배열
var nums = [2,5,7,8]
var index: Int = 0

func bubbleSort() {
    for i in 0..<nums.count {
        // i를 빼서 수가 커질수록 비교하는 수가 줄어들도록 한다
        for j in 0..<(nums.count-1-i) {
            // 앞에서부터 비교
            if nums[j] > nums[j+1] {
                nums.swapAt(j, j+1)
            }
        }
    }
    print("BubbleSort: ", nums)
}

bubbleSort() //BubbleSort:  [8, 7, 5, 2]

 

시간복잡도: O(n²)

stable Sort 입니다.

 

선택 정렬

'가장 작은 원소를 앞으로 보내는' 알고리즘

func selectionSort() {
    for i in 0..<list.count-1 {
    //인덱스를 저장
        var minIdx = i
        for j in i+1 ..< list.count {
            if list[minIdx] > list[j] {
                minIdx = j
            }
        }
        list.swapAt(minIdx, i)
    }
    print("SelectionSort: ",list)
}

넣을 자리는 이미 정해져 있고, 그 자리에 알맞은 원소를 선택해서 넣습니다.
시간복잡도는 O(n²)

공간복잡도도 O(n²)
Unstable Sort 입니다.

 

var minIdx = i

에서 인덱스가 고정되어 있음 확인.