Skip to content

Instantly share code, notes, and snippets.

@atonamy
Created October 30, 2017 15:25
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save atonamy/6600107b478a24a380d7382f179e64a3 to your computer and use it in GitHub Desktop.
Save atonamy/6600107b478a24a380d7382f179e64a3 to your computer and use it in GitHub Desktop.
Beautiful implementation of quick sort on Kotlin
package quicksort
import java.util.Collections
fun main(args : Array<String>) {
val list = "abcdefghijklmnopqrstuvwxyz".toMutableList()
Collections.shuffle(list)
println("before sort: $list")
list.quicksort()
println("after sort: $list")
}
fun <T> MutableList<T>.swap(index1: Int, index2: Int) {
val tmp = this[index1]
this[index1] = this[index2]
this[index2] = tmp
}
fun <T: Comparable<T>> MutableList<T>.quicksort(low: Int = 0, high: Int = this.size - 1) {
if(this.isEmpty())
return
val pivot = this[low+(high - low)/2]
var i = low
var j = high
while(i <= j){
while(this[i] < pivot)
i++
while(this[j] > pivot)
j--
if(i <= j) {
this.swap(i, j)
i++
j--
}
}
if (low < j)
this.quicksort(low, j)
if (i < high)
this.quicksort(i, high)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment