Understanding Quick Sorting Algorithm With Example In Java

Quick Sorting Algorithm - 

This is the one of the most in use sorting algorithm. This sorting algorithm provides a way to each element to arrange themselves. Every element finds their own place in the list.

Each list will be partitioned into smaller lists, left list holds less elements and right part hold greater elements. This algorithm is based on divide and conquer method.


Quick sort is the faster sorting algorithm and preferable for large amount of data elements.  Average time complexity of quick sort is O(n log n) and worst case complexity is O(n2).

In quick sort we pick any element and call it as pivot.


We will find pivot sorted position in the list, again select another element as pivot and finds its sorted position, this process will be continue until we get all element's sorted positions in the list. 


Assuming we have list of 8 elements ...

STEP - 1 


In the mentioned array list - 20, 2, 8, 39, 67, 5

I am taking 20 (first element of list ) as pivot.


 pivot

 20, 2, 8, 39, 67, 5
                          

STEP - 2 


Quick sort algorithm divides list on the basis of pivot value, left part of the list will have elements that are smaller than pivot and right part will have elements that are greater than pivot and at last will get the position of pivot in the list.


Again same process (selecting pivot, arranging elements, and get pivot position) will be continue with left and right side list recursively.


Let's understand quick sort with example - 20, 2, 8, 39, 67, 5


Rule - 1  
Running two loops i and j, i will read from left and j will read from right i.e index = 5.

Rule - 2
Compare elements with pivot element <pivot element will be in left side of list and >pivot will be in right side of list.

Rule - 3  

If small element swap with pivot then i counter will be incremented by 1. 
If greater element swap with pivot element  then j counter will be decremented 
by 1. 

Rule - 4  

Do comparing until i , j and pivot index are equal at this condition we will get sorted pivot index.


Quick Sort Method -

              pivot 

Array List   - 20, 2, 8, 39, 67, 5

              i=0              j=5            



i = 0 , j = 5  ,  if (pivot < array[j] ) 20  < 5 = False



Small element is swapping with pivot i.e. i will be incremented by 1.



                              pivot 

Array List   - 5, 2, 8, 39, 67, 20

                 i=1          j=5


i = 1 , j = 5, if if (pivot >array[i] ) 20 > 2 = True



Element already sorted no swapping required. Increment i by 1.


                              pivot 

Array List   - 5, 2, 8, 39, 67, 20

                    i=2       j=5


i = 2 , j = 5  , if (pivot >array[i] )  20 > 8 = True



Element already sorted no swapping required. Increment i by 1.


                              pivot 

Array List   - 5, 2, 8, 39, 67, 20

                       i=3    j=5


i = 3 , j = 5  , if (pivot >array[i]) 20 > 39 = False



Greater element is swapping with pivot i.e. j will be decremented by 1.


                      pivot 

Array List   - 5, 2, 8, 20 67, 39

                      i=3 j=4


i = 3 , j = 4 ,  if (pivot < array[j]) 20 < 67= True



Element already sorted no swapping required. decremented j by 1


                      pivot 

Array List   - 5, 2, 8, 20 67, 39

                      i=3 

                      j=3


i = 3, j = 3 ,pivot index = 3 i.e. we got the sorted position of pivot.


Sorted List- 5, 2, 8, 20 67, 39


Now divide the list into two small parts,


left list from 0 to pivot position  - 5, 2, 8, 20 .


right list from pivot position+1 to list size. -  67, 39


will send left list and right list to the quick sort process recursively.



Let's start with left side list, i=0 is the pivot element.


              pivot   

Array List   - 5, 2, 8, 20

             i=0      j=3


i = 0, j = 3  , if (pivot < array[j] ) 5 < 20 = True


Element already sorted no swapping required, decrements  j by 1.


             pivot   

Array List   - 5, 2, 8, 20

              i=0  j=2


i = 1, j = 2  ,  if (pivot < array[j] ) 5 < 8 = False


Element already sorted no swapping required, decrements  j by 1.


             pivot   

Array List   - 5, 2, 8, 20

             i=0 j=1


i = 0, j = 1  ,  if (pivot < array[j] ) 5 < 2 = True


