Skip to content

Instantly share code, notes, and snippets.

@bholota
Last active September 25, 2019 19:43
Show Gist options
  • Save bholota/d2d1b28ed93ef32e3536109dbb1f6b20 to your computer and use it in GitHub Desktop.
Save bholota/d2d1b28ed93ef32e3536109dbb1f6b20 to your computer and use it in GitHub Desktop.
fun Array<Int>.quickSort() {
quickSortImpl(this, 0, this.lastIndex)
}
fun quickSortImpl(input: Array<Int>, leftIndex: Int, rightIndex: Int) {
if (input.size <= 1) return
val pivotIndex = (leftIndex + rightIndex) / 2
val pivotValue = input[pivotIndex]
input[pivotIndex] = input[rightIndex]
var j = leftIndex
var i = leftIndex
while (i < rightIndex) {
if (input[i] < pivotValue) { // here we can swap < with > to change asc/desc
val temp = input[i]
input[i] = input[j]
input[j] = temp
j++
}
i++
}
input[rightIndex] = input[j]
input[j] = pivotValue
if (j - 1 > leftIndex) quickSortImpl(input, leftIndex, j - 1)
if (j + 1 < rightIndex) quickSortImpl(input, j + 1, rightIndex)
}
@Test
fun testQuicksort() {
val tab = arrayOf(2, 5, 1, 3, 4, 0, 6, 2, 5)
val tab2 = tab.clone()
tab.sort()
tab2.quickSort()
assert(tab.contentEquals(tab2))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment