Description:
Quicksort is a very efficient sorting algorithm invented by C.A.R.
Hoare. It has two phases:
- The partition phase and
- The sort phase.
As we will see, most of the
work is done in the partition phase. The sort phase simply sorts the two
smaller problems that are generated in the partition phase.
This makes
Quicksort a good example of the divide and conquer strategy
for solving problems. In quicksort, we divide the array of items to be sorted
into two partitions and then call the quicksort procedure recursively to sort
the two partitions, ie we divide the problem
into two smaller ones and conquer by solving the smaller
ones.
Algorithm
1.
Pick an element, called a pivot, from the
array.
2.
Partitioning: reorder the array so that all
elements with values less than the pivot come before the pivot, while all
elements with values 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.
3.
Recursively apply the above steps to
the sub-array of elements with smaller values and separately to the sub-array
of elements with greater values.
Solution:
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int partition(int a[],int low,int high)
{
int i,j,key,temp,true=1;
key=a[low];
i=low+1;
j=high;
while(true)
{
while((key>=a[i])&&(i<high))
i=i+1;
while(key<a[j])
j=j-1;
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else
true=0;
}
temp=a[low];
a[low]=a[j];
a[j]=temp;
return j;
}
void quicksort(int a[],int low,int high)
{
int pos;
if(low<high)
{
pos=partition(a,low,high);
quicksort(a,low,pos-1);
quicksort(a,pos+1,high);
}
}
void main()
{
clock_t n1,n2,n3;
double n4;
int a[2000],n,i,low,high,choice,num;
FILE *fp;
char f_name[10];
label:printf("\nEnter your choice
:\nPress 1 to read numbers from file\n
Press
2 to generate random numbers\nPress 3 to take the numbers from
keyboard\n");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("Enter the
filename:");
scanf("%s",f_name);
fp=fopen(f_name,"r");
if(fp==NULL)
{
printf("Error!! File not found");
goto
label;
}
i=0;
while(fscanf(fp,"%d",&num)!=EOF)
{
a[i]=num;
i++;
}
n=i;
break;
case 2: printf("Enter the
number of elements\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
a[i]=rand()%100;
}
break;
case 3: printf("Enter
the number of elements\n");
scanf("%d",&n);
printf("Enter
those elements \t");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
break;
default:exit(0);
}
printf("\nThe
unsorted array is:");
for(i=0;i<n;i++)
printf("\t%d",a[i]);
n1=clock();
for(i=0;i<10000;i++)
quicksort(a,0,n-1);
n2=clock();
n3=n2-n1;
n4=n3/CLOCKS_PER_SEC;
printf("\nThe sorted array
is:\n");
for(i=0;i<n;i++)
printf("\t%d",a[i]);
printf("\nTime in microseconds is
%f",n4*1000000/10000);
printf("\nCPU time is
%d",n3/10000);
}
OUTPUT 1 :
Enter your choice :
Press 1 to read numbers from file
Press 2 to generate random numbers
Press 3 to take the numbers from keyboard
1
Enter the filename:quick.txt
The unsorted array is: 23 45 65 23 12 343 54 43 0 0 0 0 0 0 0 0 0 1 1 11 1 2 2 2 2 2 2 2 33 3 3 3 3 3 3 4 4 4 4 4 4 44 4 4 4 4 4 4 5 55 5 5 5 5 5 5 5 5 5 5 5 6 6 66 6 6 6 6 6
The sorted array is:
0 0 0 0 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 2 2 33 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 55 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 12 23 23 33 43 45 54 55 65 343
Time in microseconds is 0.000000
CPU time is 0
OUTPUT 2 :
Enter your choice :
Press 1 to read numbers from file
Press 2 to generate random numbers
Press 3 to take the numbers from keyboard
2
Enter the number of elements
20
The unsorted array is:
83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36
The sorted array is:
15 21 26 26 27 35 36 40 49 59 62 63 72 77 83 86 86 90 92 93
Time in microseconds is 0.000000
CPU time is 0
OUTPUT 3 :
Enter your choice :
Press 1 to read numbers from file
Press 2 to generate random numbers
Press 3 to take the numbers from keyboard
3
Enter the number of elements
10
6 2 78 23 45 21 73 38 40 64
The unsorted array is:
6 2 78 23 45 21 73 38 40 64
The sorted array is:
2 6 21 23 38 40 45 64 73 78
Time in microseconds is 0.000000
CPU time is 0
No comments:
Post a Comment