Small element is swapping with pivot i.e. i will be incremented by 1.


                 pivot   

Array List   - 2, 5, 8, 20

                 i=1

                 j=1


i = 1, j = 1 ,pivot index = 1 i.e. we got the sorted position of pivot.


Sorted Left Side List - 2, 5, 8, 20


Next, Right side list, i=0 is the pivot element.


             pivot   

Array List   - 67, 39

             i=0  j=1


i = 0, j = 1  ,  if (pivot < array[j] ) 67 < 39 = False


Small element is swapping with pivot i.e. i will be incremented by 1.


                  pivot

Array List   - 39, 67

                  i=0

                  j=0


i = 1, j = 1 ,pivot index = 1 i.e. we got the sorted position of pivot.


Sorted Right Side List - 39,67


Final List is  -  2, 5, 8, 20,39,67


Quick Sort Implementation In Java –



public class QuickSortingExample {


     public static int pivot = 0;


     public static int pivot_index = 0;


     public static void main(String []args) {
     

     System.out.println("Quick Sorting Algorithm Starts ...\n");


     int array[] = {20,2,8,39,67,5};


     int size = 6;

     // sending array and size

     array = quickSortingMethod (array,0,size);


     if (!isSorted(array,0, size)) {


      System.out.println("\nList is not sorted yet. " );


      System.out.println ("\nDivide List in two small parts,

      left list from 0 to pivot_index and right list from

      pivot_index+1 to array size");


      System.out.println ("\nLeft list - ");
   

      printList(array,0,pivot_index+1);
    

      System.out.println ("\nRight list - ");
     

      printList(array,pivot_index+1,size);
     

      System.out.println("\nSending left list to quickSorting

      method to be sorted");


      int previous_pivot = pivot_index;


      quickSortingMethod(array,0,pivot_index+1);


      quickSortingMethod(array,previous_pivot+1,size);

   }

     System.out.println("Congrats your list is sorted \n " );

     printList(array,0,size);


 } // end of main


public static int[] quickSortingMethod(int array[],int initial,int size){


      // Get pivot value

       pivot = array [initial];


       pivot_index = initial;


       int i =initial;
       

       int j = size-1;
       

       System.out.println("\nList is = ");
       

       printList (array,initial,size);

       
       System.out.println ("\nPivot = " +pivot);
       

       while (i != j) {
       

        int temp ;
      

       System.out.println ("\ni =" +i  + " j = "+j+"\n");
    

       if ( pivot > array [j]) {
  

         System.out.println (pivot +" > "+array [j]

           + ", swap elements\n");

           temp = array [j] ;

           array[j] = pivot;

           array[pivot_index] = temp;

           pivot_index = j;


           printList (array,initial,size);


           System.out.println ("\nSmall element is swapping with

           pivot, i will be incremented by 1. \n");

             
           i++;         

      }   

    
      else if ( pivot < array [i]) {
         

          System.out.println (pivot +" < "+array [i]

             + ", swap elements\n");
          

          temp = array [i] ;       

          array[i] = pivot;

          array[pivot_index] = temp;

          pivot_index = i;

          
          printList (array,0,size);

            
          System.out.println ("\nGreater element is swapping

          with pivot, j will be decremented by 1. \n");
         

          j--;

        

       }

         
     else {

            
          System.out.println (array [i] +" < "+pivot+"\n");


          System.out.println ("Element is already sorted."); 
        

        }
      
        if( pivot < array [j]) {


            j--;

        }
         

        if(pivot > array[i]) {
             

           i++; 

       }

       
       if ( i == j) {
          

        System.out.println ("\n i = j = pivot_index , at this point

        loop will be end because we got thepivot sorted position.");
          

        break;
        
     }
   

  } // end of while
  

    System.out.println("\nProcess completed updated list is \n " );


    printList(array,initial,size);
    

    return array;


  } // end of quickSortingMethod

    
 public static void printList (int array[],int intial,int size) {


       for (int i=intial;i<size-1;i++) {



         if (array [i] < array [i+1])



            counter ++;

        }


     if (counter == size) return true;
    

      return false;


  }// end of isSorted Method


}// end of class

No comments

Powered by Blogger.