search_and_sort.cpp

// Author: Taylor Carr
//
// Spring 2016
//
// This program generates a list of numbers and
// utilizes different sorting and searching methods
// to see which ones take the least amount of time
 
#include <iostream>
#include <iomanip>
#include <ctime>
#include <vector>
#include <cstdlib>
 
using namespace std;
 
void display(const vector<int> numbers);
void sequentialSearch(const vector<int> numbers);
void bubbleSort(const vector<int> numbers, vector<int> &sorted);
void selectionSort(const vector<int> numbers);
void insertionSort(const vector <int> numbers);
void quickSort (const vector<int> numbers, int, int, int &);
void sortedSequential(const vector<int> numbers);
void binarySearch (const vector<int> numbers);
 
int main() {
 
    int SIZE = 100000, // size of array
        recursions = 0; // recursion count for
                        // quick sort
    float start, // start time
          end;   // end time
 
    vector<int> numbers; //stores initial array
    vector<int> sorted; //stores sorted array
 
    srand(time(NULL));
 
    for (int i = 0; i < SIZE; i++){
        numbers.push_back(rand()%SIZE);
    }
 
    display(numbers);
 
    start = clock();
    sequentialSearch(numbers);
    end = clock();
    cout << endl << "Start Time:  " << fixed
         << setprecision(2) << start/1000;
    cout << endl << "End Time:    " << fixed
         << setprecision(2) << end/1000;
    cout << endl << "Time passed: " << ((end - start)/1000) << "s";
 
    start = clock();
    bubbleSort(numbers, sorted);
    end = clock();
    cout << endl << "Start Time:  " << fixed
         << setprecision(2) << start/1000;
    cout << endl << "End Time:    " << fixed
         << setprecision(2) << end/1000;
    cout << endl << "Time passed: " << ((end - start)/1000) << "s";
 
    start = clock();
    selectionSort(numbers);
    end = clock();
    cout << endl << "Start Time:  " << fixed
         << setprecision(2) << start/1000;
    cout << endl << "End Time:    " << fixed
         << setprecision(2) << end/1000;
    cout << endl << "Time passed: " << ((end - start)/1000) << "s";
 
    start = clock();
    insertionSort(numbers);
    end = clock();
    cout << endl << "Start Time:  " << fixed
         << setprecision(2) << start/1000;
    cout << endl << "End Time:    " << fixed
         << setprecision(2) << end/1000;
    cout << endl << "Time passed: " << ((end - start)/1000) << "s";
 
    start = clock();
    quickSort(numbers, 0, SIZE-1, recursions);
    end = clock();
    cout << endl << endl << "    Quick Sort" << endl
         << "Number of Recursions: " << recursions;
    cout << endl << "Start Time:  " << fixed
         << setprecision(2) << start/1000;
    cout << endl << "End Time:    " << fixed
         << setprecision(2) << end/1000;
    cout << endl << "Time passed: " << ((end - start)/1000) << "s";
 
    start = clock();
    sortedSequential(sorted);
    end = clock();
    cout << endl << "Start Time:  " << fixed
         << setprecision(2) << start/1000;
    cout << endl << "End Time:    " << fixed
         << setprecision(2) << end/1000;
    cout << endl << "Time passed: " << ((end - start)/1000) << "s";
 
    start = clock();
    binarySearch(sorted);
    end = clock();
    cout << endl << "Start Time:  " << fixed
         << setprecision(2) << start/1000;
    cout << endl << "End Time:    " << fixed
         << setprecision(2) << end/1000;
    cout << endl << "Time passed: " << ((end - start)/1000) << "s";
 
 
    cout << endl << endl << "Benchmark Algorithm Implemented by: "
            "Taylor Carr";
    cout << endl << "April 2016";
 
    return 0;
}
 
void display(vector<int> numbers){
 
    for (int i = 0; i < 20; i++){
        cout << numbers[i] << " ";
    }
}
 
void sequentialSearch(vector<int> numbers){
    int target = 500,    // number to search for
        i = 0,           // used in loops
        comparisons = 0; //counts how many
                         // checks there were for
                         // target number
    bool found = false;  // flag if number is found
 
    cout << endl << endl << "    Sequential Search"
         << endl << "Searching for: " << target << endl;
 
    while (found == false && i < numbers.size()){
        for (i = 0; i < numbers.size(); i++){
            comparisons++;
            if (numbers[i] == target){
                cout << endl << target << " was found at " << i;
                found = true;
                i = numbers.size();
            }
        }
    }
 
    if (found == false){
        cout << endl << target << " was not found.";
    }
 
    cout << endl << "Number of Comparisons: " << comparisons;
}
 
