Algorithm - 버블 정렬 & 선택 정렬

안녕하세요, Diana 입니다.

예전엔 퇴근하고 나름 시간이 있어서 카페에 앉아서 블로그 정리를 했었는데 요즘엔 퇴근이 늦다보니 버스나 지히철 말고는 블로그를 쓸 시간이 없네요.

이동 중에 쓰고 있지만 최대한 하나하나 구현해보며 이해한 뒤 작성하고 있습니다!

 

아무튼 오늘은 버블 정렬(Bubble Sort)와 선택 정렬(Selection Sort)에 대해 알아보려고 합니다.

바로 시작할게요!

 

 

 

---

 

 

✅ 1. 버블 정렬(Bubble Sort)

버블 정렬은 간단하게 이야기 하면 인접한 두 요소를 비교 한 뒤 정렬해주는 방법입니다.

첫 번째와 두 번째, 두 번째와 세 번째 이렇게 마지막 요소까지 비교한 뒤 이를 정렬이 될 때까지 반복합니다.

 

따라서 정렬되어있지 않은 N개의 요소들이 있을 때 버블 정렬의 시간 복잡도는 (N - 1)(N - 1) 이므로 O(N^2) 이 됩니다.

 

버블 정렬을 Swift 로 구현하면 아래와 같습니다.

 

func bubbleSort(input: [Int]) {
    var array = input
    for _ in 0 ..< array.count - 1 {
        for i in 0 ..< array.count - 1 {
            if array[i] > array[i + 1] {
                let temp = array[i]
                array[i] = array[i + 1]
                array[i + 1] = temp
            }
        }
    }
    print(array)
}

 

✅ 2. 선택 정렬(Selection Sort)

선택 정렬은 전체 값 중 가장 작은 값을 찾은 뒤 해당 값을 맨 첫번째에 배치하고, 이후에는 첫번째 값을 제외하고 해당 비교를 반복해 정렬하는 방법입니다.

 

처음 N개의 요소를 탐색한뒤 이후 N - 1, N - 2의 탐색을 진행하므로 시간복잡도는 O(N^2)이 됩니다.

 

선택정렬을 Swift로 구현하면 아래와 같습니다.

 

func selectionSort(input: [Int]) {
    var array = input
    for i in 0 ..< array.count - 1 {
        var min = i
        for j in i + 1 ..< array.count {
            if array[j] < array[min] {
                min = j
            }
        }
        let temp = array[i]
        array[i] = array[min]
        array[min] = temp
    }
    print(array)
}

 

 

이렇게 오늘은 버블 정렬과 선택 정렬에 대해 알아보았습니다.