Category : C++ Source Code
Archive   : MERGSORT.ZIP
Filename : MERGSORT.CPP

////////////////////////////////////////////////////////////////////////////
// mergsort.cpp: Merge sort testing program.
// Adapted from upcoming book "Practical Algorithms in C++"
// by Bryan Flamig, (John Wiley & Sons), Spring 1994.
// Copyright(c) 1993 Azarona Software. All rights reserved.
//
// Usage: mergsort [options] [seed]
//
// -h Gives this usage
// -n num_items Specifies number of items to sort, (default 1000)
// -p Prints out the last list sorted, (default is no print)
// seed Starting seed for random numbers, (default based on clock)
////////////////////////////////////////////////////////////////////////////
#include
#include
#include
#include
#include

typedef int Item; // We'll use integer data just for example

struct Snode {
Item item;
Snode *next;
Snode();
Snode(const Item &x);
};

inline Snode::Snode()
{
next = 0;
}

inline Snode::Snode(const Item &x)
: item(x), next(0)
{
}

void PrtList(Snode *v)
// Prints a singly-linked list null-terminated list
// starting with node v
{
while(v) {
cout << v->item << ' ';
v = v->next;
}

cout << '\n';
}

void ClrList(Snode *v)
// Clears a singly-linked null-terminated list
// starting with node v
{
Snode *q;

while(v) {
q = v->next;
delete v;
v = q;
}
}

int RandomNum(int n)
// Return a random integer in the range [0..n-1]
{
return int(long(rand())*long(n) / (long(RAND_MAX) + 1));
}

void MakeRandomList(Snode *&v, int n)
// Passes back in v the starting node of a singly-linked
// null-terminated list of n randomly generated nodes.
{
cout << "Randomizing ...\n";
v = new Snode(RandomNum(INT_MAX));
Snode *p = v;
for (int i = 1; i p->next = new Snode(RandomNum(INT_MAX));
if (p->next == 0) {
cout << "WARNING: Out of room to add all nodes\n";
cout << "Only " << i << " nodes used\n";
break;
}
else p = p->next;
}
}

int CheckIfSorted(Snode *v)
// Tests to see if the singly-linked, null-terminated list starting
// with node v is sorted in ascending order.
// Returns 1 if list passes test, else 0.
{
Snode *q;

if (v == 0) return 1;
q = v->next;

while(1) {
if (q == 0) break;
if (v->item > q->item) return 0;
v = q;
q = q->next;
}
return 1;
}


