// Code to compare execution times when quicksort and merge sort are applied to
// lists.
//
// CS 503 - Advanced Programming I
// Spring '06
#include <cassert>
#include <iostream>
#include "stopwatch.h"
// One of the two list-element types; the other is int.
struct point {
double x, y, z;
};
inline bool
operator < (const point & a, const point & b) {
return a.x < b.x;
}
// A list node.
template <typename T>
struct node {
T data;
node * next;
node() : next(0) { }
};
// Deja vu c++ style.
template <typename T> static T * mergesort(T *);
static node<int> * make_random_int(unsigned n);
static node<point> * make_random_point(unsigned n);
template <typename T> static T * quicksort(T *, int);
template <typename T> static void run_sort(T);
template <typename T> static void split(T * l, T *, T *);
template <typename T>
static T *
copy(T * l) {
// Return a copy of the given list.
T lst, * end = &lst;
while (l) {
end = end->next = new T;
end->data = l->data;
l = l->next;
}
return lst.next;
}
static int *
iota(unsigned n) {
// Return an array containing a permutation of the integers 0..n-1. The
// returned array should be freed by the caller.
int * a = new int [n];
unsigned i;
for (i = 0; i < n; i++)
a[i] = i;
std::random_shuffle(a, a + n);
return a;
}
template <typename T>
static bool
less(T * a, T * b) {
// Return true iff the first value pointed at is less than the second value
// pointed at.
return a->data < b->data;
}
int
main(int argc, char * argv[]) {
srandom(getpid());
if (2 == argc)
for (unsigned i = 10000; i <= 100000; i += 10000)
run_sort(make_random_int(i));
else
for (unsigned i = 10000; i <= 100000; i += 10000)
run_sort(make_random_point(i));
}
template <typename T>
static T *
make_list(unsigned n) {
// Make a list with the given number of elements.
T l, * next = &l;
while (n-- > 0) {
next->next = new T;
next = next->next;
}
return l.next;
}
static node<int> *
make_random_int(unsigned n) {
// Make an int-list with the given number of elements.
node<int>
* l = make_list<node<int> >(n),
* l2 = l;
int * vals = iota(n);
while (n-- > 0) {
l2->data = vals[n - 1];
l2 = l2->next;
}
delete [] vals;
return l;
}
static node<point> *
make_random_point(unsigned n) {
// Make an point-list with the given number of elements.
node<point>
* l = make_list<node<point> >(n),
* l2 = l;
int * vals = iota(n);
while (n-- > 0) {
l2->data.x = vals[n - 1];
l2 = l2->next;
}
delete [] vals;
return l;
}
template <typename T>
static T *
merge(T * left, T * right) {
// Merge the two given ordered list into a new ordered list; return the new
// ordered list.
T both,
* end = &both;
while (left or right)
if (left and (not right or left->data < right->data)) {
end = end->next = left;
left = left->next;
}
else {
end = end->next = right;
right = right->next;
}
return both.next;
}
template <typename T>
static void
run_sort(T l) {
// Run comparisions between mergesort and quicksort on the given list.
T i;
stopwatch sw;
T lcpy = copy(l);
sw.start();
lcpy = mergesort(lcpy);
sw.stop();
unsigned size = 0;
for (i = lcpy; i->next; i = i->next) {
assert(not (i->next->data < i->data));
size++;
}
std::cout << "merge " << size << " " << sw.elapsed() << "\n";
lcpy = copy(l);
sw.start();
lcpy = quicksort(lcpy, size);
sw.stop();
for (i = lcpy; i->next; i = i->next)
assert(not (i->next->data < i->data));
std::cout << "quick " << size << " " << sw.elapsed() << "\n";
}
template <typename T>
static T *
mergesort(T * l) {
// Place the elements in the given list in ascending order; return the
// ordered list.
if (l and l->next) {
T left, right;
split(l, &left, &right);
l = merge(mergesort(left.next), mergesort(right.next));
}
return l;
}
template <typename T>
static int
partition(T a[], int left, int right) {
// Permute the values in a[left..right-1] such that
//
// a[left..mid] <= a[mid] < a[mid + 1..right-1]
//
// and return mid.
assert(left < right);
T pivot = a[left];
int l = left + 1;
// a[0 .. left - 1] <= pivot < a[right .. N - 1]
while (l < right)
if (not less(pivot, a[l])) l++;
else if (less(pivot, a[right - 1])) right--;
else std::swap(a[l++], a[--right]);
std::swap(a[left], a[--l]);
return l;
}
template <typename T>
static T *
quicksort(T * l, int n) {
// Put the n elements in the given list in ascending order; return the
// ordered list.
if (n > 1) {
assert(l);
T ** a = new T * [n];
int i;
for (i = 0; i < n; i++) {
a[i] = l;
l = l->next;
}
assert(not l);
quicksort(a, 0, n);
for (i = 0; i < n - 1; i++)
a[i]->next = a[i + 1];
a[n - 1] = 0;
l = a[0];
delete [] a;
}
return l;
}
template <typename T>
static void
quicksort(T a[], int left, int right) {
// Put the elements a[left .. right - 1] in ascending order.
if (right > 1 + left) {
int mid = partition(a, left, right);
quicksort(a, left, mid);
quicksort(a, mid + 1, right);
}
}
template <typename T>
static void
split(T * l, T * left, T * right) {
// Split the list l in half, appending each half to the given left and right
// lists.
while (l) {
left = left->next = l;
l = l->next;
if (not l) break;
right = right->next = l;
l = l->next;
}
left->next = right->next = 0;
}
// $Log: list-sorting.cc,v $
// Revision 1.3 2006-07-16 19:25:14 rclayton
// Use random_shuffle().
//
// Revision 1.2 2006-02-28 19:23:04 rclayton
// Documentation.
//
// Revision 1.1 2006-02-20 23:35:59 rclayton
// Created.
//
syntax highlighted by Code2HTML, v. 0.9.1