15 Sorting Algorithms in 6 Minutes in C++

/******************************************************************************
 * src/SortAlgo.cpp
 *
 * Implementations is many sorting algorithms.
 *
 * Note that these implementations may not be as good/fast as possible. Some
 * are modified so that the visualization is more instructive.
 *
 * Futhermore, some algorithms are annotated using the mark() and watch()
 * functions from WSortView. These functions add colors to the illustratation
 * and thereby makes the algorithm's visualization easier to explain.
 *
 ******************************************************************************
 * The algorithms in this file are copyrighted by the original authors. All
 * code is freely available.
 *
 * The source code added by myself (Timo Bingmann) and all modifications are
 * copyright (C) 2013-2014 Timo Bingmann <[email protected]>
 *
 * This program is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation, either version 3 of the License, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 * more details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program.  If not, see <http://www.gnu.org/licenses/>.
 *****************************************************************************/

#include "SortAlgo.h"

#include <algorithm>
#include <numeric>
#include <limits>
#include <inttypes.h>

typedef ArrayItem value_type;

// inversion count limit for iterator instrumented algorithms
const unsigned int inversion_count_instrumented = 512;

const struct AlgoEntry g_algolist[] =
{
    { _("Selection Sort"), &SelectionSort, UINT_MAX,
      wxEmptyString },
    { _("Insertion Sort"), &InsertionSort, UINT_MAX,
      wxEmptyString },
    { _("Binary Insertion Sort"), &BinaryInsertionSort, UINT_MAX,
      wxEmptyString },
    { _("Merge Sort"), &MergeSort, 512,
      _("Merge sort which merges two sorted sequences into a shadow array,"
        "and then copies it back to the shown array.") },
    { _("Quick Sort (LR ptrs)"), &QuickSortLR, UINT_MAX,
      _("Quick sort variant with left and right pointers.") },
    { _("Quick Sort (LL ptrs)"), &QuickSortLL, UINT_MAX,
      _("Quick sort variant from 3rd edition of CLRS: two pointers on left.") },
    { _("Quick Sort (ternary, LR ptrs)"), &QuickSortTernaryLR, UINT_MAX,
      _("Ternary-split quick sort variant, adapted from multikey quicksort by "
        "Bentley & Sedgewick: partitions \"=<?>=\" using two pairs of pointers "
        "at left and right, then copied to middle.") },
    { _("Quick Sort (ternary, LL ptrs)"), &QuickSortTernaryLL, UINT_MAX,
      _("Ternary-split quick sort variant: partitions \"<>?=\" using two "
        "pointers at left and one at right. Afterwards copies the \"=\" to middle.") },
    { _("Quick Sort (dual pivot)"), &QuickSortDualPivot, UINT_MAX,
      _("Dual pivot quick sort variant: partitions \"<1<2?>\" using three pointers, "
        "two at left and one at right.") },
    { _("Bubble Sort"), &BubbleSort, UINT_MAX,
      wxEmptyString },
    { _("Cocktail Shaker Sort"), &CocktailShakerSort, UINT_MAX,
      wxEmptyString },
    { _("Gnome Sort"), &GnomeSort, UINT_MAX,
      wxEmptyString },
    { _("Comb Sort"), &CombSort, UINT_MAX,
      wxEmptyString },
    { _("Shell Sort"), &ShellSort, 1024,
      wxEmptyString },
    { _("Heap Sort"), &HeapSort, UINT_MAX,
      wxEmptyString },
    { _("Smooth Sort"), &SmoothSort, 1024,
      wxEmptyString },
    { _("Odd-Even Sort"), &OddEvenSort, 1024,
      wxEmptyString },
    { _("Bitonic Sort"), &BitonicSort, UINT_MAX,
      wxEmptyString },
    { _("Cycle Sort"), &CycleSort, UINT_MAX,
      wxEmptyString },
    { _("Radix Sort (LSD)"), &RadixSortLSD, 512,
      _("Least significant digit radix sort, which copies item into a shadow "
        "array during counting.") },
    { _("Radix Sort (MSD)"), &RadixSortMSD, UINT_MAX,
      _("Most significant digit radix sort, which permutes items in-place by walking cycles.") },
    { _("std::sort (gcc)"), &StlSort, inversion_count_instrumented,
      wxEmptyString },
    { _("std::stable_sort (gcc)"), &StlStableSort, inversion_count_instrumented,
      wxEmptyString },
    { _("std::sort_heap (gcc)"), &StlHeapSort, inversion_count_instrumented,
      wxEmptyString },
    { _("Tim Sort"), &TimSort, inversion_count_instrumented,
      wxEmptyString },
    { _("Block Merge Sort (WikiSort)"), &WikiSort, inversion_count_instrumented,
      _("An O(1) place O(n log n) time stable merge sort.") },
    { _("Bogo Sort"), &BogoSort, UINT_MAX,
      wxEmptyString },
    { _("Bozo Sort"), &BozoSort, UINT_MAX,
      wxEmptyString },
    { _("Stooge Sort"), &StoogeSort, inversion_count_instrumented,
      wxEmptyString },
    { _("Slow Sort"), &SlowSort, inversion_count_instrumented,
      wxEmptyString }
};

