Quick Sort

• Quick Sort is also based on the concept of Divide and Conquer, just like merge sort.

• But in quick sort all the heavy lifting(major work) is done while dividing the array into subarrays, while in case of merge sort, all the real work happens during merging the subarrays. 

• It is also called partition-exchange sort.

• Pivot element can be any element from the array, it can be the first element, the last element or any random element.

Algorithm:

Step 1 − Make any element as pivot

Step 2 − Partition the array on the basis of pivot

Step 3 − Apply quick sort on left partition recursively

Step 4 − Apply quick sort on right partition recursively

Quick Sort Pivot Algorithm:

Step 1 − Choose the highest index value has pivot

Step 2 − Take two variables to point left and right of the list excluding pivot

Step 3 − left points to the low index

Step 4 − right points to the high

Step 5 − while value at left is less than pivot move right

Step 6 − while value at right is greater than pivot move left

Step 7 − if both step 5 and step 6 does not match swap left and right

Step 8 − if left ≥ right, the point where they met is new pivot

Step 1 − Choose the highest index value has pivot ie. pivot=3

    

0                  1               2                3                   4                  // Index

 7   4 5       2               3                  // Value

Step 2 − Take two variables to point left and right of the list excluding pivot

Step 3 − left points to the low index.  Low= 0 th location

Step 4 − right points to the high,  high= 3 th location

Low 0      1                2               high=3              4                  

  7   4 5       2              3 

Step 5 − while value at left is less than pivot move right .

            Is 7 less than 3 ?    no :   We can’t move low to right

Step 6 − while value at right is greater than pivot move left

Is 2 greater than 3 ?    no :   We can’t move high to left

Step 7 − if both step 5 and step 6 does not match swap left (low) and right (high)

Low= 0      1                2               high=3              4                  

  2   4 5         7             3

Step 8 − if left ≥ right, the point where they met is new pivot

  

Repeat Step 5 − while value at left is less than pivot move right

Ie. is 2 less than 3, yes: then we move left (low ) to right;  so low = 1

        0           low=1                2               high=3              4                  

      2   4 5         7             3  

Repeat Step 5 − while value at left is less than pivot move right

    Ie. is 4 less than 3, no: then we can’t move left (low ) to right; 

    Low= 0      1                2               high=3              4                  

      2   4 5         7           3  

Step 8 − if left ≥ right, the point where they met is new pivot

Repeat Step 5 − while value at left is less than pivot move right

Ie. is 2 less than 3, yes: then we move left (low ) to right;  so low = 1

    0           low=1                2               high=3              4                  

   2   4 5         7             3  

Repeat Step 5 − while value at left is less than pivot move right

Ie. is 4 less than 3, no: then we can’t move left (low ) to right; 

Step 6: while value at right is greater than pivot move left

Ie. is 7 greater than 3,  yes: then we can move right (high ) to left;

            0           low=1           high=2               3              4                  

  2   4 5         7       3  

Step 6: while value at right is greater than pivot move left

Ie. is 5 greater than 3,  yes: then we can move right (high ) to left; 

0           low=1           high=2               3              4                  

  2   4 5        7       3  

Step 6: while value at right is greater than pivot move left

Ie. is 5 greater than 3,  yes: then we can move right (high ) to left;

0        low/high=1            2               3              4                  

  2   4 5        7             3  

Step 6: while value at right is greater than pivot move left

Ie. is 4 greater than 3,  yes: then we can move right (high ) to left;

0        low/high=1            2               3              4                  

  2   4 5        7             3  

Step 8 − if left ≥ right, the point where they met is new pivot

low=0       1                     2          high= 3      pivot=4               

  2   3 5        7               4  

And so on.... we follow same steps till the condition is true

Time Complexities:

• Worst Case Complexity: O(n2))
  If we want to sort in ascending order and the array is in descending order then, the worst case occurs.

• Best Case Complexity: O(n log(n))
  It occurs when the array is already sorted

• Average Case Complexity: O(n log(n))
  It occurs when the elements of the array are in jumbled order (neither ascending nor descending)