void bubbleSort(vector <int> numbers, vector<int> &sorted){
    int temp;              // variable used to swap values
    long exchanges = 0;    // keeps count of number of swaps
    bool swapped = false;  // flag to end loop
    sorted = numbers;      // copy of unsorted vector
 
    cout << endl << endl << "    Bubble Sort" << endl;
 
    do {
        swapped = false;
        for (int i = 0; i < sorted.size() - 1; i++){
            if (sorted[i] > sorted[i+1]) {
                temp = sorted[i];
                sorted[i] = sorted[i+1];
                sorted[i+1] = temp;
                exchanges++;
                swapped = true;
            }
        }
    } while (swapped == true);
 
    cout << "Number of exchanges: " << exchanges;
}
 
void selectionSort(vector <int> numbers){
    int min,            // smallest value
        minIndex,       // array index of min
        temp;           // temp variable for swap
    long exchanges = 0; // keeps count of
                        // number of swaps
    vector <int> selectionNums = numbers; // copy of unsorted vector
 
    cout << endl << endl << "    Selection Sort" << endl;
 
    for (int index = 0; index < selectionNums.size()-1; index++){
        min = selectionNums[index];
        for (int i = 1; i < selectionNums.size(); i++){
            if (selectionNums[i] < min){
                min = selectionNums[i];
                minIndex = i;
            }
        }
        temp = selectionNums[index];
        selectionNums[index] = min;
        selectionNums[minIndex] = temp;
        exchanges++;
    }
 
    cout << "Number of Exchanges: " << exchanges;
}
 
void insertionSort(vector <int> numbers){
    int temp,            // variable used to swap values
        traverse;        // traverses array for value comparison
    long insertions = 0; // keeps track of number
                         // of insertions
    vector<int> insertNums = numbers; // copy of unsorted vector
 
    cout << endl << endl << "    Insertion Sort" << endl;
 
    for (int index = 1; index < insertNums.size(); index++){
        traverse = index;
        while (traverse > 0 && insertNums[traverse - 1] > insertNums[traverse])
        {
            temp = insertNums[traverse];
            insertNums[traverse] = insertNums[traverse - 1];
            insertNums[traverse - 1] = temp;
            insertions++;
            traverse--;
        }
    }
 
    cout << "Number of Insertions: " << insertions;
}
 
void quickSort(vector <int> numbers, int left, int right, int &recursions){
    int i = left;                      // traverses left array
    int j = right;                     // traverses right array
    int temp;                          // variable used to swap values
    int pivot= numbers[(left+right/2)]; // splits array in 2
 
    while (i<=j) {
        while (numbers[i]<pivot) i++;
        while (numbers[j]>pivot) j--;
 
        if (i<=j) {
            temp= numbers[i];
            numbers[i]=numbers[j];
            numbers[j]=temp;
            i++;
            j--;
         }
    };
 
    if (left<j) {
        recursions++;
        quickSort(numbers, left, j, recursions);
    }
    if (i<right) {
        recursions++;
        quickSort(numbers, right, i, recursions);
    }
}
 
void sortedSequential(vector<int> numbers){
    int target = 500,    // value to search for
        i = 0,           // used in loops
        comparisons = 0; // keeps count for # of comparisons
    bool found = false;  // flag to end loop
 
    cout << endl << endl << "    Sorted Sequential Search"
         << endl << "Searching for: " << target << endl;
 
    while (found == false && i < numbers.size()){
        for (i = 0; i < numbers.size(); i++){
            comparisons++;
            if (numbers[i] == target){
                cout << endl << target << " was found at " << i;
                found = true;
                i = numbers.size();
            }
        }
    }
 
    if (found == false){
        cout << endl << target << " was not found.";
    }
 
    cout << endl << "Number of Comparisons: " << comparisons;
 
}
 
void binarySearch (vector<int> numbers){
    int first = 0,                 // index for beginning of search
        last = numbers.size() - 1, // index for end of search
        middle,                    // splits array in 2
        target = 500,              // value to search for
        comparisons = 0;           // keeps track of number of comparisons
    bool found = false;            // flag if value is found
 
    cout << endl << endl << "    Binary Search"
         << endl << "Searching for: " << target << endl;
 
    while(found == false && first <= last){
        middle = (first + last)/2;
        comparisons++;
        if (numbers[middle] == target){
            cout << endl << target << " was found at " << middle;
            found = true;
        }
        else if (numbers[middle] > target){
            last = middle - 1;
        }
        else {
            first = middle + 1;
        }
    }
 
    if (found == false){
        cout << endl << target << " was not found.";
    }
 
    cout << endl << "Number of Comparisons: " << comparisons;
}