By | 27.02.2017

Java Program to perform Quick Sort

Quicksort is a divide and conquer algorithm. In a divide and conquer sorting algorithm the original data is separated into two parts “divide” which are individually sorted and “conquered” and then combined.

If the array contains only one element or zero elements than the array is sorted.

If the array contains more than one element than:

• Select an element from the array. This element is called the “pivot element”. For example select the element in the middle of the array.
• All elements which are smaller then the pivot element are placed in one array and all elements which are larger are placed in another array.
• Sort both arrays by recursively applying Quicksort to them.
• Combine the arrays.

Quicksort can be implemented to sort “in-place”. This means that the sorting takes place in the array and that no additional array needs to be created.

This is a Java Program to perform Quick Sort Algorithm.Here is the source code of the Java program to implement Quick Sort Algorithm. The program output is also shown below.

SOURCE CODE : :

```import java.util.Scanner;

public class QuickSort {

//------------------Enter data Function--------------------------------

static int [] enter_data()
{
int i,n;
Scanner sc = new Scanner(System.in);
System.out.print("Enter no. of elements u want to sort :");
n=sc.nextInt();
int a[]=new int[n];
System.out.println("Enter elements--->");

for(i=0;i<n;i++)
{
System.out.print((i+1)+" Element : ");
a[i]=sc.nextInt();
}
return a;
}

//----------------------QuickSort-----------------------------

static void quicksort(int a[],int p,int r)
{
if(p<r)
{
int q;
q=partition(a,p,r);
quicksort(a,p,q);
quicksort(a,q+1,r);

}

}

//---------------Partition---------------------------------------

static int partition(int a[],int p,int r)
{
int i, j, pivot, temp;
pivot = a[p];
i = p;
j = r;
while(true)
{
while(a[i] < pivot && a[i] != pivot)
{
i++;
}

while((a[j] > pivot) && (a[j] != pivot))
{

j--;
}

if(i < j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
else
{
return j;
}
}
}

//-----------------Print array---------------------------------------

static void printarray(int arr[])
{
int i,len;
len=arr.length;
System.out.println("\nAfter Sorting Elements are : ");
for(i=0;i<len;i++)
{
System.out.println((i+1)+" Element : "+arr[i]);
}
}

//-----------------------Main Function-------------------------------

public static void main(String[] args) {

int a[],b[],p=0,r;

a=enter_data();
r=a.length;
quicksort(a,p,r-1);
printarray(a);

}

}```

OUTPUT : :

```Enter no. of elements u want to sort :7

Enter elements--->

1 Element : 5
2 Element : 1
3 Element : 9
4 Element : 3
5 Element : 4
6 Element : 0
7 Element : 8

After Sorting Elements are :

1 Element : 0
2 Element : 1
3 Element : 3
4 Element : 4
5 Element : 5
6 Element : 8
7 Element : 9```