Quick / Partition Sort using Java

Working :

This sorting technique works on a policy called Divide and Conquer policy.

This sorting will partition the array into two parts(left and right). This partition is done by placing a pivot element at correct(or final) place in the array.

The partition process can be explained as follows :

Consider that the partition process has to be done on an array 'a' from position 'left' to position 'right'. This partition process will place the element a[left] at such a place that all values to the left of a[left] are less than or equal to a[left] and all values to the right of a[left] are greater than a[left].

Code :


//program for Quick sort

import java.util.*;

public class Quick
{
static int partition(int a[],int left,int right)
{
int i,j,x,t;

i = left;
j = right;
x = a[left];

while(i < j)
{
while(i <= right && a[i] <= x)
i++;

while(a[j] > x)
j--;

if(i < j)
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}

//swap a[j] and a[left]

t = a[j];
a[j] = a[left];
a[left] = t;

return j;
}//end of partition

static void quicksort(int a[],int left,int right)
{
int p;

if(left < right)
{
p = partition(a,left,right);
quicksort(a, left,p-1);
quicksort(a,p+1,right);
}
}


public static void main(String args[])
{
System.out.println("Enter number of elements you wish to sort : ");
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

//declare array of n elements

int a[] = new int[n];
//scan array from 0 to n-1 locations
for(int i = 0; i <= n-1;i++)
{
System.out.print("\nEnter element " + (i+1) + " : ");
a[i] = sc.nextInt();
}

System.out.println("\nOriginal array : ");

for(int i=0;i<=n-1;i++)
System.out.print(a[i] + " ");

//sort the array

quicksort(a,0,n-1);

//print sorted array

System.out.println("\nSorted array : ");

for(int i=0;i<=n-1;i++)
System.out.print(a[i] + " ");

}
}


Output :


Enter number of elements you wish to sort :
5

Enter element 1 : 5

Enter element 2 : 4

Enter element 3 : 1

Enter element 4 : 2

Enter element 5 : 6

Original array :
5 4 1 2 6
Sorted array :
1 2 4 5 6