void MergeSort(Snode *&v)
// Sorts the singly-linked null-terminated list starting with v
// in ascending order, setting v to the new front of the list.
// If you wish to use descending order, simply use >= instead
// of <= in the comparison given below.
{
// If list has 0 or 1 nodes, we're sorted

if (v == 0 || v->next == 0) return;

Snode head[4]; // Dummy header nodes for temp lists
Snode *p, *q, *r, *s, *t; // Pointers used in walking lists

// Otherwise, split the list in two, and place each half into
// the first two temporary working lists, which have headers

p = v; head[0].next = p; // p & q are the "current" nodes
q = v->next; head[1].next = q; // that we walk down lists with

r = v->next->next; // r is current node of input list

while(1) {
if (r == 0) break;
p->next = r; p = r; r = r->next;
if (r == 0) break;
q->next = r; q = r; r = r->next;
}

p->next = 0; q->next = 0; // Be sure to null-terminate the lists

// Now, start the merge sorting. Basically, we merge two n-node
// blocks, one from each input list, into 2*n-node blocks,
// alternating between the two output lists, and alternating
// the groups of input and output lists. This process is
// repeated until we have only one input list. This list is
// absorbed into the original list coming in, which by the
// way will be empty and waiting.

// In what follows: p is first input list, q is second input list,
// r is first output list, s is second output list, and t is
// the currently selected output list. p_cnt is how many nodes
// we need to extract from p in the inner loop, q_cnt is ditto
// for q. We use p_cnt == -1 and q_cnt == -1 to signal that
// these lists are empty.


int p_cnt, q_cnt, n, outer_toggle, inner_toggle;

outer_toggle = 0; n = 1;

while(1) {

// Do one merging pass, merging n-blocks into 2n-blocks.
// Alternate between the 2 groups of working lists

if (outer_toggle == 1) {
p = head[2].next; q = head[3].next;
if (q == 0) break; // p is head of sorted list, r the tail
r = &head[0]; s = &head[1];
outer_toggle = 0;
}
else {
p = head[0].next; q = head[1].next;
if (q == 0) break; // p is head of sorted list, r the tail
r = &head[2]; s = &head[3];
outer_toggle = 1;
}

p_cnt = 0; q_cnt = 0; inner_toggle = 0;

while(1) {
// Merge n nodes from each input list into 2n nodes for an
// output list, alternating between each output list, until
// the input is exhausted.
inner_toggle ^= 1;
t = inner_toggle ? r : s;
if (p_cnt >= 0) p_cnt = n; // Set to n if p list isn't empty
if (q_cnt >= 0) q_cnt = n; // Set to n if q list isn't empty
while(1) {
// Merge n nodes from each input list into 2n nodes in
// one of the output lists. May exhaust both input lists
// before we get n from each.
if (p_cnt > 0 && (q_cnt < 1 || p->item <= q->item)) {
t->next = p;
t = p;
p = p->next;
if (p == 0) p_cnt = -1; else p_cnt--;
}
else {
if (q_cnt < 1) break; // We have enough, or EOL for both inputs
t->next = q;
t = q;
q = q->next;
if (q == 0) q_cnt = -1; else q_cnt--;
}
}
if (inner_toggle) r = t; else s = t; // Update walking pointers
if (p_cnt < 0 && q_cnt < 0) break;
}

r->next = 0; s->next = 0; // Be sure to null-terminate working lists

n = n + n; // Ready to do another pass of 2n-blocks

}

// At this point, p is the head of the sorted list, r is the tail

v = p;
}

main(int argc, char *argv[])
{
const int num_iters = 10;
int i, num_items, jj, print_it;
unsigned seed;
clock_t stime, etime, ttime;

seed = (unsigned)time(NULL);

i = 1;

// Set defaults:

seed = (unsigned)time(NULL);
num_items = 1000;
print_it = 0;

while(i < argc) {
if (!strcmp(argv[i], "-p")) {
print_it = 1;
}
else if (!strcmp(argv[i], "-n")) {
num_items = atoi(argv[++i]);
}
else if (!strcmp(argv[i], "-h")) {
cout << "Usage: mergsort [options] [seed]\n\n";
cout << "-h Gives this usage\n";
cout << "-n num_items Specifies number of items to sort, (default 1000)\n";
cout << "-p Prints out the last list sorted, (default is no print)\n";
cout << "seed Starting seed for random numbers, (default based on clock)\n";
return 0;
}
else {
seed = (unsigned)atoi(argv[i]);
}
i++;
}

srand(seed);

cout << "List size " << num_items << ", seed = " << seed << "\n\n";
cout << "Sorting list of " << num_items << " in ascending order...\n";

Snode *tst_list = 0;

ttime = 0;

for (jj = 0; jj < num_iters; jj++) {
ClrList(tst_list);
MakeRandomList(tst_list, num_items);
cout << "Sorting ...\n";
cout.flush();
stime = clock();
MergeSort(tst_list);
etime = clock();
ttime += etime - stime;
cout << "Testing sort results ... ";
cout.flush();
if (CheckIfSorted(tst_list)) {
cout << "passed.\n";
}
else {
cout << "failed.\n";
exit(1);
}
}

if (print_it) PrtList(tst_list);

cout << num_iters << " ascending sorts in approximately "
<< (ttime)/(CLK_TCK*num_iters) << " seconds per sort\n";

cout << "List size " << num_items << ", seed = " << seed << "\n\n";

return 0;
}