multi-sort2.cpp

Bubble, BiDirectional Bubble, Bitonic排序算法

/////////////////////
//                 //
// Dave S. Maynard //
// -- Daxxus       //
//                 //
/////////////////////
//                 //
//   March 2001    //
//                 //
/////////////////////

#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>
#include <time.h>

//#define DEBUGIT

void printResults(double, int);
void bubbleSort(int[], int);
void bidirectionalBubbleSort(int[], int);
void bitonicSort(int[], int);
void sortUp(int[], int, int);
void sortDown(int[], int, int);
void mergeUp(int[], int, int);
void mergeDown(int[], int, int);
void Swap(int[], int, int);

#ifdef DEBUGIT
void printToScreen(int[], int, int);
void printToScreen(float[], int, int);
#endif

//////////
// Main //
//////////
void main()
{
int i = 0;
int startTime = 0;
int finishTime = 0;
double totalTime = 0.0;
int sampleSizeIndex;

int sampleSizes[] = {10, 50, 100, 500, 1000, 5000, 10000, 50000,
                     100000, 500000, 1000000};

cout << "Multi-Sort Program";

// Valid Input loop
while(1)
   {
   cout << endl << endl << "Sample Sizes:: ";
   for(int i = 0; i < 11; i++)
      cout << sampleSizes[i] << " ";
   cout << endl << "Choices::       ";
   cout << "1  2   3   4    5    6     7     8      9     10      11"
        << endl << endl << "Choose:: ";
   cin >> sampleSizeIndex;
   if((sampleSizeIndex < 1) || (sampleSizeIndex > 12))
      cout << "Your Choice must be between 1 and 12...";
   else
      break;
}
cout << endl;

// Creation of the Random Data Array
int *rawData;
rawData = new int[sampleSizes[sampleSizeIndex - 1]];

// Seed
srand(time(NULL));

// Creation of the Random Data
for(i = 0; i < sampleSizes[sampleSizeIndex - 1]; i++)
   rawData[i] = rand();

cout << "Statistics::" << endl
     << "The Random Sample Size is " << sampleSizes[sampleSizeIndex - 1]
     << "." << endl << endl;

// BUBBLE SORT //////////////////////////////////////////////
int *bubbleData;
bubbleData = new int[sampleSizes[sampleSizeIndex - 1]];

for(i = 0; i < sampleSizes[sampleSizeIndex - 1]; i++)
   bubbleData[i] = rawData[i];

startTime = clock();
bubbleSort(bubbleData, sampleSizes[sampleSizeIndex - 1] - 1);
finishTime = clock();

#ifdef DEBUGIT
printToScreen(bubbleData, sampleSizes[sampleSizeIndex - 1], 100);
#endif

delete [] bubbleData;
 
totalTime = double(finishTime - startTime) / CLOCKS_PER_SEC;
printResults(totalTime, 0);
// END BUBBLE SORT //////////////////////////////////////////

// BIDIRECTIONAL BUBBLE SORT ////////////////////////////////
int *biDiBubbleData;
biDiBubbleData = new int[sampleSizes[sampleSizeIndex - 1]];

for(i = 0; i < sampleSizes[sampleSizeIndex - 1]; i++)
   biDiBubbleData[i] = rawData[i];

startTime = clock();
bidirectionalBubbleSort(biDiBubbleData, sampleSizes[sampleSizeIndex - 1] - 1);
finishTime = clock();

#ifdef DEBUGIT
printToScreen(biDiBubbleData, sampleSizes[sampleSizeIndex - 1], 100);
#endif

delete [] biDiBubbleData;
 
totalTime = double(finishTime - startTime) / CLOCKS_PER_SEC;
printResults(totalTime, 1);
// END BIDIRECTIONAL BUBBLE SORT ////////////////////////////

// BITONIC SORT /////////////////////////////////////////////
int bitonicSampleSizes[] = {16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192,
                            16384, 32768, 65536, 131072};

cout << endl << endl << "For Bitonic Sort";

// Valid Input loop
while(1)
   {
   cout << endl << endl << "Sample Sizes:: " << endl;
   for(int i = 0; i < 14; i++)
      cout << bitonicSampleSizes[i] << " ";
   cout << endl << "Choices::       " << endl;
   cout << " 1  2  3   4   5   6    7    8    9   10    11    12    13     14"
        << endl << endl << "Choose:: ";
   cin >> sampleSizeIndex;
   if((sampleSizeIndex < 1) || (sampleSizeIndex > 14))
      cout << "Your Choice must be between 1 and 14...";
   else
      break;
}
cout << endl;

int *bitonicRawData;
bitonicRawData = new int[bitonicSampleSizes[sampleSizeIndex - 1]];

// Creation of the Random Data
for(i = 0; i < bitonicSampleSizes[sampleSizeIndex - 1]; i++)
   bitonicRawData[i] = rand();

cout << "Statistics::" << endl
     << "The Random Sample Size is " << bitonicSampleSizes[sampleSizeIndex - 1]
     << "." << endl << endl;

startTime = clock();
bitonicSort(bitonicRawData, bitonicSampleSizes[sampleSizeIndex - 1] - 1);
finishTime = clock();

#ifdef DEBUGIT
printToScreen(bitonicRawData, bitonicSampleSizes[sampleSizeIndex - 1], 100);
#endif

delete [] bitonicRawData;
 
totalTime = double(finishTime - startTime) / CLOCKS_PER_SEC;
printResults(totalTime, 2);
// END BITONIC SORT /////////////////////////////////////////

delete [] rawData;
cin.ignore();
cout << "Press [Enter] to Exit" << endl;
cin.get();
}

