Quick Sort in Java Example

Algorithm for Quick Sort:

Here ‘a’ is an array of elements and ‘first’ and ‘last’ represent the first index and last index of the array ‘a’ Perform the following steps only if(first<last).

step 1: Set i=first

step 2: Set j=last+l

step 3: Set k=first

step 4: Repeat through step-9 while(i<j)

step 5: Repeat through step-6 while(a[i]<a[j])

step 6: Increment the value of ‘i’ as i=i+1

step 7: Repeat through step-8 while(a[J]>a[k])

step 8: Decrement the value of ‘J’ as j=j+1

step 9: If(i<j)then exchange the value of a[i]and a[j]

step 10: Exchange the value of a[k] and a[j]

step 11: Call QuickSort(a,first,j-1)

step 12: Call QuickSort(a,j+ 1,last)

step 13: Exit

Here is the Java Example for Quick Sort:

import java.util.Scanner; 
 class QuickSort 
 { 
             static int a[]; 
             static int n; 
           public static void main(String args[]) 
       { 
             Scanner read=new Scanner(System.in); 
             System.out.print("Enter Number of Elements You Want to Insert : "); 
             n=read.nextInt(); 
             a=new int[n]; 
             for(int i=0;i<n;i++) 
                { 
                  System.out.print("\nEnter no."+(i+1)+" :"); 
                  a[i]=read.nextInt(); 
                } 
                  QuickSort ii=new QuickSort(); 
                  ii.QuickSort(a,0,n-1); 
                  System.out.print("\nAll Elements are :"); 
                  for(int i=0;i<n;i++) 
                     { 
                          System.out.print(a[i]+" "); 
                     } 
        } 
           void QuickSort(int a[],int first,int last) 
                { 
                    int i,j,k,temp; 
                    if(first<last) 
                      { 
                           i=first; 
                           j=last+1; 
                           k=first; 
                            do 
                              { 
                                do 
                                  { 
                                     i++; 
                                   }while(a[i]<a[k]); 
                                       do 
                                        { 
                                           j--; 
                                         }while(a[j]>a[k]); 
                                          if(i <j) 
                                            { 
                                              temp=a[i]; 
                                              a[i]=a[j]; 
                                              a[j]=temp; 
                                             } 
                              }while(i<j); 
                               temp=a[k]; 
                               a[k]=a[j]; 
                               a[j] =temp; 
                               QuickSort(a,first,j-1); 
                               QuickSort(a,j+1,last); 
                       } 
                } 
 }