느린 정렬(Slow Sort)

목표: 숫자 배열을 낮은 순서부터 높은 순서로(또는 높은 순서부터 낮은 순서로) 정렬한다.

숫자 배열이 주어지면 올바른 순서로 정렬해야 한다. 삽입 정렬 알고리즘은 다음과 같이 동작한다:

n개의 숫자를 오름차순으로 정렬하는 문제를 다음과 같이 분해할 수 있다:

1. 숫자들 중 최댓값을 찾는다
2. 첫 번째 n/2 개의 요소 중 최댓값을 찾는다
3. 나머지 n/2 개의 요소 중 최댓값을 찾는다
4. 두 최댓값 중 더 큰 값을 찾는다
5. 나머지 숫자들을 정렬한다

코드

다음은 Swift로 구현한 느린 정렬(slow sort) 코드이다:

func slowSort(_ i: Int, _ j: Int, _ numberList: inout [Int]) {
    guard i < j else { return }
    let m = (i+j)/2
    slowSort(i, m, &numberList)
    slowSort(m+1, j, &numberList)
    if numberList[j] < numberList[m] {
        let temp = numberList[j]
        numberList[j] = numberList[m]
        numberList[m] = temp
    }
    slowSort(i, j-1, &numberList)
}

성능

함께 보기

인터넷 상의 Slow Sort 설명

Swift Algorithm Club을 위해 Lukas Schramm가 작성

(Insertion Sort Readme를 템플릿으로 사용함)