//////////////////////////
// Bubble Sort Function //
//////////////////////////
void bubbleSort(int values[], int size)
{
int temp = 0;
for(int j = 0; j < (size - 1); j++)
   for(int k = (j + 1); k < size; k++)
      if(values[j] > values[k])
         Swap(values, j, k);
}

/////////////////////////////////////////
// Bi-directional Bubble Sort Function //
/////////////////////////////////////////
void bidirectionalBubbleSort(int values[], int size)
{
int limit = size;
int st = -1;
while(st < limit)
   {
   st++;
   limit--;
   for(int i = st; i < limit; i++)
      if(values[i] > values[i + 1])
	     Swap(values, i, i + 1);
      
   for(int j = limit; j >= st; --j)
      if(values[j] > values[j+1])
	     Swap(values, j, j + 1);
   }
}

///////////////////////////
// Bitonic Sort Function //
///////////////////////////
void bitonicSort(int values[], int size)
{
sortUp(values, 0, size);
}

//////////////////////
// Sort Up Function //
//////////////////////
void sortUp(int values[], int m, int size)
{
if(size == 1)
   return;
sortUp(values, m, size/2);
sortDown(values, (m + size/2), size/2);
mergeUp(values, m, size/2);
}

////////////////////////
// Sort Down Function //
////////////////////////
void sortDown(int values[], int m, int size)
{
if(size == 1)
   return;
sortUp(values, m, size/2);
sortDown(values, (m + size/2), size/2);
mergeDown(values, m, size/2);
}

///////////////////////
// Merge Up Function //
///////////////////////
void mergeUp(int values[], int m, int size)
{
if(size == 0)
   return;
for(int i = 0; i < size; i++)
   if(values[m + i] > values[m + i + size])
      Swap(values, m + i, m + i + size);
        
mergeUp(values, m, size/2);
mergeUp(values, m + size, size/2);
}

////////////////////////
// Sort Down Function //
////////////////////////
void mergeDown(int values[], int m, int size)
{
if(size == 0)
   return;
for(int i = 0; i < size; i++)
   if(values[m + i] < values[m + i + size])
      Swap(values, m + i, m + i + size);

mergeDown(values, m, size/2);
mergeDown(values, m + size, size/2);
}

///////////////////
// Swap Function //
///////////////////
void Swap(int values[], int i, int j)
{
  int temp = values[i];
  values[i] = values[j];
  values[j] = temp;
}

///////////////////////////
// printResults Function //
///////////////////////////
void printResults(double totalTime, int title)
{
char* titles[] = {"Bubble Sort", "Bi-Directional Bubble Sort",
                  "Bitonic Sort"};
cout << "The execution time for " << titles[title] << " is:: "  
     << setprecision(5) << setiosflags(ios::fixed|ios::showpoint) 
     << totalTime << " Seconds." << endl;
}

//////////////////////////////////////////////////////////
// printToScreen Function -- this is for debugging only //
//////////////////////////////////////////////////////////
#ifdef DEBUGIT
void printToScreen(int values[], int size, int stepSize)
{
int columns = 0;
cout << endl << "DEBUG CODE::: " << endl;
for(int i = 0; i < size; i += stepSize)
   {
   cout << setw(6) << values[i];
   columns++;

   if(columns % 10 == 0)
      cout << endl;
   }
   cout << endl;
}
#endif