const size_t g_algolist_size = sizeof(g_algolist) / sizeof(g_algolist[0]);

const struct AlgoEntry* g_algolist_end = g_algolist + g_algolist_size;

// ****************************************************************************
// *** Selection Sort

void SelectionSort(WSortView& A)
{
    volatile ssize_t jMin = 0;
    A.watch(&jMin, 3);

    for (size_t i = 0; i < A.size()-1; ++i)
    {
        jMin = i;

        for (size_t j = i+1; j < A.size(); ++j)
        {
            if (A[j] < A[jMin]) {
                A.mark_swap(j, jMin);
                jMin = j;
            }
        }

        A.swap(i, jMin);

        // mark the last good element
        if (i > 0) A.unmark(i-1);
        A.mark(i);
    }
    A.unwatch_all();
}

// ****************************************************************************
// *** Insertion Sort

// swaps every time (keeps all values visible)
void InsertionSort(WSortView& A)
{
    for (size_t i = 1; i < A.size(); ++i)
    {
        value_type key = A[i];
        A.mark(i);

        ssize_t j = i - 1;
        while (j >= 0 && A[j] > key)
        {
            A.swap(j, j+1);
            j--;
        }

        A.unmark(i);
    }
}

// with extra item on stack
void InsertionSort2(WSortView& A)
{
    for (size_t i = 1; i < A.size(); ++i)
    {
        value_type tmp, key = A[i];
        A.mark(i);

        ssize_t j = i - 1;
        while (j >= 0 && (tmp = A[j]) > key)
        {
            A.set(j + 1, tmp);
            j--;
        }
        A.set(j + 1, key);

        A.unmark(i);
    }
}

README - Source Code Overview and Implementation Notes

The demo program uses the wxWidgets toolkit for cross-platform dialogs and painting. For sound output, the audio component of the cross-platform SDL library is used.

All sources resides in src/. The main window's GUI functions are grouped in WMain.h/cpp. The sorting visualization, including the instrumented array class and painting methods are in WSortView.h/cpp.

SortAlgo.h/cpp contains all sorting algorithms. These were mainly modified to operate on a WSortView object, which exposes most of the usual array operators such as operator[], and many special functions to create nicer visualizations. Most notable among these, are a special swap() function and mark() to colorize bars. There is also watch() to do live tracking of indexes stored as local variables (use this with care)!

Comparison counting and sound effects are signaled by the operators of ArrayItem, which is the item class of the instrumented array WSortView. As such, all comparisons of the sorting algorithms will be intercepted by this class.

On each comparison, the values are used to generate sound. All sound generating methods are in SortSound.cpp. The main class here is an Oscillator, which generates an enveloped triangular waveform of a specific frequency. Oscillators are mixed together for the output sound. The output volume is scaled automatically depending on the number of oscillators active.

For (somewhat) rapid development with wxWidgets, the wxGlade dialog generator tool is use. The public version of the Sound of Sorting contains no recording facilities. If you want to contribute a sorting algorithm, please notify me.

ChangeLog

2014-05-15 - v0.6.5

New sorting algorithms: Binary-Search Insertion Sort, Block Merge Sort (WikiSort), Cycle Sort, Dual-Pivot Quick Sort.
Displaying current number of inversions and runs in array.
Microseconds delay on Win32 using QueryPerformanceCounter().

2013-11-26 - v0.6.3

New sorting algorithms: TimSort, StoogeSort and Slowsort
Renaming array from a to A for easier reading and matching to SoS-Cheatsheet.
Fixed compilation with older compilers and on Mac OS X.
Added random algorithm button.

Download more : https://panthema.net/2013/sound-of-sorting/

<br>

Source : https://panthema.net/2013/sound-of-sorting/

*Beware click the link!