Question

Implement quicksort and bucket sort. Use the code in your book to help; the partition in quicksort is tricky. Make sure your implementations are correct — it is easy to gain some confidence in the correctness of your code by writing a program which creates arrays filled with random numbers, sorts them, and then checks that they are sorted.

Then time your code (using clock() or similar methods) on both methods for arrays filled with random integers of the following sizes (where n is the number of elements to be sorted, and m is the maximum integer value of the items in the input array):

1) n is very large,

2)m is very small n is very small, m is very large

3)Find values of n and m where both implementations take (approximately) equal time.

Discuss where quicksort performs best, and where bucket sort performs best.

A clock time of 0 isn't very meaningful. When timing your code, try doing the same thing many times (like 100 times or more) to get more accurate results. Show both your code and your results. Experiment with the values of m and n and with your code to get reasonable, interesting, reportable results.

Note that the quicksort code in the book is incorrect if you remove the dependence on insertionSort. If you include insertion sort, the code is correct. If you want to eliminate insertion sort, then you should do the following: surround line 27 in quicksort (the "restore pivot" step) with an if block:

if (left + 1 < right) {

/* 27 */ swap(a[i], a[right - 1]); // Restore pivot

}

Language is C++

Answer 1

Results:

n m bucket_time qucik_sort_time

100001 99001 0.001054 4.19768

10 100000 0.00027 1e-06

100000 10 9e-05 0.458895

100000 3000 0.000143 0.032271

//CODE:

#include<bits/stdc++.h>
#include<utility>
#include<time.h>
using namespace std;
void BucketSort(int A[],int size,int Buckets)
{
int bucket[Buckets]={0};
int i,j,k;
for(i=0;i<size;i++)
++bucket[A[i]];
for(i=0,j=0;j<Buckets;j++)
{
for(k=bucket[j];k>0;k--)
A[i++]=j;
}
}
void InsertionSort(int A[],int size)
{

int i,j,k;
for(i=1;i<size;i++)
{
k=A[i];
j=i;
while(A[j-1]>k && j>=1)
{
A[j]=A[j-1];
j--;
}
}
}
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}

int partition (int arr[], int low, int high)
{
int pivot = arr[high];   
int i = (low - 1);
  
for (int j = low; j <= high- 1; j++)
{
if (arr[j] <= pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
  

void quickSort(int arr[], int low, int high)
{
if (low < high)
{
  
int pi = partition(arr, low, high);
  
  
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

//-(100000*(100-loop))+1;
//-(100000*loop)+1;
int main()
{

srand(time(0));
int loop=0;
while(loop<1)
{
int m=3000;
int n=100000;
int i=0,A[n];
for(int i=0;i<n;i++)
{
A[i]=rand()%m+1;
}
clock_t BucketSortTime;
clock_t quickSortTime;
BucketSortTime = clock();
BucketSort(A,n,m);
BucketSortTime = clock()-BucketSortTime;
quickSortTime = clock();
quickSort(A, 0, n-1);
quickSortTime = clock()-quickSortTime;
cout<<n<<" "<<m<<" "<<(float)BucketSortTime/CLOCKS_PER_SEC<<" "
<<(float)quickSortTime/CLOCKS_PER_SEC<<endl;
loop++;
}
}