Category: Sorting Algorithms

Blog Entry (c) Tuesday, June 3, 2025, Sorting Algorithms by James Pate Williams, Jr.

First, we make sure the sorts actually work as expected and then we do some timing tests.

^^ Integer Data ^^
** Options Menu **
1 Single Sorting Tests
2 Statistical Tests
3 Create log file and log events
4 Exit
Option number: 1
-- Single Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number: 1
Insertion Sort
PRNG Seed       1
Number of Samples       20
Maximum Sample Value    20
          11             -17
         -16             -16
           9             -14
         -17             -12
         -14              -7
          17               0
          10               0
           0               3
           7               6
           3               7
           8               7
           0               8
          -7               9
          11              10
         -12              11
          13              11
           7              12
          12              13
          16              16
           6              17
-- Single Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number: 2
std::qsort
PRNG Seed       1
Number of Samples       20
Maximum Sample Value    20
          11             -17
         -16             -16
           9             -14
         -17             -12
         -14              -7
          17               0
          10               0
           0               3
           7               6
           3               7
           8               7
           0               8
          -7               9
          11              10
         -12              11
          13              11
           7              12
          12              13
          16              16
           6              17
-- Single Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number: 3
Singleton's FORTRAN Sort
PRNG Seed       1
Number of Samples       20
Maximum Sample Value    20
          11             -17
         -16             -16
           9             -14
         -17             -12
         -14              -7
          17               0
          10               0
           0               3
           7               6
           3               7
           8               7
           0               8
          -7               9
          11              10
         -12              11
          13              11
           7              12
          12              13
          16              16
           6              17
