Category: Sorting Algorithms

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

Word to Word Game by James Pate Williams, Jr.

I implemented a computerized version of a game similar to the board game Boggle. Given a jumble of letters find as many words as possible. Suppose we have the jumbled letters “sldfie” then my C++ program outputs:

Now suppose the scrambled letters are “nifrsmo”:

The program uses permutations and power sets. All permutations of the set of three numbers 1, 2, and 3 are:

123 132 213 231 312 321

The total number of permutations of n objects is n! where n! = n * (n – 1) * … * 2 * 1. So we have 3! = 3 * 2 * 1 = 6 and 4! = 4 * 3 * 2 * 1 = 24.


A power set of three objects can generated by using the binary representation of all binary numbers 0 to 2 * 2 * 2 – 1 = 8 – 1 = 7.

0 = 000, 1 = 001, 2 = 010, 3 = 011, 4 = 100, 5 = 101, 6 = 110, and 7 = 111

My main C++ function in the implementation is as follows:

vector<string> PowerSet(char cstr[], int len)
{
    vector<int> index;
    vector<string> match;

    for (long ps = 0; ps <= pow(2, len); ps++)
    {
        string str = ConvertBase2(cstr, ps, len);
        int psf = 1;

        for (int i = 2; i <= len; i++)
            psf *= i;

        for (int i = 0; i < psf; i++)
        {
            if (binary_search(dictWords.begin(), dictWords.end(), str))
            {
                if (!binary_search(match.begin(), match.end(), str))
                {
                    match.push_back(str);
                    sort(match.begin(), match.end());
                }
            }

            next_permutation(str.begin(), str.end());
        }
    }

    return match;
}

More Tests of two Selection Sort Implementations

In our last blog we introduced two algorithms for implementing the selection sort which differed by the number of swap operations involved. The two required the same number of comparisons n * (n – 1) / 2 = 45 for n = 10, where n is the length of the array to be sorted and different number of swaps. We notice about a two-fold speed up in sorting using the minimal number of swaps version. Also make sure the number of swaps is implemented by a 64-bit integer since 100,000 * 99,999 = 9,999,899,999 which overflows a 32-bit integer. I learned about overflow while trying to sort large arrays of integers.

Who Knew? Better Code for Selection Sort

I have been using inferior code for the Selection Sort since 1979. Last night I found the more efficient pseudo code:

Data Structure and Algorithms Selection Sort – Tutorialspoint

Here is my old code for the Selection Sort in C#:

Old Code for the Algorithm

And my new code from the more efficient pseudo code found online:

New and Better Code
Common Swap Function (Procedure)

Both implementations require n * (n – 1) / 2 comparisons which for an array of length 15 is 15 * 14 /2 = 15 * 7 = 105. The second implementation requires typically fewer calls to the swap function.

Selection Sort Test 15-Element Random Array
Selection Sort Test 15-Element Reverse Ordered Array
Selection Sort Test 15-Element Sorted Array

The first number after the unsorted array is the number of comparisons which is always 105 in our 15-element test cases. The second number is the tally of the swap function calls.

Singleton’s Sorting Algorithm 1979 and 2018 by James Pate Williams, Jr., BS, BS, MSwE, PhD

I first implemented Singleton’s sorting algorithm in the Summer of 1979. The programming language was Data General’s version of Dayton BASIC (Beginner’s All-purpose Symbolic Instruction Code). This variant of BASIC was interpretive like C#, Java, and Pascal. Below is my BASIC version and run-times for double precision numbers in an inverted sequence.

Summer of 1979 BASIC Singleton’s Sorting Algorithm

Zoom forward to my current computer and C# programming language in 2018.

C# Singleton’s Sorting Algorithm 2008 – 2018 Random Lists of Double Precision Numbers

Two of My Many Sorting Algorithms Implementations by James Pate Williams, Jr. BA, BS, MSwE, PhD

A recurring theme in my life has been to implement and re-implement the sorting algorithms found in Harold Lorin’s treatise Sorting and Sort Systems and Thomas H. Corman et al.’s Algorithms. I purchased a copy of Lorin’s book in the summer of 1979 and Corman’s textbook in 1999 or 2000. This has been good exercise in translating from one computer language to a later and greater newer computer language. I began in BASIC and FORTRAN IV and transitioned to C, C++, C#, Common LISP, Java, Modula-2, Pascal, and Scheme in alphabetic not chronological order. In this blog we cover two C# applications, one from October 26, 2010, named Sorting Comparisons and the other from January 17, 2015, with the moniker Sorting.

In the Sorting Comparisons application, we compare the sorting algorithms: Heap Sort, Quick Sort, and Singleton’s Sort. The first two algorithms are from the Algorithms tome and Singleton’s Sort is from Lorin’s treatment. These are some of the fastest general purpose sorting algorithms available in my particular arsenal.

Sorting Comparisons Test All 16Sorting Comparisons Time All 1000Sorting Comparisons Time All 10000Sorting Comparisons Time All 100000Sorting Comparisons Time All 1000000

Sorting Comparisons Source Code

https://code.msdn.microsoft.com/windowsdesktop/Tests-of-Six-Sorting-94aa6fd0?redir=0