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 : 2Decremented j : 5Didnot cross,So exchange i and j25 15 20 5 10 30 Incremented i : 5Decremented j : 4Crossed,So exchange pivot with j,and return j=4One sorting is over10 15 20 5 25 30 ***************current pivot 10, i=0, j=3, Incremented i : 1Decremented j : 3Didnot cross,So exchange i and j10 5 20 15 25 30 Incremented i : 2Decremented j : 1Crossed,So exchange pivot with j,and return j=1One sorting is over5 10 20 15 25 30 ***************current pivot 20, i=2, j=3, Incremented i : 4Decremented j : 3Crossed,So exchange pivot with j,and return j=3One sorting is over5 10 15 20 25 30 ***************Final sorted array::51015202530` 