Quick Sort

import java.util.Scanner;
public class QuickSort
{

public static void main()
{
Scanner in=new Scanner(System.in);
int a[]=new int[10];
System.out.println(“QUICK SORT PROGRAM”);
System.out.println(“Enter 10 nos…”);

for(int i=0;i<10;i++)
a[i]=in.nextInt();

quickSort(a, 0, a.length-1);
System.out.println(“The sorted Array is…”);
for(int i=0;i<10;i++)
System.out.println(a[i]);
}

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

private static int partition(int[] a, int p, int r)
{

int x = a[p];
int i = p-1 ;
int j = r+1 ;

while (true)
{
i++;
while ( i< r && a[i] < x)
i++;
j–;
while (j>p && a[j] > x)
j–;

if (i < j)
swap(a, i, j);
else
return j;
}
}

private static void swap(int a[], int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s