Quick sort

Introduction

Pivot, Divide and Conquer, Wall and Randomized Algorithms are the four terminologies we should know when come to quick sort.

Pivot value selection

Randomly select an element from the array. Here, we are choosing the last element as a pivot.

Wall

The left side of the wall will always have values that are smaller than the pivot. The right side will always have bigger values. The index of the wall will start at the start index and keep moving on. 

Comparison

Compare the elements from wall to pivot, with the pivot value. If we found any value less than the pivot, swap the value with the wall and move the wall by one index. Once you did the comparison of all elements with the pivot, swap the pivot with the wall. Now the pivot has been placed successfully in its position.

Divide and conquer

Now if we divide the elements by the wall, we get 2 arrays. Continue the same process again as we mentioned above. No need of conquering.

Code

Look at the below code to get a better understanding,

public void doQuickSort(int[] a,int strtIdx,int lstIdx) {
 int pivotValue = a[lstIdx];
 int wall = strtIdx;
 for(int i=strtIdx;i < lstIdx;i++) {
  if(a[i] < pivotValue){
   swap(a,wall,i);
   wall++;
  }
 }
 swap(a,wall,lstIdx);
 if(strtIdx < wall-1){
  doQuickSort(a, strtIdx, wall-1);   
 }
 if(wall+1 < lstIdx){
  doQuickSort(a, wall+1, lstIdx);   
 }
 System.out.println();
 for(int i=0;i < a.length;i++) {
  System.out.print(a[i]+" ");
 }
}

Complexity

The time complexity of this sorting is O(n2) in a worst-case scenario. The worst case is when your pivot value is always the smallest or largest element than the rest of the elements. Each time the list is divided into 2 equal-sized lists, so the complexity will be O(nlogn) which is the best case complexity of this algorithm.

Published By