Quick Sort in Java

In today's article, we discuss Quick Sort in Java. Quick sort is based on a divide-and-conquer strategy as is the merge sort.

Introduction

 
In today's article, we discuss the Quick Sort in Java.
 

Quick Sort

 
Quicksort is based on a divide-and-conquer strategy as is the merge sort.  It starts by picking one item in the entire list to serve as a pivot element. It then reorders the list so that all elements with values less than the pivot come left of the pivot, and all elements with values greater than the pivot come after it (a process often called "partitioning"). It then picks a pivot for the left side and moves those items to the left and right of the pivot and continues the pivot picking and dividing until there is only one item left in the group. It then sorts the sub-lists to the left and the right of the pivot using the same strategy, continuing this process recursively until the entire list is sorted. There are many variants for picking the pivot, partitioning the list, and halting the recursion. Quicksort is a comparison sort and, inefficient implementations is not a stable sort.
 
Basic Features
  1. One of the fastest sorting algorithms
  2. Similar to mergesort, a divide-and-conquer recursive algorithm
  3. Average running time is O(NlogN)
  4. Worst-case running time is O(N2)
Algorithm (QuickSort)
 
STEP 1. Choosing the pivot 
Choosing the pivot is an essential step. 
Choosing a good pivot causes the algorithm to run fast, or in quadric time:
  1. Choosing randomly: still a bad choice.
  2. Choosing fixed values: e.g. the last, the first, the one in the middle 
    This is a bad choice; the pivot may turn to be the smallest or the largest element, then one of the partitions will be empty.
  3. Choosing the median of the array. The median-of-three choices: take the first, the last and the middle element. 
    Choose the median of these three elements.
Example
 
[22, 3, 44, 16, 6, 19, 1, 2, 18, 8] 
The median of [22,6,8] is 8
 
STEP 2. Partitioning
  
Partitioning is illustrated in the example above.  
1. The first action is to get the pivot out of the way then swap it with the last element
     22, 3, 44, 16, 6, 19, 1, 2, 18, 8
2. We select a larger value to go to the right and smaller value go to the left
    [22, 3, 44, 16, 6, 19, 1, 2, 18, 8] 
     ^                                     ^ 
      i                                      j
  • While i is to the left of j, we move i right, skipping all the elements less than the pivot. If an element is found greater then the pivot, i stops
  • While j is to the right of i, we move j left, skipping all the elements greater than the pivot. If an element is found less then the pivot, j stops
  • When both i and j have stopped, the elements are swapped.
  • When i and j have crossed, no swap is performed, scanning stops, and the element pointed to by i is swapped with the pivot .
3. Restore the pivot.  
    After restoring the pivot we obtain the following partitioning into three groups:  
     [ 3, 6, 1, 2, ] [ 8 ] [22, 44, 16, 19, 18]
 
STEP 3.
Recursively quicksort the left and the right parts 
the output generates: [1,2,3,6,8,16,18,19,22,44]
 
Example
  1. /*  
  2. QuickSort:  
  3. This sort can be done in different ways ..........  
  4. I have taken Pivot as middle element.  
  5. you can take any element as Pivot. 
  6. */   
  7. public class QuickSortEx  
  8. {     
  9.    public static void main(String a[])  
  10.    {  
  11.       //Numbers which are to be sorted  
  12.       int n[] = {234,213,43,12,3,177,25,2,1,67};  
  13.       //Displays the numbers before sorting  
  14.       System.out.print("Before sorting, numbers are ");  
  15.       for(int i = 0; i < n.length; i++)  
  16.        {  
  17.          System.out.print(n[i]+" ");  
  18.        }  
  19.       System.out.println();  
  20.       //Sorting in ascending order using quick sort  
  21.       initializequickSort(n,0,n.length-1);  
  22.       //Displaying the numbers after sorting  
  23.       System.out.print("After sorting, numbers are ");  
  24.       for(int i = 0; i < n.length; i++)  
  25.        {  
  26.          System.out.print(n[i]+" ");  
  27.        }  
  28.    }  
  29.    //This method sorts the input array in asecnding order  
  30.    public static void initializequickSort(int a[],int low, int len)   
  31.    {   
  32.       if(low>=len) return// checking the length of array is Zero.   
  33.       int l=low,s=len; //initialization   
  34.       int piv=a[(l+s/2]; //selecting pivot(as middle in this example)   
  35.       while(l<s)   
  36.       { /**  
  37.          moving upto less than pivot value from start.  
  38.          */   
  39.          while(l<s && a[l]<piv)   
  40.          l++;   
  41.          /**  
  42.          moving upto greater than pivot value from end.  
  43.          */   
  44.          while(l<s && a[s]>piv)   
  45.          s--;   
  46.          /**  
  47.          swap in order to move least elements to left and maximum to right  
  48.          of the pivot.  
  49.          */   
  50.          if(l<s)  
  51.           {   
  52.             int tem = a[l];   
  53.             a[l]=a[s];   
  54.             a[s]=tem;   
  55.           }   
  56.       }   
  57.       if(s<l)// checking start and end index(start must be less than end otherwise swap)   
  58.       {   
  59.          int t = l;l=s;s=t;   
  60.       }   
  61.       initializequickSort(a,low,l);// sort left part of the array.   
  62.       initializequickSort(a,l==low?l+1:l,len); //sorting right part of the array   
  63.    }   
  64. }  
Output
 
quicksort.jpg