1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171
|
/********************************************************\
Test program for demonstrating sorting algorithms
\********************************************************/
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include "dataobject.h"
using namespace std;
int randNum();
template <class iterator>
void sortContainer(iterator start, iterator finish, int gap);
int randNum()
{
// rand() produces pseudo-random number in range 0 to RAND_MAX
// for most compilers RAND_MAX is 2^15-1
// randNum() produces pseudo-random number in range 0 to 2^31-1
return ((rand() << 16) + rand());
}
template <class iterator>
int sortPercent(iterator start, iterator finish)
{
/************************************************** ***********************\
sortPercentage
Checks every consecutive pair of items in the container,
eg, 1st and 2nd, 2nd and 3rd, 3rd and 4th ... to ... 2nd last and last
and finds the percentage that are in order vs the total number of pairs.
This percentage value is returned.
\************************************************* ************************/
iterator left, right;
int InnerCount;
int comparisons;
int swaps = 0;
for (comparisons = 0; comparisons < finish; comparisons++)
{
for (InnerCount = 0; InnerCount < finish; InnerCount++)
{
right = left = start;
while (right != finish)
{
if (*left < *right)
{
swaps+=1;
}
}
}
comparisons+=1;
}
return comparisons;
}
template <class iterator>
void sortContainer(iterator start, iterator finish, int gap)
{
/****************************************************************\
Sort the container using shell sort
gap will be called with the original size of the container
The underlying sort for the container is bubble sort which
will be run twice for each gap decrement
\****************************************************************/
if (gap == 1) return;
iterator left, right;
int i, numswap, totswap=0, numpass;
gap = gap * 3 / 4;
do {
numswap = 0;
// Reduce gap. Gap will start out at half the size of the container
// Eventually will stabilize at 1 in size
gap = (gap * 2 + 1) / 3;
// make two passes through container with bubble sort
for (numpass=0; numpass<2; numpass++) {
right = left = start;
// Make the distance between left and right gap in size
for (i=0; i<gap; i++) right++;
// Make a pass through container using Bubble sort
while (right != finish) {
if (*left < *right) {
swap(left, right);
numswap++;
}
left++;
right++;
}
cout << "LOL \n";
// update some statistics and print them
totswap += numswap;
cout << "gap = " << gap << " num swaps = " << numswap;
cout << " sort percentage = " << sortPercent(start, finish) << "\n";
if (numswap == 0) break;
}
} while (numswap > 0 || gap > 1);
cout << "Total swaps = " << totswap << "\n";
}
int main(int argc, char *argv[])
{
const int MAXDATA = 10000;
vector<dataObject> array;
dataObject *doPtr;
int i, rand;
try {
/**************************************************************\
Initialise things to demonstrate the sort
\**************************************************************/
// fill vector with unique values
for (i=0; i<MAXDATA; i++) {
doPtr = new dataObject(i);
array.push_back(*doPtr);
delete doPtr;
}
// set up random number generator
if (argc != 2) {
cout << "Syntax : program seed\n";
cout << "seed is any integer value\n";
return 0;
}
int seed = atoi(argv[1]);
srand(seed);
// scramble vector
for (i=0; i<MAXDATA; i++) {
rand = randNum() % MAXDATA;
swap(array[i], array[rand]);
}
cout << MAXDATA << " Items in vector\n";
/*************************************************************\
sort the vector using iterators
\*************************************************************/
cout << "Sorting vector using shell sort\n";
sortContainer(array.begin(), array.end(), array.size());
} catch(...) {
cout << "\nERROR - undefined Exception thrown\n";
exit(1);
}
return 0;
}
|