Quicksort is a divide and conquer algorithm which relies on a partition operation: to partition an array,an element, called a pivot is choosen,all smaller elements are moved before the pivot, and all greater elements are moved after it.
This can be done efficiently in linear time and in-place. Then recursively sorting can be done for the lesser and greater sublists. Efficient implementations of quicksort (with in-place partitioning) are typically unstable sorts and somewhat complex, but are among the fastest sorting algorithms in practice. Together with its modest O(log n) space usage, this makes quicksort one of the most popular sorting algorithms, available in many standard libraries.
The most complex issue in quicksort is choosing a good pivot element; consistently poor choices of pivots can result in drastically slower (O(n2)) performance, but if at each step we choose the median as the pivot then it works in O(n log n).
Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists. Pick an element, called a pivot, from the list. Reorder the list so that all elements which are less than pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
Pseudocode For partition(a, left, right, pivotIndex)
pivotValue := a[pivotIndex]
swap(a[pivotIndex], a[right]) // Move pivot to end
storeIndex := left
for i from left to right-1
if a[i] ≤ pivotValue
swap(a[storeIndex], a[i])
storeIndex := storeIndex + 1
swap(a[right], a[storeIndex]) // Move pivot to its final place
return storeIndex
Pseudocode For quicksort(a, left, right)
if right > left
select a pivot value a[pivotIndex]
pivotNewIndex := partition(a, left, right, pivotIndex)
quicksort(a, left, pivotNewIndex-1)
quicksort(a, pivotNewIndex+1, right)
ANALYSIS
The partition routine examines every item in the array at most once, so complexity is clearly O(n).Usually, the partition routine will divide the problem into two roughly equal sized partitions. We know that we can divide n items in half log2n times.
#include<stdio.h>
#include<conio.h>
void quicksort(int[],int,int);
int partition(int[],int,int);
void main()
{
int i,n,a[20],ch=1;
clrscr();
while(ch)
{
printf("\n enter the number of elements\n");
scanf("%d",&n);
printf("\n enter the array elements\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quicksort(a,0,n-1);
printf("\n\nthe sorted array elements are\n\n");
for(i=0;i<n;i++)
printf("\n%d",a[i]);
printf("\n\n do u wish to continue (0/1)\n");
scanf("%d",&ch);
}
getch();
}
void quicksort(int a[],int low,int high)
{
int mid;
if(low<high)
{
mid=partition(a,low,high);
quicksort(a,low,mid-1);
quicksort(a,mid+1,high);
}
}
int partition(int a[],int low,int high)
{
int key,i,j,temp,k;
key=a[low];
i=low+1;
j=high;
while(i<=j)
{
while(i<=high && key>=a[i])
i=i+1;
while(key<a[j])
j=j-1;
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else
{
k=a[j];
a[j]=a[low];
a[low]=k;
}
}
return j;
}
OUTPUT enter the number of elements 5 enter the elements to be sorted 8 5 2 4 1 the sorted list of elements are: 1 2 4 5 8 time taken:0.824176