Written by Kousik :
QUICKSORT(S)
QUICKSORT(S)
{
1. If ||S||<=1 return;
else {
2. Select a first element e as
pivot from s.
3. Compare elements of s with e to
partition S into subsets S1, S2, S3 such that
Elements of S1 are
less than e.
Elements
of S2 are equal to e.
Elements
of S3 are greater than e.
4. return (QUICKSORT(S1), followed by S2,
QUICKSORT(S3)) ;
}
Implementation of step 2 [Partitioning]
1) Select the very first element of S as pivot.(Simplest
implementation)
2) Select pivot from S at random.(Randomized implementation)
Analysis of Time complexity of this
algorithm:
Let T(n) be the time complexity of this
algorithm.
i)
Worst Case
T(n) = T(0) +
T(n-1) + n -1
= 1+ T(n-1) + n -1
= T(n-1)+n
= n(n+1)/2 = O(n2)
This is a
polynomial in time complexity. So this is a nice algorithm for solving a
sorting problem. But we use this algorithm in a better way such that the time
complexity of this algorithm reduced to O(nlogn).
ii)
Best Case:
<- n/2 elements
|
->n/2
elements
|
Time
complexity will be
T(n)=2T(n/2)+n
T(n)=O(nlogn)
iii)
Average case:
[Assumption: all elements
of S are equal probable to be
the pivot in QUICKSORT(S)]
Let ith
smallest element appear as pivot then
T(n)=n
-1+T(i-1)+T(n-i)
=cn+T(i-1)+T(n-i)
Total time
require by randomized quick sort algorithm is T(n).
T(n)=(1/n)
Assume
T(0)=T(1)=b
Then
T(n)=(1/n)
T(n)=(1/n)
= cn+(1/n)
= cn+(2/n)
= O(nlogn) [ for proof follow
this book: Design and analysis of algorithm (aho: hofcroft: ullman)]
Now it is time for writing the average
or randomized algorithm for quick sort.
Same procedure will be used in here
except the method of pivot element.
QUICKSORT(S)
{
1. If ||S||<=1 return;
else {
2. select an
element e as pivot from s in a random manner.
3. compare elements of s with e to
partition S into subsets S1, S2, S3 such that
Elements of S1 are
less than e.
Elements
of S2 are equal to e.
Elements
of S3 are greater than e.
4. return (QUICKSORT(S1), followed by S2,
QUICKSORT(S3)) ;
}
See carefully at the line 2.
Before the pivot was the very first
element but now it would be any element of s.
This is the big advantage of randomized
quick sort algorithm.
Now we have to write the C code for
randomized quick sort algorithm.
/* A program for randomized quick
sort*/
#include<stdio.h>
#include<stdlib.h>
int *a,n;
void swap(int *a1,int *a2)/* function
for swapping two element*/
{
int
k;
k=*a1;
*a1=*a2;
*a2=k;
}
int partition(int i,int j)/* function
for partition the array into three sub arrays*/
{
int x,p,v;
x=a[j];
p=i-1;
for(v=i;v<=j-1;v++)
{
if(a[v]<=x)
{
p++;
swap(a+p,a+v);
}
}
swap(&a[p+1],&a[j]);
return(p+1);
}
int rand_partition(int i,int j)/*
function to finding the random number*/
{
int q;
q=rand()%(j-i)+i;
swap(a+q,a+j);
return partition(i,j);
}
void quicksort(int i,int j)/* function
for main alogorithm QUICKSORT(S)*/
{
int b;
if(i<j)
{
b=rand_partition(i,j);
quicksort(i,b-1);
quicksort(b+1,j);
}
else
return;
}
void main()
{
int i;
printf("\n Enter the number of elements in the array: ");
scanf("%d",&n);
a=(int*)malloc(n*sizeof(int));
printf("\n Enter the elements in the array: ");
for(i=0;i<n;i++)
scanf("%d",a+i);
printf("\n The array before sorting is: ");
for(i=0;i<n;i++)
printf("%d ",a[i]);
quicksort(0,n-1);
printf("\n");
printf("\n The array after sorting is:");
for(i=0;i<n;i++)
printf(" %d",a[i]);
printf("\n");
return;
0 comments:
Post a Comment