- (+91) 7 999 01 02 03
- info@onlinelearningcenter.in

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(n^{2})

best case : O(n log n)

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(n

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