정렬

본 글은 '이것이 취업을 위한 코딩 테스트다 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()

 

swift 정렬 라이브러리

sort()나 sorted()를 사용할 수 있으며

sort는 기존 배열을 재정렬하며, sorted는 새로운 배열의 반환값이 있다.

둘 다 시간복잡도는 O(NlogN)을 보장

내부 구현은 Timsort로 구현되어 있다.

 

Timsort란 hybrid stable sorting algorithm으로
merge sort와 insert sort가 섞여있다.

 

참고

https://velog.io/@hansangjin96/Swift-sort
https://book.naver.com/bookdb/book_detail.nhn?bid=16439154