Quick Sort in Java

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

/*
QuickSort:
This sort can be done in different ways ..........
I have taken Pivot as middle element.
you can take any element as Pivot.
*/
public class QuickSortEx
{
   public static void main(String a[])
   {
      //Numbers which are to be sorted
      int n[] = {234,213,43,12,3,177,25,2,1,67};
      //Displays the numbers before sorting
      System.out.print("Before sorting, numbers are ");
      for(int i = 0; i < n.length; i++)
       {
         System.out.print(n[i]+" ");
       }
      System.out.println();
      //Sorting in ascending order using quick sort
      initializequickSort(n,0,n.length-1);
      //Displaying the numbers after sorting
      System.out.print("After sorting, numbers are ");
      for(int i = 0; i < n.length; i++)
       {
         System.out.print(n[i]+" ");
       }
   }
   //This method sorts the input array in asecnding order
   public static void initializequickSort(int a[],int low, int len)
   {
      if(low>=len) return; // checking the length of array is Zero.
      int l=low,s=len; //initialization
      int piv=a[(l+s/2]; //selecting pivot(as middle in this example)
      while(l<s)
      { /**
         moving upto less than pivot value from start.
         */
         while(l<s && a[l]<piv)
         l++;
         /**
         moving upto greater than pivot value from end.
         */
         while(l<s && a[s]>piv)
         s--;
         /**
         swap in order to move least elements to left and maximum to right
         of the pivot.
         */
         if(l<s)
          {
            int tem = a[l];
            a[l]=a[s];
            a[s]=tem;
          }
      }
      if(s<l)// checking start and end index(start must be less than end otherwise swap)
      {
         int t = l;l=s;s=t;
      }
      initializequickSort(a,low,l);// sort left part of the array.
      initializequickSort(a,l==low?l+1:l,len); //sorting right part of the array
   }
}

Output