Please help: Create a program to sort a list of integers using the in place Quic
ID: 3759816 • Letter: P
Question
Please help:
Create a program to sort a list of integers using the in place Quicksort algorithm.
---------
Test out the program on lists of size 100, 1000, 5000, 10000 and 50000 or other sizes. The program should generate the list randomly every time using the java.util.Random class.
---------
It should allow the user to choose the size and pivot method at runtime. In particular, try randomly choosing the pivot element, try choosing the median of 3 randomly chosen elements as the pivot or the book technique (median of first center and last element).
----------
Is there a noticeable difference? How much of a difference in there for different sizes.
------
Both the unsorted and sorted lists must be written to two output files named ‘sorted’ and ‘unsorted’.
Attempt to gauge the run time of your sort experimentally, print these results on the console.
Explanation / Answer
#include<iostream.h>
#include<conio.h>
int a[10],l,u,i,j;
void quick(int *,int,int);
void main()
{
clrscr();
cout <<"enter 10 elements";
for(i=0;i<10;i++)
cin >> a[i];
l=0;
u=9;
quick(a,l,u);
cout <<"sorted elements";
for(i=0;i<10;i++)
cout << a[i] << " ";
getch();
}
void quick(int a[],int l,int u)
{
int p,temp;
if(l<u)
{
p=a[l];
i=l;
j=u;
while(i<j)
{
while(a[i] <= p && i<j )
i++;
while(a[j]>p && i<=j )
j--;
if(i<=j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;}
}
temp=a[j];
a[j]=a[l];
a[l]=temp;
cout <<" ";
for(i=0;i<10;i++)
cout <<a[i]<<" ";
quick(a,l,j-1);
quick(a,j+1,u);
}
}