Skip to content

Latest commit

 

History

History
416 lines (341 loc) · 24.4 KB

정렬.md

File metadata and controls

416 lines (341 loc) · 24.4 KB
Raw

널리 사용되는 정렬 알고리즘

leetcode Sort an Array 문제를 여러 정렬 구현으로 풀어보자.
이 문제는 O(nlog(n)) 시간복잡도를 지켜야하므로 어떤 정렬이 통과하고 실패하는지 확인할 수 있다.

class Solution {
    fun sortArray(nums: IntArray): IntArray {
//        selectionSort(nums)                       // Time Limit Exceeded
//        insertionSort(nums)                       // Runtime 2900 ms
//        shellSort(nums)                           // Runtime 662 ms
//        aux = IntArray(nums.size)
//        topDownMergeSort(nums, 0, nums.size - 1)  // Runtime 646ms
//        bottomUpMergeSort(nums)                   // Runtime 693ms
//        quickSort(nums, 0, nums.size - 1)         // Runtime 2055ms , shuffle을 수행한다면 700ms 이내
//        threeWayQuickSort(nums, 0, nums.size - 1) // Runtime 2088ms , shuffle을 수행한다면 700ms 이내 , shuffle을 수행하지 않고 정렬된 케이스를 구분해서 정렬을 하면 1300ms
        nums.sort()                                 // Runtime 626ms
        return nums;
    }
    
    private fun IntArray.exchange(index1: Int, index2: Int) {
        val tmp = this[index1]
        this[index1] = this[index2]
        this[index2] = tmp
    }
}

