[swift] 정렬 알고리즘 코드

개린이가 쓴 글이므로 오류가 있을 수 있음을 미리 알려드립니다 🐹 (꾸벅)
이 게시글은 이것이 코딩테스트다 를 참고하여 정리하였습니다.

✍🏻 정렬 알고리즘 비교하기

정렬 알고리즘	평균 시간 복잡도	공간 복잡도	특징
선택 정렬	$O(N^2)$	$O(N)$	아이디어가 매우 간단
삽입 정렬	$O(N^2)$	$O(N)$	데이터가 거의 정렬되어 있다면 이 방법이 가장 빠르다.
퀵 정렬	$O(NlogN)$	$O(N)$	대부분의 경우 가장 적합하다. 충분히 빠르다.
계수 정렬	$O(N+K)$	$O(N+K)$	데이터의 크기가 한정되어 있는 경우에만 사용이 가능, 매우 빠르다.

선택 정렬

func selectionSort(_ array: [Int]) -> [Int] {
  guard array.count > 1 else { return array }

  var a = array

  for x in 0 ..< a.count - 1 {

    var lowest = x
    for y in x + 1 ..< a.count {
      if a[y] < a[lowest] {
        lowest = y
      }
    }

    if x != lowest {
      a.swapAt(x, lowest)
    }
  }
  return a
}

삽입 정렬

func insertionSort(_ array: [Int]) -> [Int] {
    var sortedArray = array
    for index in 1..<sortedArray.count {
        var currentIndex = index
        while currentIndex > 0 && sortedArray[currentIndex] < sortedArray[currentIndex - 1] {
            sortedArray.swapAt(currentIndex - 1, currentIndex)
            currentIndex -= 1
        }
    }
    return sortedArray
}

퀵 정렬

func quicksort<T: Comparable>(_ a: [T]) -> [T] {
  guard a.count > 1 else { return a }

  let pivot = a[a.count/2]
  let less = a.filter { $0 < pivot }
  let equal = a.filter { $0 == pivot }
  let greater = a.filter { $0 > pivot }

  return quicksort(less) + equal + quicksort(greater)
}

계수 정렬

func countingsort(_ array:[Int]) -> [Int] {
    
    let maxElement = array.max() ?? 0
    
    var countArray = [Int](repeating: 0, count: Int(maxElement + 1))
    for element in array {
        countArray[element] += 1
    }
    
    for index in 1 ..< countArray.count {
        let sum = countArray[index] + countArray[index - 1]
        countArray[index] = sum
    }
    
    var sortedArray = [Int](repeating: 0, count: array.count)
    for index in stride(from: array.count - 1, through: 0, by: -1) {
        let element = array[index]
        countArray[element] -= 1
        sortedArray[countArray[element]] = element
    }
    
    return sortedArray
}

코드 참고