Swift로 정렬 알고리즘 정리하기 ... 1

 

안녕하세요. 린다입니다.

오늘은 간단하게 알고리즘의 기초인 정렬 알고리즘 중

버블, 선택, 삽입, 퀵 정렬에 대해서 정리해볼게요!

 

버블 정렬

• 데이터의 인접요소끼리 비교하여 swap 연산을 수행하여 정렬하는 기법
• 루프를 돌면서 연산 수행
• 시간복잡도 O(n^2)

let array = [99, 98, 97, 96]

func bubbleSort(_ array: [Int]) -> [Int] {
    var bubbleArray = array
    let n = bubbleArray.count
    
    for i in 0..<n-1 { // 0부터 n-1-1까지
        for j in 0..<(n - i - 1) {
            if bubbleArray[j] > bubbleArray[j+1] {
                bubbleArray.swapAt(j, j+1)
//                let temp = bubbleArray[j]
//                bubbleArray[j] = bubbleArray[j+1]
//                bubbleArray[j+1] = temp
            }
        }
    }
    return bubbleArray
}

• 첫번째 루프 : n -1 (2개씩 묶어서 비교할거기 때문에 (+1) -1까지의 루프
• 두번째 루프 : n - i - 1
  → 첫번째 루프를 통해 한 숫자의 자리가 fix 되면, 그자리는 확인하지 않아도 되기 때문에 -1

 

선택 정렬

• 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap

let array = [99, 98, 97, 96]
// [12, 18, 10, 13, 15]

func selectionSort(_ array: [Int]) -> [Int] {
    var selectArray = array
    let n = selectArray.count
    
    for i in 0..<n-1 {
        var min = i // min => 숫자 자체가 아니라 인덱스
        for j in i+1..<n { // min을 제외한 숫자부터 비교 시작
            if selectArray[j] < selectArray[min] {
                min = j
            }
        }
        selectArray.swapAt(i, min)
    }
    
    return selectArray
}

• 첫번째 루프 : 배열의 전체 길이 - 1 (어차피 swap을 위해서 +1로 다음꺼랑 비교할꺼니까)
• 최솟값 : array[첫번째 루프의 시작 index]
• 두번째 루프 : 바깥루프의 +1부터(최솟값을 제외하고) 배열의 길이까지 최솟값과 비교하여 최솟값 찾기

 

삽입 정렬

• 작은 배열로 시작해서 insert하여 점점 커지는 정렬 기법
• 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식

func insertSort(_ array: [Int]) -> [Int] {
    var insertArray = array
    let n = insertArray.count
    
    for i in 1..= 0 && insertArray[j] > key) {
            // insertArray[j] > key -> 임시 최솟값과 정렬된 어레이의 비교를 통해 최솟값 찾기
            insertArray[j+1] = insertArray[j] // 만약, 최솟값이 새롭게 찾아졌다면, 해당 값을 정렬된 어레이 뒤에 배치
            j -= 1 // 정렬된 어레이 만큼 -1해야 하기 때문에 -1
        }
        
        insertArray[j+1] = key // 최솟값이 변경되었다면, j에 최솟값이기 때문에 key j+1로 이동
    }
    
    return insertArray
}

• 첫번째 루프 : 기준이 되는 첫번째 index [0]를 제외하고 1부터 시작하여 끝(n)까지
• 두번째 루프 : 첫번째 루프를 파고들어 안을 탐색해야 하기 때문에
  → i -1 인 j부터 시작해서 j -= 1 해가면서 끝까지 탐색하기

 

 

 

퀵 정렬

• 기준값을 선정하여 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복하여 정렬하는 방법

import Foundation
var array = [99, 98, 97, 96, 95]

func quickSort(_ array: inout[Int], _ left: Int, _ right: Int) {
    
    if (left < right) {
        let p = partition(&array, left, right)
        
        quickSort(&array, left, p - 1)
        quickSort(&array, p + 1, right)
    }
}

func partition(_ array: inout[Int], _ left: Int, _ right: Int) -> Int {
    let pivot = array[right]
    var i = (left - 1)
    
    for j in left..<right {
        if array[j] <= pivot {
            i += 1
            array.swapAt(i, j)
        }
    }
    
    array.swapAt(i+1, right)
    return (i + 1)
}


quickSort(&array, 0, array.count-1)
print(array)