Welcome to BigData School that can get you hired on Small startups or big Product based companies.Are you tired of 30-40 hours of theoritical bigdata courses in the market. Welcome to 240+ hours of Bigdata training. Just subscribe to our popup to get access to our 80+hours of course absolutely free.Try them out and you can join our further course once you are happy with our Demos.

Quick Sort

Big Data    On Thursday 22nd of June 2017 12:10:06 PM By Suraz Ghimire
The quick sort is divide and conquer algorithm where you will have pivot,high,low.
Any element can be chosen as pivot. I would prefer choosing the 1st element.
low will be the first element and high will be the last element in observation.

We will also have 2 variables i and j where i=low and j=high.
The job of the i is to find out element larger than the pivot, similarly the job of j is to find out element smaller than pivot.
Once you find the larger and smaller elements than pivot, check if i and j has crossed the path.
If not, exchange the value of i and j.
If yes, then exchange the pivot with j, and return j.
This will further divide the problem and solve it recursively.

Complexity:
Worst case: O(n2)
best case : O(n log n)

object QuickSort {

def main(args: Array[String]): Unit = {
val arr=Array(25,15,30,5,10,20 )
sort(arr,0,arr.length-1)
println("Final sorted array::")
arr.foreach(println)

}

def partition(arr: Array[Int], low: Int, high: Int):Int = {
val pivot=arr(low)
var i=low
var j=high

println(s"current pivot $pivot, i=$i, j=$j, ")
while(i<j && j>=0) {
while (arr(i) <= pivot) {
i = i + 1
}

while (j >= 0 && arr(j) > pivot) {
j = j - 1
}
println(s"Incremented i : $i")
println(s"Decremented j : $j")

if (i < j) {
println("Didnot cross,So exchange i and j")
val temp = arr(j)
arr(j) = arr(i)
arr(i) = temp

arr.foreach(num => print(num + " "))
println
}else{
println(s"Crossed,So exchange pivot with j,and return j=$j")
val temp = arr(j)
arr(j) = pivot
arr(low) = temp
println(s"One sorting is over")
arr.foreach(num => print(num + " "))
println("\n***************")

return j
}
}
//}
return j
}

def sort(arr:Array[Int], low:Int, high:Int):Unit= {
if (low < high) {
val p = partition(arr, low, high)
sort(arr, low, p - 1)
sort(arr, p + 1, high)
}
}
}

Output:

current pivot 25, i=0, j=5,
Incremented i : 2
Decremented j : 5
Didnot cross,So exchange i and j
25 15 20 5 10 30
Incremented i : 5
Decremented j : 4
Crossed,So exchange pivot with j,and return j=4
One sorting is over
10 15 20 5 25 30
***************
current pivot 10, i=0, j=3,
Incremented i : 1
Decremented j : 3
Didnot cross,So exchange i and j
10 5 20 15 25 30
Incremented i : 2
Decremented j : 1
Crossed,So exchange pivot with j,and return j=1
One sorting is over
5 10 20 15 25 30
***************
current pivot 20, i=2, j=3,
Incremented i : 4
Decremented j : 3
Crossed,So exchange pivot with j,and return j=3
One sorting is over
5 10 15 20 25 30
***************
Final sorted array::
5
10
15
20
25
30

About Author

Suraz Ghimire