sort.cpp

Code

/*
    sort.cpp
    CIS 250
    David Klick
    2005-01-31
    revised 2010-11-21

    Demonstration of various sorting algorithms.
*/

#include <iostream>
#include <cstdlib>
#include <sys/time.h>
#include <time.h>
#include <limits.h>
using std::cout;
using std::endl;

int ARRAY_SIZE = 100000;

void copyArray(int*, int*, int);
bool isSorted(int*, int);
void bubbleSort(int*, int);
void mySort(int*, int);
void woldSort(int*, int);
void insertionSort(int*, int);
void selectionSort(int*, int);
void shellSort(int*, int);
void mergeSort(int*, int);
void m_sort(int*, int*, int, int);
void merge(int*, int*, int, int, int);
void heapSort(int*, int);
void siftDown(int*, int, int);
void quickSort(int*, int);
void q_sort(int*, int, int);
void quickSort2(int*, int);
void q_sort2(int*, int, int);

int main(int argc, char* argv[]) {
    if (argc > 1) ARRAY_SIZE = atoi(argv[1]);
    cout << "Array size: " << ARRAY_SIZE << '\n';

    long elapsedTime;
    srand(time(NULL));
    timeval startTime, stopTime;
    static struct timezone tz;
    const int RANGE = 1000000;
    int work[ARRAY_SIZE];
    int hold[ARRAY_SIZE];
    // create an array of random integers
    for (int i=0; i<ARRAY_SIZE; i++) {
        hold[i] = rand() % RANGE;
    }

    // copy holding array to working array and do bubble sort
    copyArray(hold, work, ARRAY_SIZE);
    if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
    cout << "Sorting work array using bubble sort ";
    gettimeofday(&startTime, &tz);
    bubbleSort(work, ARRAY_SIZE);
    gettimeofday(&stopTime, &tz);
    elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
        + (stopTime.tv_usec - startTime.tv_usec);
    if (!isSorted(work, ARRAY_SIZE)) cout << "- bubble sort failed!\n";
    else cout << "- elapsed time: " << elapsedTime << "us\n";

    // copy holding array to working array and do my sort
    copyArray(hold, work, ARRAY_SIZE);
    if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
    cout << "Sorting work array using my sort ";
    gettimeofday(&startTime, &tz);
    mySort(work, ARRAY_SIZE);
    gettimeofday(&stopTime, &tz);
    elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
        + (stopTime.tv_usec - startTime.tv_usec);
    if (!isSorted(work, ARRAY_SIZE)) cout << "- my sort failed!\n";
    else cout << "- elapsed time: " << elapsedTime << "us\n";

    // copy holding array to working array and do Jermey Wold's sort
    copyArray(hold, work, ARRAY_SIZE);
    if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
    cout << "Sorting work array using Wold sort ";
    gettimeofday(&startTime, &tz);
    woldSort(work, ARRAY_SIZE);
    gettimeofday(&stopTime, &tz);
    elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
        + (stopTime.tv_usec - startTime.tv_usec);
    if (!isSorted(work, ARRAY_SIZE)) cout << "- Wold sort failed!\n";
    else cout << "- elapsed time: " << elapsedTime << "us\n";

    // copy holding array to working array and do selection sort
    copyArray(hold, work, ARRAY_SIZE);
    if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
    cout << "Sorting work array using selection sort ";
    gettimeofday(&startTime, &tz);
    selectionSort(work, ARRAY_SIZE);
    gettimeofday(&stopTime, &tz);
    elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
        + (stopTime.tv_usec - startTime.tv_usec);
    if (!isSorted(work, ARRAY_SIZE)) cout << "- selection sort failed!\n";
    else cout << "- elapsed time: " << elapsedTime << "us\n";

    // copy holding array to working array and do insertion sort
    copyArray(hold, work, ARRAY_SIZE);
    if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
    cout << "Sorting work array using insertion sort ";
    gettimeofday(&startTime, &tz);
    insertionSort(work, ARRAY_SIZE);
    gettimeofday(&stopTime, &tz);
    elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
        + (stopTime.tv_usec - startTime.tv_usec);
    if (!isSorted(work, ARRAY_SIZE)) cout << "- insertion sort failed!\n";
    else cout << "- elapsed time: " << elapsedTime << "us\n";

    // copy holding array to working array and do shell sort
    copyArray(hold, work, ARRAY_SIZE);
    if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
    cout << "Sorting work array using shell sort ";
    gettimeofday(&startTime, &tz);
    shellSort(work, ARRAY_SIZE);
    gettimeofday(&stopTime, &tz);
    elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
        + (stopTime.tv_usec - startTime.tv_usec);
    if (!isSorted(work, ARRAY_SIZE)) cout << "- shell sort failed!\n";
    else cout << "- elapsed time: " << elapsedTime << "us\n";

    // copy holding array to working array and do merge sort
    copyArray(hold, work, ARRAY_SIZE);
    if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
    cout << "Sorting work array using merge sort ";
    gettimeofday(&startTime, &tz);
    mergeSort(work, ARRAY_SIZE);
    gettimeofday(&stopTime, &tz);
    elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
        + (stopTime.tv_usec - startTime.tv_usec);
    if (!isSorted(work, ARRAY_SIZE)) cout << "- merge sort failed!\n";
    else cout << "- elapsed time: " << elapsedTime << "us\n";

    // copy holding array to working array and do heap sort
    copyArray(hold, work, ARRAY_SIZE);
    if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
    cout << "Sorting work array using heap sort ";
    gettimeofday(&startTime, &tz);
    heapSort(work, ARRAY_SIZE);
    gettimeofday(&stopTime, &tz);
    elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
        + (stopTime.tv_usec - startTime.tv_usec);
    if (!isSorted(work, ARRAY_SIZE)) cout << "- heap sort failed!\n";
    else cout << "- elapsed time: " << elapsedTime << "us\n";

    // copy holding array to working array and do quick sort
    copyArray(hold, work, ARRAY_SIZE);
    if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
    cout << "Sorting work array using quick sort ";
    gettimeofday(&startTime, &tz);
    quickSort(work, ARRAY_SIZE);
    gettimeofday(&stopTime, &tz);
    elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
        + (stopTime.tv_usec - startTime.tv_usec);
    if (!isSorted(work, ARRAY_SIZE)) cout << "- quick sort failed!\n";
    else cout << "- elapsed time: " << elapsedTime << "us\n";

    // copy holding array to working array and do quick sort 2
    copyArray(hold, work, ARRAY_SIZE);
    if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
    cout << "Sorting work array using quick sort 2 ";
    gettimeofday(&startTime, &tz);
    quickSort2(work, ARRAY_SIZE);
    gettimeofday(&stopTime, &tz);
    elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
        + (stopTime.tv_usec - startTime.tv_usec);
    if (!isSorted(work, ARRAY_SIZE)) cout << "- quick sort 2 failed!\n";
    else cout << "- elapsed time: " << elapsedTime << "us\n";
}

