|
The Quicksort and the Heapsort are two n log2 n algorithms for
sorting data. One way to more empirically measure the performance of
these two algorithms is to write a benchmarking program and count the
number of comparisons each uses in order to sort a random data set.
Another total that may be of interest is the number of swaps a given
algorithm uses in the sorting process. Below is a benchmarking
program that does just that.
/*************************************************************************
** **
** Sorting Benchmark **
** **
** Data and Algorithm Analysis **
** **
** Assignment #6 **
** **
** Due Dec 1, 1997 **
** **
** Scott Gasch **
** **
** available online at http://wannabe.guru.org/alg/alg.html **
** **
*************************************************************************/
#include <stdio.h>
#include <stdlib.h>
/*
* We need math.h for the log stuff in the table
*
*/
#include <math.h>
/*
* We need time.h in order to seed the random number generator based on the
* value of the system clock...
*
*/
#include <time.h>
/*
* This is the index number of the top item in the data set to be sorted...
*
*/
int TOPITEM = 100;
/*
* The random value generator will fill the data set with values between
* zero and RANGE, inclusive.
*
*/
int RANGE = 10000;
/*
* The array itself is global to memory and me the headache of passing it
* all around the place.
*
*/
int data[1000];
/*
* To keep track of number of swaps and comparisons each alg uses
*
*/
int num_swaps, num_comps;
/*
* Function protos
*
*/
void swap (int *a, int *b);
void q_sort (int low, int hi);
void show_array(void);
void fill_array(void);
int get_pivot (int low, int hi);
void pushdown(int which, int limit);
void heapify(int low, int hi);
void h_sort(int low, int hi);
/* ------------------------------------------------------------------------- */
/* show_array - dump the contents of the data set to stdout
*/
void show_array(void) {
int i;
for (i = 1; i < TOPITEM; i++) {
printf("%d: %d\n", i, data[i]);
}
}
/* ------------------------------------------------------------------------- */
/* fill_array - place random numbers between
* 0..RANGE (inclusive) in data[]
*/
void fill_array(void) {
int i;
float r;
/* clean slate */
num_comps = num_swaps = 0;
/* [re]randomize */
srand(time(NULL));
for (i = 1; i < TOPITEM; i++) {
r = (float) rand() / (float) RAND_MAX;
data[i] = r * RANGE + 1;
}
}
/* ------------------------------------------------------------------------- */
/* get_pivot - return the index of the selected pivot value
*/
int get_pivot (int low, int hi) {
/* safety net, this should not happen */
if (low == hi) return(data[low]);
/* return the greater of the first two items in the range
*
* return( (data[low] > data[low+1]) ? low : (low+1) );
*
*/
/* return the midpoint as the pivot element */
return( (low + hi) / 2 );
}
/* ------------------------------------------------------------------------- */
/* swap - given two pointers to integers, swap their contents
*/
void swap (int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
num_swaps++;
}
/* ------------------------------------------------------------------------- */
/* q_sort - Quicksort a data range
*/
void q_sort (int low, int hi) {
int pivot_index; /* index in the data set of the pivot */
int pivot_value; /* the value of the pivot element */
int left, right;
/* select the pivot element and remember its value */
pivot_index = get_pivot(low, hi);
pivot_value = data[pivot_index];
/* do the partitioning */
left = low; right = hi;
do {
/* move left to the right bypassing elements already on the correct side */
while ((left <= hi) && (data[left] < pivot_value)) {
num_comps++;
left++;
}
num_comps++;
/* move right to the left bypassing elements already on the correct side */
while ((right >= low) && (pivot_value < data[right])) {
num_comps++;
right--;
}
num_comps++;
/*
* if the pointers are in the correct order then they are pointing to two
* items that are on the wrong side of the pivot value, swap them...
*/
if (left <= right) {
swap(&data[left], &data[right]);
left++;
right--;
}
} while (left <= right);
/* now recurse on both partitions as long as they are large enough */
if (low < right) q_sort(low, right);
if (left < hi) q_sort(left, hi);
}
/* ------------------------------------------------------------------------- */
/* pushdown - push a data item down the heap until in the proper place
*/
void pushdown(int which, int limit) {
/* we will determine the node's max child */
int max_child = which * 2;
/* if this is a leaf node (i.e. it has no children) then we're done */
if (max_child > limit) return;
/* if it has a second child, make max_child the index of the greater kid */
if (((which * 2) + 1) <= limit) {
num_comps++;
if (data[max_child] < data[(which * 2) + 1]) max_child = (which * 2) + 1;
}
/* now see if the node in question if greater than its max child... */
num_comps++;
if (data[which] < data[max_child]) {
/* if it's not, swap them and keep going with the push down */
swap (&data[which], &data[max_child]);
pushdown(max_child, limit);
}
}
/* ------------------------------------------------------------------------- */
/* heapify - given a data range, make it into a heap
*/
void heapify(int low, int hi) {
/* we only have to start at the first node with children */
int mid = (low + hi) / 2;
int i;
/* work backwards to the top of the heap calling pushdown */
for (i = mid; i > 0; i--) pushdown(i, TOPITEM-1);
}
/* ------------------------------------------------------------------------- */
/* h_sort - perform a heap sort on a range of data items
*/
void h_sort(int low, int hi) {
int i;
/* heapify the data set */
heapify(low, hi);
/* repeatedly swap top and last then pushdown the promoted last */
for (i = TOPITEM - 1; i > 1; i--) {
swap(&data[1], &data[i]);
pushdown(1, i - 1);
}
}
/* ------------------------------------------------------------------------- */
/* main - the driver
*/
int main(void) {
int save_array[1000]; /* used to store/reset the global array */
int tab[6][4]; /* tabular values for #comps, #swaps */
int i, j; /* loop control */
int n;
/*
* requirements:
*
* 1) see above
*
* 2) Check your code works by comparing to answers for hw 4, #2
*
*/
init_data();
q_sort(1, 10);
printf("homework data, quicksort:"
"%d comparisons, %d swaps\n", num_comps, num_swaps);
hwdata();
h_sort(1, 10);
printf("homework data, heapsort:"
"%d comparisons, %d swaps\n", num_comps, num_swaps);
/*
*
* (footnote: my version of quicksort works better)
*
*
* 3) Use a random number generator to generate ints from 1 to 10000
* (see fill_array())
*
* 4) Take 100 random numbers and demonstrate your code works...
*
*/
TOPITEM=101; RANGE=10000;
printf("creating an array of 100 random numbers... here it is:\n");
fill_array();
show_array();
/* save this untarnished list so heapsort can sort later */
for (i = 0; i<1000; i++) save_array[i] = data[i];
/* run a qsort and show the nice people */
printf("quick sorting...\n");
q_sort(1, TOPITEM-1);
show_array();
/* restore the list to its unsorted splendor */
for (i = 0; i<1000; i++) data[i] = save_array[i];
/* heap sort */
printf("heap sorting...\n");
h_sort(1, TOPITEM);
show_array();
/*
*
* 5) Take N random numbers (500<N<1000 by 100 steps) and make a
* nice table.
*
*/
for (i = 500; i<=1000; i+=100) {
TOPITEM = i+1;
num_swaps = num_comps = 0;
fill_array();
/* store data set */
for (j = 0; j<1000; j++) save_array[j] = data[j];
/* quicksort */
q_sort(1, TOPITEM);
/* save the results */
tab[(i - 500) / 100][0] = num_comps;
tab[(i - 500) / 100][1] = num_swaps;
/* get ready to heapsort */
num_swaps = num_comps = 0;
/* restore the data set and doit */
for (j = 0; j<1000; j++) data[j] = save_array[j];
h_sort(1, TOPITEM);
/* save results */
tab[(i - 500) / 100][2] = num_comps;
tab[(i - 500) / 100][3] = num_swaps;
}
/* now show them the table */
printf(" Quicksort Heapsort\n"
" N NlogN #comps #swaps #comps #swaps\n"
"-------------------------------------------------------\n");
for (i = 0; i<6; i++) {
n = (i * 100) + 500;
printf(" %4d %4d %5d %5d %5d %5d\n",
n,
n * (int)(log(n) / log(2)),
tab[i][0],
tab[i][1],
tab[i][2],
tab[i][3]);
}
}
|
Search