timequicksort.cpp

C++&datastructure书籍源码,以前外教提供现在与大家共享

#include <iostream>
#include <string>
using namespace std;
#include "ctimer.h"
#include "tvector.h"
#include "sortall.h"
#include "randgen.h"
#include "prompt.h"

// compare running times of quick and insertion sort

void Shuffle(tvector<int> & a, int count)
// precondition: a has space for count elements
// postcondition: a contains 0..count-1 randomly shuffled    
{
    RandGen gen;    // for random # generator
    int randIndex,k;
    
    // fill with valuesl 0..count-1
    for(k=0; k < count; k++)
    {   a[k] = k;
    }
    // choose random index from k..count-1 and interchange with k
    for(k=0; k < count - 1; k++)
    {   randIndex = gen.RandInt(k,count-1);   // random index
        Swap(a,k,randIndex);                  // swap in sortall.h
    }
}

int main()
{
    int size,minSize,maxSize,incr; // sort minSize, minSize+incr, ... maxSize
    CTimer timer;

    cout << "min and max size of vector: ";
    cin >> minSize >> maxSize;
    incr =  PromptRange("increment in vector size",1,10000);
    
    cout << endl << "n\tinsert\tquick" << endl << endl;
    for(size=minSize; size <= maxSize; size += incr)
    {   tvector<int> copy(size), original(size);
        cout << size << "\t";
        Shuffle(original,size);
        
        copy = original;     // sort using insertion sort
        timer.Start();
        MergeSort(copy,copy.size());
        timer.Stop();
        cout << timer.ElapsedTime() << "\t";
        
        copy = original;     // sort using quick sort
        timer.Start();
        QuickSort(copy,copy.size());
        timer.Stop();
        cout << timer.ElapsedTime() << endl;
    }
    return 0;
}