Sort Timed Test Sort


Program Listing

SortTimeTest.cpp

/************************************************************************
*                                                                       *
*   Program:    SortTimeTest                                            *
*                                                                       *
*   Purpose:    This program will sort a list of numbers using          *
*               various sorting algorithms and then report the run      *
*               times                                                   *
*                                                                       *
************************************************************************/

//  Header files

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

//  Function prototypes

void TimeTheSort(void (* Sort)(int*, int), int size, unsigned int seed, 
    string name);

void BubbleSort(int array[], int size);
void SelectionSort(int array[], int size);
void InsertionSort(int array[], int size);
void QuickSort(int array[], int size);

void GenerateList(int array[], int size);
void Swap(int &x, int &y);

int Comp(const void* a, const void* b);     // Needed for qsort()

using namespace std;

//  For this example, make the array global
//  (Global arrays are allocated differently from local arrays)

const int maxSize = 50000;
int array[maxSize];

/************************************************************************
*                                                                       *
*   Function:   main                                                    *
*                                                                       *
*   Purpose:    To sort a list of numbers using various sorting         *
*               algorithms and then report the run times                *
*                                                                       *
************************************************************************/

int main() {

//  Get the size of the list

    cout << "Enter the size of the list:  " << flush;
    int size;
    cin >> size;
    
//  Get a single seed to use for each sort method

    unsigned int seed = (unsigned int) time(0);

//  Perform the different sorts and report the times

    TimeTheSort(BubbleSort, size, seed, "Bubble Sort");
    TimeTheSort(SelectionSort, size, seed, "Selection Sort");
    TimeTheSort(InsertionSort, size, seed, "Insertion Sort");
    TimeTheSort(QuickSort, size, seed, "Quick Sort");
    
    return 0;
}

/************************************************************************
*                                                                       *
*   Function:   TimeTheSort                                             *
*                                                                       *
*   Purpose:    To run the specified sorting algorithm and report the   *
*               run time                                                *
*                                                                       *
************************************************************************/

void TimeTheSort(void (* Sort)(int*, int), int size, unsigned int seed, 
    string name) {

//  Generate a list of random integers

    srand(seed);
    cout << endl << "Generating a list of " << size << " numbers for the "
         << name << "..." << endl;
    GenerateList(array, size);
    
//  Run the Selection Sort
    
    cout << "Running the " << name << "..." << endl;
    int startTime = clock();
    Sort(array, size);
    int endTime = clock();  
    float elapsed = (float)(endTime - startTime)/CLOCKS_PER_SEC;

//  Report the elapsed time for the Selection Sort
    
    cout << name << " done." <<endl;
    cout << "elapsed time = " << elapsed << " sec." << endl;
    
    return;
}

/************************************************************************
*                                                                       *
*   Function:   GenerateList                                            *
*                                                                       *
*   Purpose:    To generate a list of random integers                   *
*                                                                       *
************************************************************************/

void GenerateList(int array[], int size) {
    for (int i = 0; i < size; i++)
        array[i] = rand();
    return;
}

/************************************************************************
*                                                                       *
*   Function:   BubbleSort                                              *
*                                                                       *
*   Purpose:    To sort a list of numbers using the bubble sort         *
*               algorithm                                               *
*                                                                       *
************************************************************************/

void BubbleSort(int list[], int size) {
    for (int i = 0; i < size - 1; i++)
        for (int j = 0; j < size - i - 1; j++)
            if (list[j] > list[j + 1]) {
                int temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
            }
    return;
}

/************************************************************************
*                                                                       *
*   Function:   SelectionSort                                           *
*                                                                       *
*   Purpose:    To sort a list of numbers using the selection sort      *
*               algorithm                                               *
*                                                                       *
************************************************************************/

void SelectionSort(int list[], int size) {

//  For each position in the list

    for (int i = 0; i < size - 1; i++) {
        int pos = i;
    
    //  Find the minimum value value from that position to the end
    
        int min = list[i];
        for (int j = i + 1; j < size; j++)
            if (list[j] < min) {
                pos = j;
                min = list[j];
            }
    
    //  Swap that position with the minimum
    
        Swap(list[i], list[pos]);
    }
    return;
}

