There is a sample final exam.
Thursday, November 14, 2002
They all work by comparing data items and then moving data items around based on the outcome of the comparisons. To illustrate this, here is a piece of HeapSort:
if (a[c/2] < a[c]) // if parent is smaller than child
swap (c/2, c); // trade their values
3, 2, 4, 5, 1
2, 3, 4, 5, 1
We may want to conclude that sorting cannot be done in less than O(n log n) time. This would be an overstatement because there is a subtle assumption in the above argument: that the program determines what actions to take (i.e., how to move values around) solely based on the outcome of comparisons between the input values. The lesson then is, programs that base their actions only on comparisons of the data cannot beat the O(n log n) barrier. To have a chance at sorting faster we have to avoid comparing data!
// CountingSort.
//
// The data to be sorted is in array A with
// subscripts 0..n-1. For example,
//
// A = [ 2, 0, 4, 1, 4, 2, 2, 1, 0 ]
// subscript: 0 1 2 3 4 5 6 7 8
//
// The data values range from 0 to MAX (=4).
// A second array B will hold the sorted data.
//
// Initialize a "counting array" C:
// ---------------------------------------------
for (i = 0; i <= MAX; i++)
C[i] = 0;
// ---------------------------------------------
// Count how often each value occurs in A:
// ---------------------------------------------
for (i = 0; i < n; i++)
C[A[i]]++;
// ---------------------------------------------
// At this point C[i] contains the number
// of occurrences of the value i in A. In
// the example:
//
// C = [ 2, 2, 3, 0, 2 ]
// 0 1 2 3 4
//
// Make C[i] contain the number of
// occurrences of values 0..i in A:
// ---------------------------------------------
for (i = 1; i <= MAX; i++)
C[i] += C[i-1];
// ---------------------------------------------
// In the example:
//
// C = [ 2, 4, 7, 7, 9 ]
// 0 1 2 3 4
//
// Note that now C[i] is such that in the sorted
// array, the last occurrence of value i will be
// just before position C[i] (e.g., the last 2 in
// the sorted array B will be just before position
// C[2]=7).
//
// Move values from A to B, using C to know
// where to put them:
// ---------------------------------------------
for (i = n-1; i >= 0; i--)
B[--C[A[i]]] = A[i];
// ---------------------------------------------
// Now B looks like
//
// B = [ 0, 0, 1, 1, 2, 2, 2, 4, 4 ]
// 0 1 2 3 4 5 6 7 8
//
// Not that it matters, but now C[i] contains the
// subscript of the first occurrence of value i
// in the sorted array B:
//
// C = [ 0, 2, 4, 7, 7 ]
// 0 1 2 3 4
//
// RadixSort on nonnegative int's
for (each digit d from least significant to most significant)
do CountingSort on digit d
sort sort sort
by by by
ones tens 100s
612 511 404 321
511 321 405 322
405 612 512 332
333 -----> 322 -----> 612 -----> 333
322 332 321 404
321 333 322 405
332 404 332 512
404 405 333 612
(number >> 16) & 0xFFFF
Don't do this shifting stuff with negative numbers.
BucketSort works on data whose distribution is uniform across a range of values.
// BucketSort.
//
// The data to be sorted is in array A with
// subscripts 0..n-1.
//
// The data values range from 0 to MAX.
//
// Performance hinges on the data being more or
// less uniformly distributed over that range.
//
// ---------------------------------------------
const int nBuckets = (MAX / 10) + 1;
Bucket bucket [nBuckets]; // one can insert a number into
// a bucket, one can sort a bucket
// (or else the insert function
// inserts in order already),
// and one can print a bucket
// Put each number into the proper bucket.
// E.g., the three numbers 8,735 and 8,739
// and 8,730 all go into bucket[873].
for (i = 0; i < n; i++)
bucket [A[i] / 10].insert (A[i]);
// Sort within each bucket. Hopefully the size of
// each bucket is very small, close to 10 most of the
// time in this example.
// if needed, sort (depends on the 'Bucket::insert' function)
for (i = 0; i < nBuckets; i++)
bucket [i].sort ();
// ... and print the sorted values ...
for (i = 0; i < nBuckets; i++)
cout << bucket [i];
© 2002 Karl Winklmann