Kotlin-Algorithms-and-Design-Patterns/src/main/kotlin/sorting/QuickSort.kt at master · ajaycode/Kotlin-Algorithms-and-Design-Patterns · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package sorting

import kotlin.random.Random

/**
 * quicksort algorithm
 *
 * worst time: n²
 * the best time: n * log(n)
 * average time: n * log(n)
 *
 * amount of memory: n
 */


fun <T : Comparable<T>> Array<T>.quickSort(start: Int = 0, end: Int = size - 1) {
    val array = this

    if (array.isEmpty()) return
    if (start >= end) return

    val pivotIndex = Random.nextInt(start, end + 1)
    val pivot = array[pivotIndex]

    var i = start
    var j = end

    while (i <= j) {
        while (array[i] < pivot) {
            i++
        }
        while (array[j] > pivot) {
            j--
        }
        if (i <= j) {
            array[i] = array[j].apply {
                array[j] = array[i]
            }
            i++
            j--
        }
    }

    if (i < end) quickSort(i, end)
    if (0 < j) quickSort(start, j)
}

fun <T : Comparable<T>> MutableList<T>.quickSort(start: Int = 0, end: Int = size - 1) {
    val list = this

    if (list.isEmpty()) return
    if (start >= end) return

    val pivotIndex = Random.nextInt(start, end + 1)
    val pivot = list[pivotIndex]

    var i = start
    var j = end

    while (i <= j) {
        while (list[i] < pivot) {
            i++
        }
        while (list[j] > pivot) {
            j--
        }
        if (i <= j) {
            list[i] = list[j].apply {
                list[j] = list[i]
            }
            i++
            j--
        }
    }

    if (i < end) quickSort(i, end)
    if (0 < j) quickSort(start, j)
}