ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 정렬
    알고리즘/이론 2021. 2. 11. 17:22

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

    댓글

Designed by Tistory.