/************************************************************************
*                                                                       *
*   Function:   InsertionSort                                           *
*                                                                       *
*   Purpose:    To sort a list of numbers using the insertion sort      *
*               algorithm                                               *
*                                                                       *
************************************************************************/

void InsertionSort(int list[], int size) {

//  For each position i > 0 in the list

    for (int i = 1; i < size; i++) {
    
    //  Insert the member in position i into the sorted sublist
    
        int item = list[i];
        int pos;
        for (pos = i - 1; pos >= 0 && list[pos] > item; pos--)
            list[pos + 1] = list[pos];
        list[pos + 1] = item;
    }

    return;
}

/************************************************************************
*                                                                       *
*   Function:   QuickSort                                               *
*                                                                       *
*   Purpose:    To sort a list of numbers using the quick sort          *
*               algorithm                                               *
*                                                                       *
************************************************************************/

void QuickSort(int array[], int size) {
    qsort((void *)array, (unsigned long)size, sizeof(int), Comp);
    return;
}

/************************************************************************
*                                                                       *
*   Function:   Comp                                                    *
*                                                                       *
*   Purpose:    To compare two integers.                                *
*                                                                       *
*   Note 1:     Comp will return                                        *
*                                                                       *
*                   1   if a > b                                        *
*                   0   if a = b                                        *
*                  -1   if a < b                                        *
*                                                                       *
*   Note 2:     Comp is intended to be used by the qsort() library      *
*               function                                                *
*                                                                       *
************************************************************************/

int Comp(const void* a, const void* b) {
    if (*(int*)a < *(int*)b) return -1;
    if (*(int*)a > *(int*)b) return 1;
    return 0;
}

/************************************************************************
*                                                                       *
*   Function:   Swap                                                    *
*                                                                       *
*   Purpose:    To swap the values of two integers                      *
*                                                                       *
************************************************************************/

void Swap(int &x, int &y) {
    int temp = x;
    x = y;
    y = temp;
    return;
}

Sample Run #1

Enter the size of the list:  10000

Generating a list of 10000 numbers for the Bubble Sort...
Running the Bubble Sort...
Bubble Sort done.
elapsed time = 4.26667 sec.

Generating a list of 10000 numbers for the Selection Sort...
Running the Selection Sort...
Selection Sort done.
elapsed time = 3.06667 sec.

Generating a list of 10000 numbers for the Insertion Sort...
Running the Insertion Sort...
Insertion Sort done.
elapsed time = 1.4 sec.

Generating a list of 10000 numbers for the Quick Sort...
Running the Quick Sort...
Quick Sort done.
elapsed time = 0.0666667 sec.

Sample Run #2

Enter the size of the list:  20000

Generating a list of 20000 numbers for the Bubble Sort...
Running the Bubble Sort...
Bubble Sort done.
elapsed time = 17.9833 sec.

Generating a list of 20000 numbers for the Selection Sort...
Running the Selection Sort...
Selection Sort done.
elapsed time = 13.3 sec.

Generating a list of 20000 numbers for the Insertion Sort...
Running the Insertion Sort...
Insertion Sort done.
elapsed time = 6.35 sec.

Generating a list of 20000 numbers for the Quick Sort...
Running the Quick Sort...
Quick Sort done.
elapsed time = 0.116667 sec.

Sample Run #3

Enter the size of the list:  40000

Generating a list of 40000 numbers for the Bubble Sort...
Running the Bubble Sort...
Bubble Sort done.
elapsed time = 79.3833 sec.

Generating a list of 40000 numbers for the Selection Sort...
Running the Selection Sort...
Selection Sort done.
elapsed time = 60.9167 sec.

Generating a list of 40000 numbers for the Insertion Sort...
Running the Insertion Sort...
Insertion Sort done.
elapsed time = 28.0667 sec.

Generating a list of 40000 numbers for the Quick Sort...
Running the Quick Sort...
Quick Sort done.
elapsed time = 0.266667 sec.



Return to Lectures page


e-mail me at robbk@hsc.edu

This page was last modified on Tue Dec 7 16:05:01 1999 .

URL: http://people.hsc.edu/faculty-staff/robbk/Coms261/Examples/SortTimeTest.html

Return to Coms 261 home page