정렬

Alimleon·2021년 1월 4일

swift 알고리즘 정렬 코딩테스트

이코테 with Swift

목록 보기

3/5

본 글은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책을 공부하며 기록합니다.
단, iOS를 공부하고 있기 때문에 swift 언어로 코드를 바꿔보고 있습니다.

퀵 정렬(quick sort)

가장 많이 사용되는 알고리즘

데이터의 특성을 파악하기 어렵다면 퀵 정렬이 유리

기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식

피벗 사용 : 교환하기 위한 기준

평균 시간 복잡도 $O(NlogN)$

그러나 최악의 경우 (데이터가 이미 정렬이 되어 있을 경우) $O(N^2)$ 이다

일반적 퀵 정렬 코드

var array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

func quick_sort(array: inout [Int], start: Int, end: Int) {
    guard start < end else { return }
    
    let pivot = start
    var left = start + 1
    var right = end
    while left <= right {
        while left <= end && array[left] <= array[pivot] {
            left += 1
        }
        while right > start && array[right] >= array[pivot] {
            right -= 1
        }
        if left > right {
            array.swapAt(right, pivot)
        } else {
            array.swapAt(left, right)
        }
    }
    quick_sort(array: &array, start: start, end: right - 1)
    quick_sort(array: &array, start: right + 1, end: end)
}

quick_sort(array: &array, start: 0, end: array.count - 1)
print(array)

고차함수 사용 간결한 코드 (시간은 더 많이듦)

func quickSort(array: inout [Int]) -> [Int] {
    guard array.count > 1 else { return array }
    
    let pivot = array[0]
    let tail = array[1..<array.count]
    
    var leftSide = tail.filter { $0 <= pivot }
    var rightSide = tail.filter { $0 > pivot }
    
    return quickSort(array: &leftSide) + [pivot] + quickSort(array: &rightSide)
}

시간 측정

0.00001406 → 일반적 퀵 정렬
0.0008339 → 고차함수 사용했을 때

계수 정렬(count sort)

특정 조건이 부합될 때만 사용 가능

그러나 아주 빠르다 데이터 개수 N, 최댓값 K일 때 시간복잡도 $O(N+K)$

데이터의 크기 범위가 제한 되어 정수 형태로 표현 가능 할 때만 사용 가능

가장 작은 데이터와 가장 큰 데이터의 차이가 1,000,000을 넘지 않을 때 사용

→ 모든 범위의 수를 담을 수 있는 배열을 선언하기 때문

데이터가 0과 999,999와 같이 2개가 있을 때는 매우 비효율적

계수 정렬의 공간 복잡도는 $O(N+K)$

let array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

var count = Array(repeating: 0, count: array.max()! + 1)

for i in 0..<array.count {
    count[array[i]] += 1
}

for i in 0..<count.count {
    for _ in 0..<count[i] {
        print(i, terminator: " ")
    }
}
print()