dataStructuresAndAlgorithms/dev.funkymuse.datastructuresandalgorithms.sort.quickSort

Package-level declarations

Functions

fun <T : Comparable<T>> MutableList<T>.medianOfThree(low: Int, high: Int): Int

Median of three finds the pivot by taking the median of the first, middle and last element.

partitionDutchFlag

fun <T : Comparable<T>> MutableList<T>.partitionDutchFlag(low: Int, high: Int, pivotIndex: Int): Pair<Int, Int>

fun <T : Comparable<T>> MutableList<T>.partitionHoare(low: Int, high: Int): Int

partitionLomuto

fun <T : Comparable<T>> MutableList<T>.partitionLomuto(low: Int, high: Int): Int

fun <T : Comparable<T>> quickSort(list: MutableList<T>, low: Int = 0, high: Int = list.size - 1)

Inventor: Tony Hoare Worst complexity: n^2 Average complexity: nlog(n) Best complexity: nlog(n) Method: Partitioning Stable: No

quicksortDutchFlag

fun <T : Comparable<T>> MutableList<T>.quicksortDutchFlag(low: Int, high: Int)

Dutch national flag partitioning strategy helps to organize duplicate elements in a more efficient way.

fun <T : Comparable<T>> MutableList<T>.quicksortHoare(low: Int, high: Int)

Hoare’s partitioning chooses the first element as its pivot.

quicksortIterativeLomuto

fun <T : Comparable<T>> MutableList<T>.quicksortIterativeLomuto(low: Int, high: Int)

quicksortLomuto

fun <T : Comparable<T>> MutableList<T>.quicksortLomuto(low: Int, high: Int)

Lomuto’s partitioning chooses the last element as the pivot.

quickSortMedian

fun <T : Comparable<T>> MutableList<T>.quickSortMedian(low: Int, high: Int)

fun <T : Comparable<T>> List<T>.quicksortNaive(): List<T>

The naive partitioning creates a new list on every filter function; this is inefficient.