Skip to content

Instantly share code, notes, and snippets.

@BillOTei
Last active January 23, 2023 08:08
Show Gist options
  • Save BillOTei/e28aaa895c1449888030621b9b9e8788 to your computer and use it in GitHub Desktop.
Save BillOTei/e28aaa895c1449888030621b9b9e8788 to your computer and use it in GitHub Desktop.
Quick sort algorithm in scala
object Application extends App {
def quickSort(l: Array[Int], low: Int, high: Int): Unit = {
if (low < high) {
val pivotIdx = partition(l, low, high)
quickSort(l, low, pivotIdx - 1)
quickSort(l, pivotIdx + 1, high)
}
}
def partition(arr: Array[Int], low: Int, high: Int): Int = {
// pivot
val pivot = arr(high)
// Index of smaller element and
// indicates the right position
// of pivot found so far
var i = low - 1
for (j <- low until high) {
// If current element is smaller
// than the pivot
if (arr(j) < pivot) {
// Increment index of
// smaller element
i += 1
swap(arr, i, j)
}
}
swap(arr, i + 1, high)
i + 1
}
def swap(arr: Array[Int], i: Int, j: Int): Unit = {
val temp = arr(i)
arr(i) = arr(j)
arr(j) = temp
}
val arr = Array(10, 7, 8, 9, 1, 5)
quickSort(arr, 0, arr.length - 1)
arr.foreach(println)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment