Merge sort Recursive
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647
object Main extends App {
def quickSort (array: Array[Int], left: Int = 0, right: Int): Array[Int] = {
if(left >= right) array
val pivot = right
val pivotPosition = partition(array, pivot, left, right)
//sort left and right
quickSort1(array, left, pivotPosition - 1)
quickSort1(array, pivotPosition + 1, right)
}
def quickSort1(array: Array[Int], left:Int, right:Int): Array[Int] = {
if(left < right) {
val pivot = right
val partitionIndex = partition(array, pivot, left, right)
//sort left and right
quickSort1(array, left, partitionIndex - 1)
quickSort1(array, partitionIndex + 1, right)
}
array
}
private def partition(array: Array[Int], pivot: Int, left: Int, right: Int):Int = {
val pivotValue = array(pivot)
var partitionIndex = left
for(i <- left to right) {
if(array(i) < pivotValue){
swap(array, i, partitionIndex)
partitionIndex = partitionIndex+1
}
}
swap(array, right, partitionIndex)
partitionIndex
}
private def swap(array: Array[Int], firstIndex: Int, secondIndex: Int){
var temp = array(firstIndex)
array(firstIndex) = array(secondIndex)
array(secondIndex) = temp;
}
val numbers = Array(-1, 10, 5, 3, 3, -10, 7, -2, 20, 100, -5, 1002,-100)
println(quickSort(numbers, 0, numbers.length - 1).toList)
println(quickSort1(numbers, 0, numbers.length - 1).toList)
}
Scala
INFO