Quick sort

Introduction

Pivot , Divide and Conquer , Wall , Randomized algorithm 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:

Left side of the wall will always have the values that's smaller than pivot. 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 wall and move the wall by one index. Once you did the comparison of all elements with pivot, swap the pivot with wall. Now the pivot has 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.

Look at the below code to get the better understanding,

Code:

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(n²) in a worst case scenario. The worst case is when your pivot value is always the smallest or largest element than rest of the elements. Each time if the list is divided into 2 equal sized list, then the complexity will be O(nlogn) which is the best case complexity of this algorithm.