-- Single Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number:
^^ Integer Data ^^
** Options Menu **
1 Single Sorting Tests
2 Statistical Tests
3 Create log file and log events
4 Exit
Option number: 2
-- Statistical Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number: 1
Insertion Sort
PRNG Seed       1
Number of Samples       1000
Maximum Sample Value    1000
Number of Experiments   100
Runtimes in microseconds
Minimum runtime          524
Maximum runtime         1751
Mean runtime             802
Median runtime           668
-- Statistical Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number: 2
std::qsort
PRNG Seed       1
Number of Samples       1000
Maximum Sample Value    1000
Number of Experiments   100
Runtimes in microseconds
Minimum runtime          115
Maximum runtime         1751
Mean runtime             481
Median runtime           391
-- Statistical Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number: 3
Singleton's FORTRAN Sort
PRNG Seed       1
Number of Samples       1000
Maximum Sample Value    1000
Number of Experiments   100
Runtimes in microseconds
Minimum runtime           93
Maximum runtime         1751
Mean runtime             363
Median runtime           174
-- Statistical Sorting Tests --
1 Insertion Sort
2 std::qsort
3 Singleton's FORTRAN Sort
4 Exit Submenu
5 Exit Program
Sort option number:
; Copilot and James Pate Williams, Jr.
; 2/8/2025 - 2/9/2025
; We use the eax register for array indices
; The array base in register ecx
; The register ebx is general purpose;
;
;class SortingCPP {
;public:
;	static void InsertionSort(std::vector<T>& a)
;	{
;		for (size_t j = 1; j < a.size(); j++)
;		{
;			T key = a[j];
;			int i = j - 1;
;
;			while (i >= 0 && a[i] > key)
;			{
;				a[i + 1] = a[i];
;				i--;
;			}
;
;			a[i + 1] = key;
;		}
;	};

.MODEL FLAT, C
.STACK 4096

.DATA
    ; Allocate space for uninitialized variables
    i DWORD ?
    j DWORD ?
    key DWORD ?
    n DWORD ?
    t DwORD ?

.CODE
InsertionSortASM PROC

    ; Parameters:
    ; array = [esp + 8]
    ; n = [esp + 12]

    push ebp
    mov ebp, esp
    sub esp, 16                 ; Allocate space for local variables

    mov ecx, [ebp + 8]          ; base of array
    mov eax, [ebp + 12]         ; n number of array elements
    mov [n], eax                ; store n

    ; Initialize variables
    mov dword ptr [i], 0        ; i = 0
    mov dword ptr [j], 1        ; j = 1

for_loop:

    mov eax, [j]                ; load j into register
    mov ebx, [n]                ; load n
    cmp eax, ebx                ; compare j to n
    je  Exit                    ; we are done

    mov ebx, [ecx + eax * 4]    ; ebx = a[j]
    mov [key], ebx              ; key = a[j]
    dec eax                     ; j = j - 1 
    mov [i], eax;               ; i = j - 1
    inc eax                     ; increment
    inc eax                     ; j = j + 1
    mov [j], eax                ; store j

while_loop:

    mov eax, [i]                ; load i into register
    cmp eax, -1                 ; is i == -1 ?
    jz  end_while               ; end the while loop
    mov ebx, [ecx + eax * 4]    ; load a[i]
    mov eax, [key]              ; load key into register
    cmp ebx, eax                ; compare a[i] to key
    jle end_while               ; end the while loop
    mov eax, [i]                ; load i
    mov ebx, [ecx + eax * 4]    ; load a[i]
    inc eax                     ; eax = i + 1
    mov edx, [ecx + eax * 4]    ; load a[i + 1]
    ;mov [t], ebx               ; t = a[i]
    mov edx, ebx                ; edx = a[i]
    mov eax, [i]                ; load i again
    inc eax                     ; i + 1
    mov [ecx + eax * 4], edx    ; a[i + 1] = a[i]
    dec eax                     ; i--
    dec eax                     ; i--
    mov [i], eax                ; store updated i
    jmp while_loop              ; continue while

end_while:

    mov eax, [i]                ; load i
    inc eax                     ; eax = i + 1
    mov ebx, [key]              ; ebx = key
    mov [ecx + eax * 4], ebx    ; a[i + 1] = key

    jmp for_loop                ; continue for loop

Exit:

    mov esp, ebp
    pop ebp
    ret

InsertionSortASM ENDP
END

Blog Entry © Thursday, February 13, 2025, by James Pate Williams, Jr. Comparison of Several C/C++ Sorting Algorithms in a Homemade Dynamic Link Library (DLL)

DLL Sorting Methods RuntimesDownload

Blog Entry © Thursday, January 23, 2025, by James Pate Williams, Jr. Merge Sort Verus Quick Sort

== Menu ==
1 Side-by-Side Tests
2 Timing Comparisons
3 Exit
Enter an option: 1
Enter a PRNG Seed >= 1: 1
0.001251        0.001251        0.001251
0.563585        0.014985        0.014985
0.193304        0.174108        0.174108
0.808740        0.193304        0.193304
0.585009        0.303995        0.303995
0.479873        0.350291        0.350291
0.350291        0.479873        0.479873
0.895962        0.513535        0.513535
0.822840        0.563585        0.563585
0.746605        0.585009        0.585009
0.174108        0.710501        0.710501
0.858943        0.746605        0.746605
0.710501        0.808740        0.808740
0.513535        0.822840        0.822840
0.303995        0.858943        0.858943
0.014985        0.895962        0.895962
== Menu ==
1 Side-by-Side Tests
2 Timing Comparisons
3 Exit
Enter an option:

== Menu ==
1 Side-by-Side Tests
2 Timing Comparisons
3 Exit
Enter an option: 2
Enter a PRNG Seed >= 1: 1
merge sort mean runtime (ms) = 523
quick sort mean runtime (ms) = 435
merge sort std dev (s) = 0.033457
quick sort std dev (s) = 0.027816
== Menu ==
1 Side-by-Side Tests
2 Timing Comparisons
3 Exit
Enter an option:
// MergeVersusQuick.c : This file contains the 'main' function.
// Program execution begins and ends there.
// mergesort is from "A Numerical Library in C for Scientists
// and Engineers" by H. T. Lau Translated from ALGOL NUMAL
// QuickSort is from "Introduction to Algorithms" by Thomas H.
// Cormen, Charles E. Leiserson, and Ronald L. Rivest

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LENGTH1			17		// static side-by-side test
#define LENGTHM1		16		// upper index
#define LENGTH2		  4097		// time test array length
#define LENGTHM2      4096		// upper inndex
#define NUMBER_TESTS  4096		// number of timing tests

void mergesort(float a[], int p[], int low, int up)
{
	int* allocate_integer_vector(int, int);
	void free_integer_vector(int*, int);
	void merge(int, int, int, int[], float[], int[]);
	int i, lo, step, stap, umlp1, umsp1, rest, restv, * hp;

	hp = allocate_integer_vector(low, up);
	for (i = low; i <= up; i++) p[i] = i;
	restv = 0;
	umlp1 = up - low + 1;
	step = 1;
	do {
		stap = 2 * step;
		umsp1 = up - stap + 1;
		for (lo = low; lo <= umsp1; lo += stap)
			merge(lo, step, step, p, a, hp);
		rest = up - lo + 1;
		if (rest > restv && restv > 0)
			merge(lo, rest - restv, restv, p, a, hp);
		restv = rest;
		step *= 2;
	} while (step < umlp1);
	free_integer_vector(hp, low);
}

int* allocate_integer_vector(int l, int u)
{
	/*  Allocates an integer vector of range [l..u].  */

	void system_error(char*);
	int* p;

	p = (int*)malloc((unsigned)(u - l + 1) * sizeof(int));
	if (!p) system_error("Failure in allocate_integer_vector().");
	return p - l;
}

void free_integer_vector(int* v, int l)
{
	/*  Frees an integer vector of range [l..u].  */

	free((char*)(v + l));
}

void system_error(char error_message[])
{
	void exit(int);

	printf("%s", error_message);
	exit(1);
}

void merge(int lo, int ls, int rs, int p[], float a[], int hp[])
{
	/* this procedure is used internally by MERGESORT */

	int l, r, lout, rout, i, pl, pr;

	l = lo;
	r = lo + ls;
	lout = rout = 0;
	i = lo;
	do {
		pl = p[l];
		pr = p[r];
		if (a[pl] > a[pr]) {
			hp[i] = pr;
			r++;
			rout = (r == lo + ls + rs);
		}
		else {
			hp[i] = pl;
			l++;
			lout = (l == lo + ls);
		}
		i++;
	} while (!(lout || rout));
	if (rout) {
		for (i = lo + ls - 1; i >= l; i--) p[i + rs] = p[i];
		r = l + rs;
	}
	for (i = r - 1; i >= lo; i--) p[i] = hp[i];
}

int Partition(float a[], int lo, int hi)
{
	int pivotIndex = lo + (hi - lo) / 2;
	float x = a[pivotIndex];
	float 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 DoQuickSort(float a[], int n, int p, int r)
{
	if (p < r)
	{
		int q = Partition(a, p, r);

		DoQuickSort(a, n, p, q - 1);
		DoQuickSort(a, n, q + 1, r);
	}
}

void QuickSort(float a[], int n)
{
	DoQuickSort(a, n, 1, n);
}

double runtime[2][NUMBER_TESTS];
float A[LENGTH1] = { 0 }, a[LENGTH1] = { 0 };
float AA[LENGTH2] = { 0 }, aa[LENGTH2] = { 0 };
float b[LENGTH1] = { 0 };
int n = NUMBER_TESTS;
int pp[LENGTH2];

int main()
{
	while (1)
	{
		float x;
		int i, j, option = 0, p[LENGTH1], seed = 1;

		printf("== Menu ==\n");
		printf("1 Side-by-Side Tests\n");
		printf("2 Timing Comparisons\n");
		printf("3 Exit\n");
		printf("Enter an option: ");
		scanf_s("%d", &option);

		if (option == 3)
			break;

		if (option == 1 || option == 2)
		{
			printf("Enter a PRNG Seed >= 1: ");
			scanf_s("%u", &seed);
			srand(seed);

			if (option == 1)
			{
				for (i = 1; i <= LENGTHM1; i++)
				{
					x = (float)rand() / RAND_MAX;
					A[i] = x;
					a[i] = x;
					b[i] = x;
				}

				mergesort(A, p, 1, LENGTHM1);
				QuickSort(a, LENGTHM1);

				for (i = 1; i <= LENGTHM1; i++)
					printf("%f\t%f\t%f\n", b[i], A[p[i]], a[i]);
			}

			else if (option == 2)
			{
				double mean[2] = { 0 }, median[2] = { 0 }, stdDev[2] = { 0 };
				double Sx[2] = { 0 };
				
				for (j = 0; j < n; j++)
				{
					for (i = 1; i <= LENGTHM2; i++)
					{
						x = (float)rand() / RAND_MAX;
						AA[i] = x;
						aa[i] = x;
					}
					
					clock_t start1 = clock();
					mergesort(AA, pp, 1, LENGTHM2);
					clock_t finis1 = clock();
					clock_t start2 = clock();
					QuickSort(aa, LENGTHM2);
					clock_t finis2 = clock();
					runtime[0][j] = ((double)finis1 - start1) / 
						CLOCKS_PER_SEC;
					runtime[1][j] = ((double)finis2 - start2) / 
						CLOCKS_PER_SEC;
					mean[0] += runtime[0][j];
					mean[1] += runtime[1][j];
				}

				for (j = 0; j < n; j++)
				{
					Sx[0] = pow((double)runtime[0][j] - mean[0], 2.0) / ((double)n - 1);
					Sx[1] = pow((double)runtime[1][j] - mean[1], 2.0) / ((double)n - 1);
				}

				stdDev[0] = (float)sqrt(Sx[0]);
				stdDev[1] = (float)sqrt(Sx[1]);

				printf("merge sort mean runtime (ms) = %3.0lf\n", 1.0e6 * mean[0] / n);
				printf("quick sort mean runtime (ms) = %3.0lf\n", 1.0e6 * mean[1] / n);
				printf("merge sort std dev (s) = %f\n", stdDev[0]);
				printf("quick sort std dev (s) = %f\n", stdDev[1]);
			}
		}
	}

	return 0;
}

Blog Entry (c) Tuesday, August 27, 2024, Graphing New Goldwasser-Kilian Primality Test Results by James Pate Williams, Jr.

New Goldwasser Kilian Primality Test ResultsDownload

The x -axis is the number to be tested, the y-axis is prime number bound for factoring, and the z-axis is the runtime in seconds.

Blog Entry (c) Wednesday, August 21, 2024, by James Pate Williams, Jr. New and Improved Version of the Goldwasser-Kilian Primality Test

I corrected my powering modulo a prime routine. I added Pollard’s p – 1 factoring method and Shanks-Mestre elliptic curve point counting algorithm.

number to be tested or 0 to quit:
10000019
number of primes in factor base:
10000
Prime sieving time = 3.220000
N[0] = 10000019
a = 7838973
b = 2449531
m = 9995356
q = 356977
P = (9786147, 3226544)
P1 = (0, 1)
P2 = (5887862, 8051455)
N[1] = 356977
a = 45561
b = 178451
m = 357946
q = 178973
P = (80627, 163299)
P1 = (0, 1)
P2 = (52101, 282559)
N[2] = 178973
a = 135281
b = 76426
m = 178996
q = 73
P = (10238, 98035)
P1 = (0, 1)
P2 = (46702, 94326)
number is proven prime
runtime in seconds = 35.471000

number to be tested or 0 to quit:
10015969
number of primes in factor base:
10000
Prime sieving time = 3.424000
N[0] = 10015969
a = 6613193
b = 3951715
m = 10013908
q = 2503477
P = (998314, 8329764)
P1 = (0, 1)
P2 = (6944357, 1053776)
N[1] = 2503477
a = 1175442
b = 379813
m = 2505736
q = 293
P = (646462, 1631861)
P1 = (0, 1)
P2 = (1477980, 88719)
number is proven prime
runtime in seconds = 5.612000

number to be tested or 0 to quit:
99997981
number of primes in factor base:
10000
Prime sieving time = 4.152000
N[0] = 99997981
a = 34129462
b = 80482974
m = 100001414
q = 181
P = (19305995, 40493835)
P1 = (0, 1)
P2 = (33828245, 72969559)
number is proven prime
runtime in seconds = 11.500000

number to be tested or 0 to quit:
100001819
number of primes in factor base:
100000
Prime sieving time = 3.218000
N[0] = 100001819
a = 2694060
b = 17329746
m = 100008102
q = 5569
P = (124594, 14596756)
P1 = (0, 1)
P2 = (32514144, 56926555)
number is proven prime
runtime in seconds = 76.301000

number to be tested or 0 to quit:
100005317
number of primes in factor base:
100000
Prime sieving time = 3.269000
N[0] = 100005317
a = 45478318
b = 328034
m = 99988256
q = 3124633
P = (62548529, 30179124)
P1 = (0, 1)
P2 = (70379514, 76899689)
N[1] = 3124633
a = 2605576
b = 1809212
m = 3127654
q = 503
P = (1236288, 2081401)
P1 = (0, 1)
P2 = (2264479, 2583693)
number is proven prime
runtime in seconds = 459.979000

number to be tested or 0 to quit:
100000007
number of primes in factor base:
100000
Prime sieving time = 3.209000
N[0] = 100000007
a = 50593669
b = 72502607
m = 100005736
q = 2053
P = (72365335, 69885097)
P1 = (0, 1)
P2 = (55023241, 20078454)
number is proven prime
runtime in seconds = 163.705000

number to be tested or 0 to quit:
100014437
number of primes in factor base:
100000
Prime sieving time = 3.919000
N[0] = 100014437
a = 49955472
b = 45482796
m = 100024160
q = 263
P = (41650735, 8652103)
P1 = (0, 1)
P2 = (53790105, 37282431)
number is proven prime
runtime in seconds = 12.915000
New and Improved Goldwasser Kilian Primality Test Single Precision C Source CodeDownload

Microsoft Visual Studio 2019 Community Version – Creating and Using a C Based Dynamic Link Library © March 22, 2024, by James Pate Williams, Jr.

Create a solution using the DLL C++ DLL template. Rename pch.cpp to pch.c and dllmain.cpp to dllmain.c. Add a header file for the DLL containing the following macro:

#define DLL_Export __declspec(dllexport)

Mark all the exportable functions in the DLL header file with the DLL_Export macro. Suppose the DLL is named CSortingDLL. Next create a console C++ project in the DLL solution to use the DLL. Open the Properties page of the console app. If you want to use the ASCII character set, select the Advanced Configuration Properties, and set the Character Set to Not Set. Now open the C/C++ General Property and under Additional Include Directories add ..\CSortingDLL\;. Do not include the previous period mark. Next open the Linker General Property page. Set Additional Library Directories to ..\CSortingDLL\$(IntDir);. The penultimate step is to set the Linker Input Additional Dependencies to CSortingDLL.lib;. The final step for the app is to add a reference to CSortingDLL.  Now you have a functioning DLL and an app using the DLL. If you have any questions, please contact me via email at jamespate@mac.com.  Also, Microsoft has a DLL walkthrough complete with source code. I will add my CSortingDLL header source code as a PDF document.

csortingdll_hDownload

Lau’s Merge-Sort Versus Cormen et. al. Quick-Sort (c) January 13-14, 2024, by James Pate Williams, Jr.

The merge-sort I used was from “A Numerical Library in C for Scientists and Engineers” by H. T. Lau Translated from ALGOL NUMAL. The quick-sort algorithm was from “Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest.

== Menu ==

1 Side-by-Side Tests

2 Timing Comparisons

3 Exit

Enter an option: 1

Enter a PRNG Seed >= 1: 1

0.001251        0.001251        0.001251

0.563585        0.014985        0.014985

0.193304        0.174108        0.174108

0.808740        0.193304        0.193304

0.585009        0.303995        0.303995

0.479873        0.350291        0.350291

0.350291        0.479873        0.479873

0.895962        0.513535        0.513535

0.822840        0.563585        0.563585

0.746605        0.585009        0.585009

0.174108        0.710501        0.710501

0.858943        0.746605        0.746605

0.710501        0.808740        0.808740

0.513535        0.822840        0.822840

0.303995        0.858943        0.858943

0.014985        0.895962        0.895962

== Menu ==

1 Side-by-Side Tests

2 Timing Comparisons

3 Exit

Enter an option:
== Menu ==

1 Side-by-Side Tests

2 Timing Comparisons

3 Exit

Enter an option: 2

Enter a PRNG Seed >= 1: 1

mergesort mean runtime = 0.358999

QuickSort mean runtime = 0.290000

mergesort std dev = 0.005610

QuickSort std dev = 0.004532

== Menu ==

1 Side-by-Side Tests

2 Timing Comparisons

3 Exit

Enter an option:

Latest Sorting C++ Code

#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, etc.
// From "Sorting and Sort Systems" by Harold Lorin
class Sorting {
public:
	// Translated from Lorin's PL/I procedure
	static void BasicExchange(long long tosort[], int number);
	// Translated from Lorin's PL/I procedure
	static void StandardExchange(long long tosort[], int number);
	static void InsertionSort(long long a[], int n);
	static void SelectionSort(long long a[], int n);
	// CACM Algorithm 175
	static void SimpleShifting(long long tosort[], int number);
	// CACM Algorithm 201 1963
	static void ShellSort(long long tosort[], int number);
	static void HeapSort(long long a[], int n);
	static void QuickSort(long long a[], int n);
	// CACM Algorithm 347 Ricahrd C. Singleton 1968
	// Translated from Lorin's PL/I procedure
	static void SingletonsSort(long long a[], int n);
	// CACM Algorithm 245 Robert W. Floyd 1964
	// Translated from Lorin's PL/I procedure
	static void TreeSort3(long long a[], int n);
	// see "Algortihms" by Thomas H. Cormen, et. al.
	// A is the array to be sorted, B is the sorted
	// array and k is maximum number in A
	static void CountingSort(
		long long A[],
		long long B[],
		long long C[],
		int n, long long k);
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(long long a[], int n, int& heapSize);
	static void Heapify(long long a[], int i, int n, int& heapSize);
	/* helper functions for SETHEAP
	static void SWOPHEAP(long long A[], int n, long long& in, long long& out);
	static void INHEAP(long long A[], int& n, long long& in);
	static void OUTHEAP(long long A[], int& n, long long& out);
	static void SETHEAP(long long A[], int n);*/
	// helper methods for Quick Sort
	static int Partition(long long a[], int n, int lo, int hi);
	static void DoQuickSort(long long a[], int n, int p, int r);
	// helper function for Singleton's sort
	static void DoSingletonsSort(long long a[], int ii, int jj);
	// helper function for TreeSort3
	static void SiftUp(long long a[], int i, int n);
};

#include "Sorting.h"
#include <math.h>

void Sorting::BasicExchange(long long tosort[], int number)
{
    int adjust = 2 * (number / 2);
    int elimit, olimit;

    if (adjust < number)
    {
        elimit = adjust;
        olimit = adjust - 1;
    }
    else
    {
        elimit = number - 2;
        olimit = number - 1;
    }
odd:
    int passw = 1;
    int limit = olimit;
    int oddeve = 1;
pass:
    int excount = 0;

    for (int i = oddeve; i <= limit; i += 2)
    {
        if (tosort[i] > tosort[i + 1])
        {
            long long temp = tosort[i];

            tosort[i] = tosort[i + 1];
            tosort[i + 1] = temp;
            excount = 1;
        }
    }
    if (excount == 0)
        return;

    if (passw == 1)
    {
        passw = 0;
        oddeve = 0;
        limit = elimit;
        goto pass;
    }

    goto odd;
}

void Sorting::StandardExchange(long long tosort[], int number)
{
pass:
    int excount = 0;

    for (int i = 0; i < number - 1; i++)
    {
        if (tosort[i] > tosort[i + 1])
        {
            long long temp = tosort[i];

            tosort[i] = tosort[i + 1];
            tosort[i + 1] = temp;
            excount = 1;
        }
    }
    if (excount == 0)
        return;
    goto pass;
}

void Sorting::InsertionSort(long long a[], int n)
{
    for (int j = 1; j < n; j++)
    {
        long long 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(long long a[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (a[i] > a[j])
            {
                long long t = a[i];

                a[i] = a[j];
                a[j] = t;
            }
        }
    }
}

void Sorting::SimpleShifting(long long tosort[], int number)
{
    for (int i = 0; i < number - 1; i++)
    {
        for (int j = i; j >= 0; j--)
        {
            if (tosort[j] > tosort[j + 1])
            {
                long long temp = tosort[j];

                tosort[j] = tosort[j + 1];
                tosort[j + 1] = temp;
            }
        }
    }
}

void Sorting::ShellSort(long long tosort[], int number)
{
    int lognumber = log2(number);
    int distance = (int)pow(2, lognumber) - 1;

    while (distance > 0)
    {
        int limit = number - distance;

        for (int j = 0; j < limit; j++)
        {
            for (int i = j; i >= 0; i--)
            {
                if (tosort[i + distance] < tosort[i])
                {
                    long long temp = tosort[i];

                    tosort[i] = tosort[i + distance];
                    tosort[i + distance] = temp;
                }
            }
        }

        distance /= 2;
    }
}

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(long long 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)
    {
        long long t = a[i];

        a[i] = a[largest];
        a[largest] = t;

        Heapify(a, largest, n, heapSize);
    }
}

void Sorting::BuildHeap(long long a[], int n, int& heapSize)
{
    for (int i = n / 2; i >= 0; i--)
        Heapify(a, i, n, heapSize);
}

void Sorting::HeapSort(long long a[], int n)
{
    int heapSize = n;

    BuildHeap(a, n, heapSize);

    for (int i = n - 1; i >= 0; i--)
    {
        long long t = a[0];

        a[0] = a[i];
        a[i] = t;

        heapSize--;

        Heapify(a, 0, n, heapSize);
    }
}

void SWOPHEAP(long long A[], int n,
    long long& in, long long& out)
{
    if (in <= A[0])
        out = in;
    else
    {
        int i = 0;
        A[n] = in;
        out = A[0];
    scan:
        int j = i + i;
        if (j <= n - 1)
        {
            long long temp = A[j];
            long long temp1 = A[j + 1];
            if (temp1 < temp)
            {
                temp = temp1;
                j++;
            }
            if (temp < in)
            {
                A[i] = temp;
                i = j;
                goto scan;
            }
        }
        A[i] = in;
    }
}

void INHEAP(long long A[], int& n, long long& in)
{
    int i = n;
    n++;
scan:
    if (i > 0)
    {
        int j = i / 2;
        if (in < A[j])
        {
            A[i] = A[j];
            i = j;
            goto scan;
        }
    }
    A[i] = in;
}

void OUTHEAP(long long A[], int& n, long long& out)
{
    SWOPHEAP(A, n - 1, A[n - 1], out);
    n = n - 2;
}

void SETHEAP(long long A[], int n)
{
    int j = 0;
L:
    INHEAP(A, j, A[j + 1]);

    if (j < n - 2)
        goto L;
}

void HEAP(long long A[], int n)
{
    SETHEAP(A, n);

    for (int i = n - 1; i >= 1; i--)
        OUTHEAP(A, i, A[i]);
}

int Sorting::Partition(long long a[], int n, int lo, int hi)
{
    int pivotIndex = lo + (hi - lo) / 2;
    long long x = a[pivotIndex];
    long long 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(long long 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(long long a[], int n)
{
    DoQuickSort(a, n, 0, n - 1);
}

void QuickerSort(long long tosort[], int number)
{
    const int limit = 20;
    int highlim = 0, lowlim, origin, partind, pivot;
    long long exch, temp = 0;
    int partablow[limit] = { 0 }, parttabhigh[limit] = { 0 };
    origin = partind = 0;
testsize:
    if (number - 1 - origin > 0)
    {
        pivot = (number - 1 + origin) / 2;
        temp = tosort[pivot];
        tosort[pivot] = tosort[origin];
        highlim = number - 1;

        for (lowlim = origin + 1; lowlim <= highlim; lowlim++)
        {
            if (tosort[lowlim] > temp)
            {
                for (highlim = highlim; highlim >= lowlim; highlim--)
                {
                    if (tosort[highlim] < temp)
                    {
                        exch = tosort[lowlim];
                        tosort[lowlim] = tosort[highlim];
                        tosort[highlim] = exch;
                        highlim = lowlim - 1;
                        goto limsmet;
                    }
                }
                highlim = lowlim - 1;
                goto limsmet;
            }
       }
    }
limsmet:
    tosort[origin] = tosort[highlim];
    tosort[highlim] = temp;
    if (2 * highlim > origin + number - 1)
    {
        partablow[partind] = origin;
        parttabhigh[partind] = highlim - 1;
        origin = highlim + 1;
    }
    else
    {
        partablow[partind] = highlim + 1;
        parttabhigh[partind] = number - 1;
        number = highlim - 1;
    }
    partind++;
    goto testsize;
    if (origin == number - 1)
        goto setpart;
    if (tosort[origin] > tosort[number - 1])
    {
        exch = tosort[origin];
        tosort[origin] = tosort[number - 1];
        tosort[number - 1] = exch;
    }
setpart:
    partind--;
    if (partind > -1)
    {
        origin = partablow[partind];
        number = parttabhigh[partind];
        goto testsize;
    }
}

void Sorting::DoSingletonsSort(long long 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;
    long long t = 0, tt = 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(long long a[], int n)
{
    DoSingletonsSort(a, 0, n - 1);
}

void Sorting::SiftUp(long long a[], int i, int n)
{
    long long 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(long long 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);

        long long t = a[0];

        a[0] = a[i];
        a[i] = t;
    }
}

void Sorting::CountingSort(
    long long A[],
    long long B[],
    long long C[],
    int n, long long k)
{
    for (long long i = 0; i <= k; i++)
        C[i] = 0;

    for (int j = 0; j < n; j++)
    {
        B[j] = 0;
        C[A[j]]++;
    }

    for (long long i = 1; i <= k; i++)
        C[i] += C[i - 1];

    for (int i = n - 1; i >= 0; i--)
    {
        long long j = A[i];

        C[j]--;
        B[C[j]] = A[i];
    }
}

#pragma once
#include <limits.h>
#include <vector>
using namespace std;

class SampleStatistics {
public:
	inline static long long Mean(vector<long long> x) {
		long long sum = 0;

		for (int i = 0; i < (int)x.size(); i++)
			sum += (long long)x[i];

		return sum / (int)x.size();
	};
	inline static long long Max(vector<long long> x)
	{
		long long max = LLONG_MIN;

		for (int i = 0; i < (int)x.size(); i++)
			if (x[i] > max)
				max = x[i];

		return max;
	};
	inline static long long Min(vector<long long> x)
	{
		long long min = LLONG_MAX;

		for (int i = 0; i < (int)x.size(); i++)
			if (x[i] < min)
				min = x[i];

		return min;
	};
	inline static long long Median(vector<long long> x)
	{
		unsigned int n0 = (unsigned int)x.size();
		unsigned int n1 = n0 / 2 - 1;
		unsigned int n2 = n0 / 2;
		long long median = 0, lt = x[n1], rt = x[n2];

		if ((n0 & 1) == 1)
			median = x[n0 / 2];
		else
			median = (lt + rt) / 2;

		return median;
	};
	inline static long long Variance(vector<long long> x)
	{
		long long mean = Mean(x), sumSq = 0;
		int n = (int)x.size();
		int n1 = n - 1;

		for (int i = 0; i < n; i++)
		{
			long long delta = x[i] - mean;

			sumSq += delta * delta;
		}

		return sumSq / n1;
	};
};

#include "SampleStatistics.h"
#include "Sorting.h"
#include <stdlib.h>
#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std::chrono;
using namespace std;

// https://www.geeksforgeeks.org/measure-execution-time-function-cpp/

int GetSubOption(char title[])
{
	char line[128];
	cout << title << endl;
	cout << "1 Basic Exchange" << endl;
	cout << "2 Standard Exchange" << endl;
	cout << "3 Insertion Sort" << endl;
	cout << "4 Selection Sort" << endl;
	cout << "5 Simple Sifting (Shuttle Sort)" << endl;
	cout << "6 Shell Sort" << endl;
	cout << "7 Heap Sort" << endl;
	cout << "8 Quick Sort" << endl;
	cout << "9 Singleton's Sort" << endl;
	cout << "10 Tree Sort 3" << endl;
	cout << "11 Counting Sort" << endl;
	cout << "12 Exit Submenu" << endl;
	cout << "13 Exit Program" << endl;
	cout << "Suboption Number: ";
	cin.getline(line, 128);

	int so = 0;
	if (strlen(line) > 1)
	{
		so = 10 * (line[0] - '0');
		so += line[1] - '0';
	}

	else
		so = line[0] - '0';
	
	return so;
}

int DoSort(char option) {
	char line[128];
	char title[128] = { 0 };
	char name[11][64] = { { 0 } };
	int subOption;

	strcpy_s(name[0], 64, "Basic Exchange");
	strcpy_s(name[1], 64, "Standard Exchange");
	strcpy_s(name[2], 64, "Insertion Sort");
	strcat_s(name[3], 64, "Selection Sort");
	strcpy_s(name[4], 64, "Simple Shifting");
	strcpy_s(name[5], 64, "Shell Sort");
	strcat_s(name[6], 64, "Heap Sort");
	strcat_s(name[7], 64, "Quick Sort");
	strcat_s(name[8], 64, "Singleton's Sort");
	strcat_s(name[9], 64, "Tree Sort 3");
	strcpy_s(name[10], 64, "Counting Sort");

	vector<long long> 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 > 13)
	{
		cout << "Illegal Suboption Exiting Application!" << endl;
		exit(-1);
	}

	if (subOption == 12)
		return subOption;
	
	if (subOption == 13)
		exit(1);

	int index = subOption - 1, maximum = 0, n = 0, seed = 1;

	cout << name[index] << endl;

	do {
		cout << "PRNG Seed             = ";
		cin.getline(line, 128);
		seed = atoi(line);
	} while (seed < 1);

	do {
		cout << "Number of Samples     = ";
		cin.getline(line, 128);
		n = atoi(line);
	} while (n < 2);

	do {
		cout << "Maximum Sample Value  = ";
		cin.getline(line, 128);
		maximum = atoi(line);
	} while (maximum < 10);

	srand(seed);

	int number = 0;
	
	if (option == '2')
	{
		do {
			cout << "Number of Experiments = ";
			cin.getline(line, 128);
			number = atoi(line);
		} while (number < 1);
	}

	else
	{
		number = 1;
	}
	
	long long k = 0;
	long long* B = new long long[n];
	long long* sample = new long long[n];
	long long* shadow = new long long[n];

	for (int i = 0; i < number; i++)
	{
		long long* C = NULL;

		for (int j = 0; j < n; j++)
		{
			sample[j] = rand() % maximum;

			if (option == '1') {
				shadow[j] = sample[j];
			}
		}

		if (subOption == 11)
		{
			for (int j = 0; j < n; j++)
				if (sample[j] > k)
					k = sample[j];

			C = new long long[(unsigned int)(k + 1)];
		}
		
		auto start = high_resolution_clock::now();

		switch (subOption) {
		case 1:
			Sorting::BasicExchange(sample, n);
			break;
		case 2:
			Sorting::StandardExchange(sample, n);
			break;
		case 3:
			Sorting::InsertionSort(sample, n);
			break;
		case 4:
			Sorting::SelectionSort(sample, n);
			break;
		case 5:
			Sorting::SimpleShifting(sample, n);
			break;
		case 6:
			Sorting::ShellSort(sample, n);
			break;
		case 7:
			Sorting::HeapSort(sample, n);
			break;
		case 8:
			Sorting::QuickSort(sample, n);
			break;
		case 9:
			Sorting::SingletonsSort(sample, n);
			break;
		case 10:
			Sorting::TreeSort3(sample, n);
			break;
		case 11:		
			Sorting::CountingSort(sample, B, C, n, k);
			break;
		default:
			cout << "Unknown Suboption" << endl;
			break;
		}

		auto stop = high_resolution_clock::now();
		auto duration = duration_cast<microseconds>(stop - start);
		long long rt = (long long)duration.count();

		runtime.push_back(rt);

		if (subOption == 11)
		{
			if (C != NULL)
				delete[] C;
		}
	}

	if (option == '1')
	{
		for (int i = 0; i < n; i++)
		{
			cout << setw(2) << shadow[i] << ' ';
			if (subOption != 11)
				cout << setw(2) << sample[i] << endl;
			else
				cout << setw(2) << B[i] << endl;
		}
	}
	
	else if (option == '2') {
		sort(runtime.begin(), runtime.end());

		cout << "Runtimes in Microseconds" << endl;

		if (runtime.size() <= 15)
		{
			for (int i = 0; i < (int)runtime.size(); i++)
				cout << setw(4) << runtime[i] << 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[] B;
	delete[] sample;
	delete[] shadow;
	
	return subOption;
}

int main() {
	while (true) {
		char line[128];

		cout << "Menu" << endl;
		cout << "1 Single Sorting 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)
			{
				int doSort = DoSort(line[0]);

				if (doSort == 12)
					break;
				else if (doSort == 13)
					exit(1);
			}
		}
	}

	return 0;
}

Sorting C++ Source Code by James Pate Williams, Jr.

#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;
    }
}