✋ TimSort에 대해 - NaverD2

  • joshuajangblog.wordpress.com
  • O(1) – 상수 시간 : 알고리즘이 문제를 해결하는데 오직 한 단계만 거칩니다.
  • O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듭니다.
  • O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가집니다.
  • O(n2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱입니다.
  • O(Cn) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱입니다. (상당히 큰수가 됩니다)

버블 정렬 (Bubble Sort) - 평균 및 최악 실행 시간 : O(n2) , 메모리 : O(1)

  • 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘
  1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환합니다.
  2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외됩니다.
  • 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어납니다.

  • 장점
    • 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.. ➜ 제자리 정렬(in-place sorting)
    • 안정 정렬(Stable Sort)
  • 단점
    • 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적입니다.
    • 정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 됩니다.

선택 정렬 (Selection Sort) - 길이 N의 배열에 대해 ~N2/2번의 비교와 N번의 교환을 수행

  1. 주어진 배열 중에 최소값을 찾는다.
  2. 그 값을 맨 앞에 위치한 값과 교체한다.
  3. 인덱스를 한 칸 옮기고 나머지 배열을 같은 방법으로 교체한다.

private fun selectionSort(nums: IntArray) {
    nums.forEachIndexed {index, element ->
        var min = index
        for (innerIndex in index + 1 until nums.size) {
            if (nums[min] > nums[innerIndex]) {
                min = innerIndex
            }
        }
        nums.exchange(index, min)
    }
}
  • 특징
    • 매우 단순한 정렬 방법으로 이해하기도 쉽고 구현하기도 쉽다.
    • 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
    • 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것
    • 각 교환 작업은 각 항목을 종국적으로 위치할 자리에 두기 때문에 전체 교환 작업 횟수는 N이 된다.
    • 따라서 실행 시간이 비교 횟수에 주요하게 영향받는다고 할 수 있다.
    • 이미 정렬되어 있거나 완전히 정렬된 배열을 입력으로 주어도 무작위로 섞인 배열만큼이나 정렬에 시간이 오래 걸려 실행시간이 입력에 민갑하다
    • 선택 정렬에서 이용하는 교환 횟수는 배열의 크기에 선형으로 비례하여 데이터의 이동을 최소화한다.
  • 명제
    • 선택 정렬은 길이 N의 배열에 대해 ~N2/2번의 비교와 N번의 교환을 수행한다.

삽입 정렬 (Insertion Sort) - 평균적으로 ~N2/4번의 비교와 ~N2/4번의 교환을 수행

  1. 정렬은 2번째 위치(index)의 값을 temp에 저장합니다.
  2. temp와 이전에 있는 원소들과 비교하며 삽입해나갑니다.
  3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복합니다.

private fun insertionSort(num: IntArray) {
    for (index in 1 until num.size) {
        var innerIndex = index
        while (innerIndex > 0 && num[innerIndex] < num[innerIndex - 1]) {
            num.exchange(innerIndex, innerIndex - 1)
            innerIndex--
        }
    }
}
  • 특징
    • 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘
    • 삽입 정렬은 큰 값을 오른쪽으로 밀어내듯이 정렬하여 기준 인덱스의 값이 왼쪽 인덱스보다 값이 크다면 바로 다음 요소로 넘어가게 된다. 따라서 배열의 접근 횟수가 절반으로 줄어든다.
    • 고급 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다.
  • 명제
    • 중복 없는 키를 가진 무작위로 정렬된 크기 N의 배열에 대해 평균적으로 ~N2/4번의 비교와 ~N2/4번의 교환을 수행한다.
    • 최악 조건에서는 ~N2/2번의 비교와 ~N2/2번의 교환을 수행한다.
    • 최적 조건에서는 N-1번의 비교와 0번의 교환을 수행한다.
    • 삽입 정렬에서 발생하는 교환 작업 횟수는 배열 안에 존재하는 역순 쌍의 개수와 동일하다. 그리고 비교 작업의 횟수는 최대, 역순 쌍의 개수 + (배열 크기 - 1)만큼 발생한다.

셸 정렬 (Shell Sort)

  • 특징
    • 삽입 정렬은 인접한 항목과의 교환만 일어나 한 번에 한 위치로만 이동할 수 있기 때문에 크기가 큰 정렬되지 않은 배열을 처리하는데 느리다.
    • 셸 정렬은 삽입 정렬의 확장 버전으로 서로 멀리 떨어진 항목 간에도 교환이 일어날 수 있게 함으로써 삽입 정렬이 빠르게 처리할 수 있는 부분적으로 정렬된 배열을 만든다.
    • 매 h번째 항목들 간에 순서를 따질 때 정렬된 상태가 되도록 배열을 재정리하는 것이다. 이렇게 부분적으로 정렬된 배열을 "h-정렬 되었다" 라고 한다.
    • 각각의 h에 대해, h개의 부분 시퀀스를 대상으로 한 독립적인 삽입 정렬을 수행하는 것이다. 단 배열을 1씩 이동 순회하는 대신 h 단위로 이동 순회하도록 수정해야 한다.
private fun shellSort(num: IntArray) {
    var N = num.size
    var h = 1

    while(h < N / 3) {
        h = h * 3 + 1
    }
    while(h >= 1) {
        for (index in h until N) {
            var innerIndex = index
            while (innerIndex >= h && num[innerIndex] < num[innerIndex - h]) {
                num.exchange(innerIndex, innerIndex - h)
                innerIndex -= h
            }
        }
        h /= 3
    }
}

힙 정렬 (Heap Sort)

우선순위 큐를 사용하여 힙 정렬을 만들 수 있다.
힙 정렬은 힙 구성(heap construction) 과 정렬 취합(sortdown) 으로 나뉜다.

힙 구성

힙 구성은 원본 배열을 힙으로서 재배치하는 것이다.
N개의 항목이 주어졌을 때 N log N에 비례하는 시간 안에 작업을 완료할 수 있다.
배열을 왼쪽에서 오른쪽으로 순회하면서 swim()을 이용해 순회 중인 항목의 왼쪽편이 힙 순서를 만족하는 완전 트리인지 검사하고 복구해 나간다.

정렬 취합

정렬 취합은 힙에서 내림차순으로 항목을 꺼내어 정렬된 결과를 만드는 것이다.

병합 정렬 (Merge Sort)

  • 배열을 절반씩 나누어 각각을 정렬한 다음 이 둘을 합하여 다시 정렬 하는 방법이다.
  • 나눈 절반을 정렬할 때도 같은 알고리즘이 사용되고 , 결국에는 원소 한 개짜리 배열 두 개를 병합하게 된다.
  • 가장 큰 장점 중 하나는 크기 N인 배열을 정렬하는 시간이 NlogN에 비례한다는 것이다. 대신 N에 비례하는 추가적인 메모리 공간을 소요한다는 것이 가장 큰 단점이다.
  • 분할 (Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할
  • 정복 (Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
  • 결합 (Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.
  • 분할 정복 알고리즘의 하나

private lateinit var aux: IntArray

private fun topDownMergeSort(num: IntArray, low: Int, high: Int) {
    if (low >= high) return

    val mid = low + (high - low) / 2      // 오버플로우 예방
    topDownMergeSort(num, low, mid)       // 왼쪽 절반 정렬
    topDownMergeSort(num, mid + 1, high)  // 오른쪽 절반 정렬
    merge(num, low, mid, high)            // 670ms 병합

//    if (num[mid] > num[mid + 1]) {
//      merge(num, low, mid, high)          // 610ms 병합
//    }
}

private fun bottomUpMergeSort(num: IntArray) {
    var size = 1
    while (size <= num.size) {
        for (low in 0 .. num.size - size step(size + size)) {
            val mid = low + size - 1
            val high = Math.min(low + size + size - 1, num.size - 1)
            merge(num, low, mid, high)
        }
        size += size
    }
}

private fun merge(num: IntArray, low: Int, mid: Int, high: Int) {
    var i = low
    var j = mid + 1

    for (index in low .. high) {
        aux[index] = num[index]
    }

    for (index in low .. high) {
        if (i > mid) num[index] = aux[j++]              // i가 mid값을 넘어섰다는 말은 왼쪽 영역을 다 할당했다는 의미
        else if (j > high) num[index] = aux[i++]        // j가 high값을 넘어섰다는 말은 오른쪽 영역을 다 할당했다는 의미
        else if (aux[i] > aux[j]) num[index] = aux[j++] // 왼쪽 값이 더 크다면 오른쪽 값을 먼저 할당
        else num[index] = aux[i++]                      // 위에 해당하지 않으면 왼쪽 값을 할당
    }
}
  • 작은 부분 배열에 삽입 정렬 이용하기
    • 정렬 자체에 있어서는 삽입 정렬(또는 선택 정렬)이 더 단순하기 때문에 매우 작은 배열에 대해서는 병합 정렬보다 더 빠를 가능성이 크다.
    • 작은 부분 배열(크기가 15이하인)에 대한 정렬을 삽입 정렬로 바꾸면 보통의 병합 정렬 구현 보다 10% ~ 15%에 이르는 성능 개선 효과를 볼 수 있다. 2.2.23 참조
  • 배열이 이미 정렬된 상태인지 확인하기
    • a[mid] <= a[mid + 1]을 확인하여 merge의 호출을 생략하도록 수정하면 배열에 대한 성능을 선형으로 만들 수 있다.
    • 이 문제에 적용하면 670ms에서 610ms로 절감된다.
  • 임시 작업 배열로의 복제 제거
    • 병합용 임시 작업 배열로의 복제에 드는 시간을 제거하는 것도 가능하다.
    • 하나는 원본 배열을 입력으로 받아 정렬 결과를 임시 배열에 넣고, 다른 하나는 그 임시 배열을 입력으로 받아 정렬 결과를 원본 배열에 넣는다.
    • 이러한 접근 방법으로 재귀적인 호출이 원본 배열과 임시 배열을 번갈아가며 이용하도록 조율한다.
    • 2.2.11 참고하여 테스트 해보기

정렬의 복잡도
병합 정렬을 알아야 하는 중요한 이유 중 하나는, 정렬 작업의 본질적인 속성을 이해하는데 필요한 "계산 복잡도"를 구하는데 있어서 기반이 되는 기초 정보를 제공한다는 점이다.
정렬 알고리즘은 계산 복잡도에 직접적으로 영향을 받는다. 따라서 계산 복잡도에 대해서 상세하게 알아볼 필요가 있다.
Comparable API를 사용해야하는 제약 때문에 이 장에서 다루는 알고리즘들은 모두 비교 기반 알고리즘 클래스에 속한다. (배열 접근 비용은 무시한다.)

  1. 공간(활용)에 있어서는 병합 정렬이 최적이라고 할 수 없다.
  2. 가정한 최악 조건이 실제 응용 상황과는 다를 수도 있다.
  3. 비교 연산 외에 다른 연산(예를 들어 배열 접근과 같은)이 더 중요할 수도 있다.
  4. 비교 연산을 전혀 사용하지 않고도 정렬할 수 있는 데이터가 있을 수도 있다.

퀵 정렬 (Quick Sort)

퀵-정렬의 내부 루프(분할 메서드에 있는)는 인덱스를 증가시켜가며 어떤 고정된 값과 배열 항목의 값을 비교한다.
이러한 단순함이 퀵-정렬을 빠르게 하는 요인 중 하나이다. (이보다 더 짤은 내부 루프를 고안하기는 어렵다.)
예를 들어, 병합 정렬이나 셸-정렬이 전형적으로 더 느린 이유는 내부 루프에서 데이터 이동까지 하기 때문이다.

퀵-정렬을 빠르게 하는 두 번째 요인은 적은 수의 비교 연산을 하기 때문이다.
퀵-정렬의 효율은 종국적으로 배열을 얼마나 잘 분할 하느냐에 달려있다.
그리고 이 부분은 어떤 항목을 분할 기준 항목으로 선택하느냐에 의해 결정된다.
가장 이상적인 분할은 매 분할 단계마다 배열이 정확히 절반으로 나뉘어지는 것이다.
이렇게 되면 비교 연산 횟수가 분할 정복 재귀 동작과 같아져 CN = 2CN/2 + N을 만족하게 된다.
2CN/2 = 두 개의 부분 배열을 정렬하는 비용
N은 분할 기준 항목 또는 다른 항목을 이용해 각 배열 항목들을 검사하는 비용을 의미

  • 분할 정복(divide and conquer) 방법
    • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
    • Merge Sort와 달리 Quick Sort는 배열을 비균등하게 분할
    • 분할이 균형있게 이루어지지 않을 경우 극단적으로 비효율적이 될 수 있다. (무작위로 섞는 이유는 이러한 상황을 피하기 위해서이다.)

명제 퀵-정렬은 최악 조건에서 ~N2/2번에 이르는 비교연산을 수행한다. 하지만 입력 배열을 무작위로 뒤섞으면 이러한 경우가 발생하는 것을 방지할 수 있다.
증명 주어진 조건에 의해, 모든 분할 작업에 대해서 분할로 생성된 두 부분 배열 중 하나가 항상 공백 배열이라면, 공백이 아닌 나머지 배열들의 정렬에 수행되는 비교 연산 횟수는 다음과 같다.
N + (N - 1) + (N - 2) + ... + 2 + 1 = (N + 1) N/2
이러한 동작은 정렬 실행 시간이 제곱 시간이라는 점뿐만 아니라 재귀 호출에 필요한 메모리 공간도 선형이라는 것을 의미한다.
표준 편차가 약 .65 N 이기 때문에 N이 커질수록 평균에 가까워지는 경향이 있고 평균을 크게 벗어나는 경우가 없을 것 이다.
큰 배열에 대해서 퀵-정렬이 삽입 정렬이나 선택 정렬만큼의 비교 연산을 사용할 가능성은 정렬 와중에 컴퓨터가 번개를 맞을 확률만큼이나 적다.
퀵-정렬은 데이터의 이동이 훨씬 적기 때문에 (비록 39%나 더 많은 비교 연산을 수행함에도 불구하고) 전형적인 경우들에서는 퀵-정렬이 병합 정렬보다 더 빠르다.
이러한 수학적 분석은 확률에 기반한 결론이기는 하지만 이에 의존한다고 해서 무리가 될 것은 없다.

  1. 배열 가운데서 하나의 원소를 고릅니다. 이렇게 고른 원소를 피벗(pivot) 이라고 합니다.
  2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눕니다.
    • 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 합니다.
    • 분할을 마친 뒤에 피벗은 더 이상 움직이지 않습니다.
  3. 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복합니다.
  4. 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해진다.

  • 장점
    • 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
    • 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.. ➜ 제자리 정렬(in-place sorting)
  • 단점
    • 불안정 정렬(Unstable Sort)
    • 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
    • 배열 분할에 사용되는 원소가 중간값에 가까운 값이 되리라는 보장이 없기 때문에 , 정렬 알고리즘이 느리게 동작할 수 있다.
private fun quickSort(num: IntArray, low: Int, high: Int) {
    if (low >= high) return

    val pivot = partition(num, low, high) // 2개의 파티션
    quickSort(num, low, pivot - 1)          
    quickSort(num, pivot + 1, high)
}

private fun partition(num: IntArray, low: Int, high: Int): Int {
    var left = low
    var right = high + 1

    val pivot = num[low]
    while (true) {
        while (num[++left] < pivot) {   // pivot의 값보다 큰 원소를 찾는다
            if (left == high) break
        }
        while (pivot < num[--right]) {  // pivot의 값보다 작은 원소를 찾는다
            if (right == low) break
        }
        if (left >= right) break  // left와 right가 서로 교차할 때 멈춘다.
        num.exchange(left, right) // 위에서 찾은 큰 원소와 작은 원소를 서로 바꾼다.
    }
    // right는 pivot보다 작은 원소를 가지고 있다는게 보장되기 때문에, 끝나면 pivot 위치와 바꾼다.
    // pivot 기준 왼쪽은 모두 기준보다 작고, 기준 오른쪽은 모두 기준보다 크다.
    num.exchange(low, right)
    return right
}

private fun IntArray.shuffle() {
    for (index in 0 until this.size) {
        val r = index + Random.nextInt(this.size - index)
        val tmp = this[index]
        this[index] = this[r]
        this[r] = tmp
    }
}
  • 즉석 분할
    • 추가적인 작업용 배열을 사용하면 구현이 쉬워지긴 하지만 분할된 배열을 원본 배열에 복제해 넣는 오버헤드 비용을 상쇄할 만큼 쉬워진다고 볼 수 없다.
    • 임시 작업 메모리를 재귀 메서드 안에서 각 분할마다 매번 새로 생성하게 구현하면 정렬 수행 시간이 급격하게 늘어난다.
  • 경계선 넘지 않기
    • 만약 분할 기준 항목이 가장 작은 키 또는 가장 큰 키를 가졌다면 스캔 중에 배열의 왼쪽 또는 오른쪽 끝을 넘어가지 않도록 주의해야 한다.
  • 분할 기준 항목과 동일한 키를 가지는 배열 항목 다루기
    • 가장 좋은 방법은 좌측을 스캔할 떄는 분할 기준 항목 보다 크거나 같은 항목이 나오면 스캔을 중단하고,
    • 우측을 스캔할 때는 분할 기준 항목보다 작거나 같은 항목이 나올 때 스캔을 중단하는 것이다.
    • 비록 이러한 방식이 분할 기준 항목과 키가 같은 항목 간에 불필요한 교환을 유발하기는 하지만 특정 활용 환경에서 제곱 시간 성능으로 떨어지는 막기 위해서는 감수해야 할 오버헤드이다.
  • 무작위로 뒤섞는 작업
    • shuffle()을 진행하지 않고 정렬을 진행하면 2000ms정도 걸리지만, 무작위로 섞은 후 정렬을 진행하면 700ms이내에 정렬된다.
    • 최악 조건이 발생하는 것을 막아주고 실행 시간을 예측할 수 있게 해주기 때문이다.

삽입 정렬로의 컷오프 전환 2.3.25 풀것 📌

거의 모든 재귀 알고리즘이 그렇듯이, 다음의 두 가지 관찰을 바탕으로 단서를 찾으면 퀵-정렬의 성능을 쉽게 개선할 수 있다.

  • 작은 부분 배열에서는 퀵-정렬이 삽입 정렬보다 느리다.
  • 재귀적 동작으로 인해, 작은 부분 배열에 대해서도 반드시 퀵-정렬의 sort()가 호출된다.

따라서, 작은 부분 배열에 대해서 알고리즘을 삽입 정렬로 전환하면 성능 개선이 있을 수 있다.
cutOff는 5 ~ 15가 적절하다고 한다.

private fun quickSort(num: IntArray, low: Int, high: Int, cutOff: Int) {
    if (low >= high) return

    val subArraySize = high - low + 1;

    if (subArraySize < cutOff) {
        insertionSort(num, low, high)
        return
    }

    val pivot = partition(num, low, high)
    quickSort(num, low, pivot - 1, cutOff)
    quickSort(num, pivot + 1, high, cutOff)
}

private fun insertionSort(num: IntArray, low: Int, high: Int) {
    for (index in low .. high) {
        var innerIndex = index
        while (innerIndex > 0 && num[innerIndex] < num[innerIndex - 1]) {
            num.exchange(innerIndex, innerIndex - 1)
            innerIndex--
        }
    }
}

3-중앙값 분할

분할 기준 항목을 정할 때 작은 크기의 샘플에서 그 중앙값을 이용하는 것도 퀵-정렬의 성능을 개선할 수 있다.
조금 더 효율적으로 분할을 할 수 있긴하지만, 중앙값을 계산하는 추가 비용이 따른다.

분할 기준 항목의 키값 보다 작은 부분, 같은 부분, 큰 부분으로 나눈다.

private fun threeWayQuickSort(num: IntArray, low: Int, high: Int) {
    if (low >= high) return

    var left = low
    var index = low + 1
    var right = high
    val pivot = num[low]

    while (index <= right) {
        val compare = num[index] - pivot
        if (compare < 0) {
            num.exchange(left++, index++)
        }
        else if (compare > 0) {
            num.exchange(index, right--)
        }
        else {
            index++
        }
    }
    threeWayQuickSort(num, low, left - 1)
    threeWayQuickSort(num, right + 1, high)
}