bsort.cpp

冒泡发排序

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



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

//主程序
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";

// 正确输入循环
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;

// 产生随机数组
int *rawData;
rawData = new int[sampleSizes[sampleSizeIndex - 1]];

// 随机起点
srand(time(NULL));

// 产生随机数
for(i = 0; i < sampleSizes[sampleSizeIndex - 1]; i++)
   rawData[i] = rand();

cout << "Statistics::" << endl
     << "The Random Sample Size is " << sampleSizes[sampleSizeIndex - 1]
     << "." << endl << endl;
//冒泡排序
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);
// 冒泡排序结束

// 双向冒泡排序
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);
// 双向冒泡排序结束



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


// 冒泡排序实现

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);
}

//双向冒泡排序实现
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);
   }
}


//向上排序
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);
}
//向下排序
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);
}

//向上合并
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);
}

//向下合并
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);
}

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

//结果输出
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;
}

//屏幕输出
#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