DESCRIPTION
Quick sort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959 (published 1962), it is still a very commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heap sortQuick sort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. In efficient implementations it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quick sort can operate in-place on an array, requiring small addit
ional amounts of memory to perform the sorting.
Mathematical analysis of quick sort shows that, on average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare
PROGRAM
package blog;
import java.util.Scanner;
public class QSR {
public static int n;
public static void main(String[] args) {
int[] a;
a=new int[20];
int i;
Scanner in= new Scanner(System.in);
System.out.println("Enter the size of array:");
n=in.nextInt();
System.out.print("Enter the elements to be sorted:");
for(i=1;i<=n;i++)
a[i]=in.nextInt();
quicksort(a,1,n);
System.out.print("The sorted array is:");
for(i=1;i<=n;i++)
System.out.printf("%d ",a[i]);
}
static int partition(int a[],int l,int u)
{
int i,j,temp,flag,p;
i=l;
j=u+1;
p=a[l];
flag=1;
while(flag==1&&j>1)
{
i=i+1;
while(a[i]<p&&i<=n)
{
i++;
}
j=j-1;
while(a[j]>p&&j>1)
{
j--;
}
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else
flag=0;
}
a[l]=a[j];
a[j]=p;
return j;
}
static void quicksort(int a[],int l,int u)
{
int i,s;
for(i=1;i<=n;i++)
if(l<u)
{
s=partition(a,l,u);
quicksort(a,l,s-1);
quicksort(a,s+1,u);
}
}}
OUTPUT
enter the limit of the array:5
enter the elements : 8
76
9
12
4
the sorted elements are 4 8 9 12 76
12
4
the sorted elements are 4 8 9 12 76
No comments:
Post a Comment