Last active
January 23, 2023 08:08
-
-
Save BillOTei/e28aaa895c1449888030621b9b9e8788 to your computer and use it in GitHub Desktop.
Quick sort algorithm in scala
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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