void copyArray(int from[], int to[], int len) {
    for (int i=0; i<len; i++) to[i] = from[i];
}

bool isSorted(int a[], int len) {
    for (int i=0; i<len-1; i++) {
        if (a[i] > a[i+1]) return false;
    }
    return true;
}

void mySort(int a[], int len) {
    int i, j, temp;
    for (i=0; i<len-1; i++) {
        for (j = i+1; j<len; j++) {
            if (a[i] > a[j]) {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
}

void bubbleSort(int a[], int len) {
    int i, j, temp;
    for (i=len-1; i>=0; i--) {
        for (j = 1; j <= i; j++) {
            if (a[j-1] > a[j]) {
                temp = a[j-1];
                a[j-1] = a[j];
                a[j] = temp;
            }
        }
    }
}

void woldSort(int a[], int len) {
    int i, j, k, temp;
    for (i=0; i<len-1; i++) {
        for (j=i+1; j<len; j++) {
            if (a[i] > a[j]) {
                temp = a[j];
                for (k=j; k>i; k--) a[k] = a[k-1];
                a[i] = temp;
            }
        }
    }
}

void selectionSort(int a[], int len) {
    int i, j, min, temp;
    for (i=0; i<len-1; i++) {
        min = i;
        for (j=i+1; j<len; j++) {
            if (a[j] < a[min]) min = j;
        }
        temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
}

void insertionSort(int a[], int len) {
    int i, j, temp;
    for (i=1; i<len; i++) {
        temp = a[i];
        j = i;
        while ((j>0) && (a[j-1] > temp)) {
            a[j] = a[j-1];
            j--;
        }
        a[j] = temp;
    }
}

void shellSort(int a[], int len) {
    int i, j, incr, temp;
    incr = 3;
    while (incr > 0) {
        for (i=0; i<len; i++) {
            j = i;
            temp = a[i];
            while ((j >= incr) && (a[j-incr] > temp)) {
                a[j] = a[j-incr];
                j -= incr;
            }
            a[j] = temp;
        }
        if (incr/2 != 0) incr /= 2;
        else if (incr == 1) incr = 0;
        else incr = 1;
    }
}

void mergeSort(int a[], int len) {
    int tmp[len];
    m_sort(a, tmp, 0, len-1);
}

void m_sort(int a[], int tmp[], int left, int right) {
    int mid;
    if (right > left) {
        mid = (right + left) / 2;
        m_sort(a, tmp, left, mid);
        m_sort(a, tmp, mid+1, right);
        merge(a, tmp, left, mid+1, right);
    }
}

void merge(int a[], int tmp[], int left, int mid, int right) {
    int i, left_end, num_elements, tmp_pos;
    left_end = mid - 1;
    tmp_pos = left;
    num_elements = right - left + 1;
    while ((left <= left_end) && (mid <= right)) {
        if (a[left] <= a[mid]) tmp[tmp_pos++] = a[left++];
        else tmp[tmp_pos++] = a[mid++];
    }
    while (left <= left_end) tmp[tmp_pos++] = a[left++];
    while (mid <= right) tmp[tmp_pos++] = a[mid++];
    for (i=0; i < num_elements; i++) {
        a[right] = tmp[right];
        right--;
    }
}

void heapSort(int a[], int len) {
    for (int i=len/2; i>0; i--) siftDown(a, i, len);
    do {
        int tmp = a[0];
        a[0] = a[len-1];
        a[len-1] = tmp;
        len--;
        siftDown(a, 1, len);
    } while (len>1);
}

void siftDown(int a[], int k, int bottom) {
    int tmp = a[k-1];
    while (k <= bottom/2) {
        int j = k + k;
        if ((j < bottom) && (a[j-1]<a[j])) j++;
        if (tmp >= a[j-1]) break;
        else {
            a[k-1] = a[j-1];
            k = j;
        }
    }
    a[k-1] = tmp;
}

void quickSort(int a[], int len) {
    q_sort(a, 0, len-1);
}

void q_sort(int a[], int left, int right) {
    int pivotNdx, l_hold = left, r_hold = right;
    int pivot = a[left];
    while (left < right) {
        while ((a[right] >= pivot) && (left < right)) right--;
        if (left != right) a[left++] = a[right];
        while ((a[left] <= pivot) && (left < right)) left++;
        if (left != right) a[right--] = a[left];
    }
    a[left] = pivot;
    pivotNdx = left;
    left = l_hold;
    right = r_hold;
    if (left < pivotNdx) q_sort(a, left, pivotNdx-1);
    if (right > pivotNdx) q_sort(a, pivotNdx+1, right);
}

void quickSort2(int a[], int len) {
    q_sort2(a, 0, len-1);
}

void q_sort2(int a[], int left, int right) {
    if (right-left < 7) { insertionSort(a+left , right-left+1); return; }
    int pivotNdx, l_hold = left, r_hold = right;
    int pivot = a[left];
    while (left < right) {
        while ((a[right] >= pivot) && (left < right)) right--;
        if (left != right) a[left++] = a[right];
        while ((a[left] <= pivot) && (left < right)) left++;
        if (left != right) a[right--] = a[left];
    }
    a[left] = pivot;
    pivotNdx = left;
    left = l_hold;
    right = r_hold;
    if (left < pivotNdx) q_sort2(a, left, pivotNdx-1);
    if (right > pivotNdx) q_sort2(a, pivotNdx+1, right);
}

/*
    Example output:

    Array size: 100000
    Sorting work array using bubble sort - elapsed time: 55601917us
    Sorting work array using my sort - elapsed time: 55000546us
    Sorting work array using Wold sort - elapsed time: 32083126us
    Sorting work array using selection sort - elapsed time: 16975082us
    Sorting work array using insertion sort - elapsed time: 14584673us
    Sorting work array using shell sort - elapsed time: 5871250us
    Sorting work array using merge sort - elapsed time: 36676us
    Sorting work array using heap sort - elapsed time: 29243us
    Sorting work array using quick sort - elapsed time: 21331us
    Sorting work array using quick sort 2 - elapsed time: 19103us
*/