#include "SampleStatistics.h"
#include "Sorting.h"
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <chrono>
using namespace std::chrono;
using namespace std;
// https://www.geeksforgeeks.org/measure-execution-time-function-cpp/
char GetSubOption(char title[])
{
char line[128];
cout << title << endl;
cout << "1 Insertion Sort" << endl;
cout << "2 Selection Sort" << endl;
cout << "3 Heap Sort" << endl;
cout << "4 Quick Sort" << endl;
cout << "5 Singleton's Sort" << endl;
cout << "6 Tree Sort 3" << endl;
cout << "7 Exit Submenu" << endl;
cout << "8 Exit Program" << endl;
cout << "Suboption Number: ";
cin.getline(line, 128);
return line[0];
}
char DoSort(char option) {
char subOption, line[128];
char title[128] = { 0 };
char name[6][64] = { { 0 } };
strcpy_s(name[0], 64, "Insertion Sort");
strcat_s(name[1], 64, "Selection Sort");
strcat_s(name[2], 64, "Heap Sort");
strcat_s(name[3], 64, "Quick Sort");
strcat_s(name[4], 64, "Singleton's Sort");
strcat_s(name[5], 64, "Tree Sort 3");
vector<double> runtime;
if (option == '1')
{
strcpy_s(title, 128, "Single Sorting Tests Submenu");
}
else {
strcpy_s(title, 128, "Statistical Sorting Tests Submenu");
}
subOption = GetSubOption(title);
if (subOption < '1' || subOption > '8') {
cout << "Illegal Suboption Exiting Application!" << endl;
exit(-1);
}
if (subOption == '7' || subOption == '8') {
return subOption;
}
int index = (int)(subOption - '1');
cout << name[index] << endl;
cout << "PRNG Seed = ";
cin.getline(line, 128);
int seed = atoi(line);
cout << "Number of Samples = ";
cin.getline(line, 128);
int n = atoi(line);
cout << "Maximum Sample Value = ";
cin.getline(line, 128);
int maximum = atoi(line);
srand(seed);
int number;
if (option == '2') {
cout << "Number of Experiments = ";
cin.getline(line, 128);
number = atoi(line);
}
else {
number = 1;
}
double* sample = new double[n];
double* shadow = new double[n];
for (int i = 0; i < number; i++) {
for (int j = 0; j < n; j++) {
sample[j] = rand() % maximum;
if (option == '1') {
shadow[j] = sample[j];
}
}
auto start = high_resolution_clock::now();
switch (subOption) {
case '1':
Sorting::InsertionSort(sample, n);
break;
case '2':
Sorting::SelectionSort(sample, n);
break;
case '3':
Sorting::HeapSort(sample, n);
break;
case '4':
Sorting::QuickSort(sample, n);
break;
case '5':
Sorting::SingletonsSort(sample, n);
break;
case '6':
Sorting::TreeSort3(sample, n);
break;
default:
cout << "Unknown Suboption" << endl;
break;
}
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
double rt = (double)duration.count();
runtime.push_back(rt);
}
if (option == '1') {
for (int i = 0; i < n; i++) {
cout << setw(2) << shadow[i] << ' ';
cout << setw(2) << sample[i] << endl;
}
}
else if (option == '2') {
cout << "Runtimes in Microseconds" << endl;
cout << "Minimum Runtime = "
<< setw(4) << fixed << setprecision(0)
<< SampleStatistics::Min(runtime) << endl;
cout << "Maximum Runtime = "
<< setw(4) << fixed << setprecision(0)
<< SampleStatistics::Max(runtime) << endl;
cout << "Mean Runtime = "
<< setw(4) << fixed << setprecision(0)
<< SampleStatistics::Mean(runtime) << endl;
cout << "Median Runtime = "
<< setw(4) << fixed << setprecision(0) <<
SampleStatistics::Median(runtime) << endl;
}
delete[] sample;
delete[] shadow;
return subOption;
}
int main() {
while (true) {
char line[128];
cout << "Menu" << endl;
cout << "1 Single Sortimg Tests" << endl;
cout << "2 Statistical Tests" << endl;
cout << "3 Exit" << endl;;
cout << "Option number: ";
cin.getline(line, 128);
if (line[0] == '3')
break;
if (line[0] == '1' || line[0] == '2') {
while (true)
{
char doSort = DoSort(line[0]);
if (doSort == '7')
break;
else if (doSort == '8')
exit(1);
}
}
}
return 0;
}
#pragma once
#include <limits.h>
#include <vector>
using namespace std;
class SampleStatistics {
public:
inline static double Mean(vector<double> x) {
double sum = 0;
for (int i = 0; i < (int)x.size(); i++)
sum += (double)x[i];
return sum / (int)x.size();
};
inline static double Max(vector<double> x)
{
double max = DBL_MIN;
for (int i = 0; i < (int)x.size(); i++)
if (x[i] > max)
max = x[i];
return max;
};
inline static double Min(vector<double> x)
{
double min = DBL_MAX;
for (int i = 0; i < (int)x.size(); i++)
if (x[i] < min)
min = x[i];
return min;
};
inline static double Median(vector<double> x)
{
int n = x.size(), n2 = n / 2 - 1;
if (n % 2 == 1)
return x[(n + 1) / 2 - 1];
return 0.5 * (x[n2] + x[n2 + 1]);
};
inline static double Variance(vector<double> x)
{
double mean = Mean(x), sumSq = 0;
int n = x.size();
int n1 = n - 1;
for (int i = 0; i < n; i++)
{
double delta = x[i] - mean;
sumSq += delta * delta;
}
return sumSq / n1;
};
};
#pragma once
// Insertion sort, heap sort, and quick sort algorithms
// From "Algortihms" by Thomas H. Cormen, et. al.
// Selection sort, Singleton's sort, and Tree Sort 3
// From "Sorting and Sort Systems" by Harold Lorin
class Sorting {
public:
static void InsertionSort(double a[], int n);
static void SelectionSort(double a[], int n);
static void HeapSort(double a[], int n);
static void QuickSort(double a[], int n);
static void SingletonsSort(double a[], int n);
static void TreeSort3(double a[], int n);
private:
// five helper methods for Heap Sort
static int Parent(int i);
static int Left(int i);
static int Right(int i);
static void BuildHeap(double a[], int n, int& heapSize);
static void Heapify(double a[], int i, int n, int& heapSize);
// helper methods for Quick Sort
static int Partition(double a[], int n, int lo, int hi);
static void DoQuickSort(double a[], int n, int p, int r);
// helper function for Singleton's sort
static void DoSingletonsSort(double a[], int ii, int jj);
// helper function for TreeSort3
static void SiftUp(double a[], int i, int n);
};
#include "Sorting.h"
void Sorting::InsertionSort(double a[], int n) {
for (int j = 1; j < n; j++)
{
double key = a[j];
int i = j - 1;
while (i >= 0 && a[i] > key)
{
a[i + 1] = a[i];
i--;
}
a[i + 1] = key;
}
}
void Sorting::SelectionSort(double a[], int n) {
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
if (a[i] > a[j])
{
double t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
}
int Sorting::Parent(int i) {
return i / 2;
}
int Sorting::Left(int i) {
return 2 * i;
}
int Sorting::Right(int i) {
return 2 * i + 1;
}
void Sorting::Heapify(double a[], int i, int n, int& heapSize) {
int l = Left(i);
int r = Right(i);
int largest = -1;
if (l < heapSize && a[l] > a[i])
largest = l;
else
largest = i;
if (r < heapSize && a[r] > a[largest])
largest = r;
if (largest != i)
{
double t = a[i];
a[i] = a[largest];
a[largest] = t;
Heapify(a, largest, n, heapSize);
}
}
void Sorting::BuildHeap(double a[], int n, int& heapSize) {
for (int i = n / 2; i >= 0; i--)
Heapify(a, i, n, heapSize);
}
void Sorting::HeapSort(double a[], int n) {
int heapSize = n;
BuildHeap(a, n, heapSize);
for (int i = n - 1; i >= 0; i--)
{
double t = a[0];
a[0] = a[i];
a[i] = t;
heapSize--;
Heapify(a, 0, n, heapSize);
}
}
int Sorting::Partition(double a[], int n, int lo, int hi) {
int pivotIndex = lo + (hi - lo) / 2;
double x = a[pivotIndex];
double t = x;
a[pivotIndex] = a[hi];
a[hi] = t;
int storeIndex = lo;
for (int i = lo; i < hi; i++)
{
if (a[i] < x)
{
t = a[i];
a[i] = a[storeIndex];
a[storeIndex++] = t;
}
}
t = a[storeIndex];
a[storeIndex] = a[hi];
a[hi] = t;
return storeIndex;
}
void Sorting::DoQuickSort(double a[], int n, int p, int r) {
if (p < r)
{
int q = Partition(a, n, p, r);
DoQuickSort(a, n, p, q - 1);
DoQuickSort(a, n, q + 1, r);
}
}
void Sorting::QuickSort(double a[], int n) {
DoQuickSort(a, n, 0, n - 1);
}
void Sorting::DoSingletonsSort(double a[], int ii, int jj) {
int m = 0;
int i = ii;
int j = jj;
int iu[50] = { 0 };
int il[50] = { 0 };
int ij = 0, l = 1, k = 0;
double t = 0.0, tt = 0.0;
Label1:
if (i >= j)
goto Label8;
goto Label2;
Label2:
k = i;
ij = (j + i) / 2;
t = a[ij];
if (a[i] <= t)
goto Label3;
a[ij] = a[i];
a[i] = t;
t = a[ij];
goto Label3;
Label3:
l = j;
if (a[j] >= t)
goto Label5;
a[ij] = a[j];
a[j] = t;
t = a[ij];
if (a[i] <= t)
goto Label5;
a[ij] = a[i];
a[i] = t;
t = a[ij];
goto Label5;
Label4:
a[l] = a[k];
a[k] = tt;
goto Label5;
Label5:
l--;
if (a[l] > t)
goto Label5;
tt = a[l];
goto Label6;
Label6:
k++;
if (a[k] < t)
goto Label6;
if (k <= l)
goto Label4;
if (l - i <= j - k)
goto Label7;
il[m] = i;
iu[m] = l;
i = k;
m++;
goto Label9;
Label7:
il[m] = k;
iu[m] = j;
j = l;
m++;
goto Label9;
Label8:
m--;
if (m == -1)
return;
i = il[m];
j = iu[m];
goto Label9;
Label9:
if (j - i > 10)
goto Label2;
if (i == ii)
goto Label1;
i--;
goto Label10;
Label10:
i++;
if (i == j)
goto Label8;
t = a[i + 1];
if (a[i] <= t)
goto Label10;
k = i;
goto Label11;
Label11:
a[k + 1] = a[k];
k--;
if (t < a[k])
goto Label11;
a[k + 1] = t;
goto Label10;
}
void Sorting::SingletonsSort(double a[], int n) {
DoSingletonsSort(a, 0, n - 1);
}
void Sorting::SiftUp(double a[], int i, int n) {
double copy = a[i];
int j;
while (true)
{
j = i + i;
if (j <= n)
{
if (j < n)
{
if (a[j + 1] > a[j])
j++;
}
if (a[j] > copy)
{
a[i] = a[j];
i = j;
continue;
}
}
break;
}
a[i] = copy;
}
void Sorting::TreeSort3(double a[], int n)
{
for (int i = n / 2; i >= 1; i--)
SiftUp(a, i, n - 1);
for (int i = n - 1; i >= 1; i--)
{
SiftUp(a, 0, i);
double t = a[0];
a[0] = a[i];
a[i] = t;
}
}
Author: jamespatewilliamsjr
My whole legal name is James Pate Williams, Jr. I was born in LaGrange, Georgia approximately 70 years ago. I barely graduated from LaGrange High School with low marks in June 1971. Later in June 1979, I graduated from LaGrange College with a Bachelor of Arts in Chemistry with a little over a 3 out 4 Grade Point Average (GPA). In the Spring Quarter of 1978, I taught myself how to program a Texas Instruments desktop programmable calculator and in the Summer Quarter of 1978 I taught myself Dayton BASIC (Beginner's All-purpose Symbolic Instruction Code) on LaGrange College's Data General Eclipse minicomputer. I took courses in BASIC in the Fall Quarter of 1978 and FORTRAN IV (Formula Translator IV) in the Winter Quarter of 1979. Professor Kenneth Cooper, a genius poly-scientist taught me a course in the Intel 8085 microprocessor architecture and assembly and machine language. We would hand assemble our programs and insert the resulting machine code into our crude wooden box computer which was designed and built by Professor Cooper. From 1990 to 1994 I earned a Bachelor of Science in Computer Science from LaGrange College. I had a 4 out of 4 GPA in the period 1990 to 1994. I took courses in C, COBOL, and Pascal during my BS work. After graduating from LaGrange College a second time in May 1994, I taught myself C++. In December 1995, I started using the Internet and taught myself client-server programming. I created a website in 1997 which had C and C# implementations of algorithms from the "Handbook of Applied Cryptography" by Alfred J. Menezes, et. al., and some other cryptography and number theory textbooks and treatises.
View all posts by jamespatewilliamsjr
Numerical Explorations 