/*
 * -----------------------------------------------------
 * CS2S03/SE2S03, November 2011
 * Assignment 5, Question 1
 * File: PE0803.cpp
 * -----------------------------------------------------
 * This program sorts an array of size n using a sorting
 * algorithm of O(n) complexity. Also, this program
 * measures the average time required to sort an array
 * of size 10.
 * -----------------------------------------------------
 */

#include "genlib.h"
#include <iostream>
#include <ctime>

/*
 * Constants
 * -----------------------------------------------------
 * MIN_RANGE -- Smallest possible value in the array
 * MAX_RANGE -- Largest possible value in the array
 */

const int MIN_RANGE = 0;
const int MAX_RANGE = 9999;

/* Private function prototypes */

void Sort(int arr[], int n);
void Display(int arr[], int n, double time);

/* Main program */

int main() {
    double start = 0.0;
    double finish = 0.0;
    double elapsed = 0.0;
    double time = 0.0;

    int arr[] = {0, 2000, 1000, 3000, 8000, 7000, 5000, 6000, 9999, 4000};
    int n = sizeof(arr) / sizeof(int);

    start = double(clock()) / CLOCKS_PER_SEC;
    for (int i = 0; i < 1000; i++) {
        Sort(arr, n);
    }
    finish = double(clock()) / CLOCKS_PER_SEC;

    elapsed = finish - start;
    time = elapsed / 1000.0;

    Display(arr, n, time);

    return 0;
}

/*
 * Function: Sort
 * Usage: Sort(arr, n)
 * -----------------------------------------------------
 * This function sorts the elements of the array into
 * increasing numerical order using a Non-comparison
 * sorting algorithm called Pigeonhole Sort.
 */

void Sort(int arr[], int n) {
    if (n < 2) return;

    const int k = MAX_RANGE - MIN_RANGE + 1;

    int holes[k];
    for (int i = 0; i < k; i++) {
        holes[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        holes[arr[i] - MIN_RANGE]++;
    }

    int i = 0;
    for (int c = 0; c < k; c++) {
        while (holes[c]-- > 0) {
            arr[i++] = c + MIN_RANGE;
        }
    }
}

/*
 * Function: Display
 * Usage: Display(arr, n, time)
 * -----------------------------------------------------
 * This function displays the sorted array and the time
 * required to execute the sorting algorithm.
 */

void Display(int arr[], int n, double time) {
    cout << "Sort Result:	";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    cout << "Average Time: " << time << " seconds" << endl;
}