Structures

A shape which draws the numbers in an array of integers as lines.

The area to draw is adjusted to the Rect in the parameter to the path function. Line lengths are adjusted to the range of numbers so that the largest (abs) value determines the length of the tallest line. Line width is also calculated based on the number of lines to draw adjusted to the available space.

The main view of the app.

The view displays, depending on the state of the SortCoordinator:

• either the animation of the sorting being executed, or
• the timing results of the “real” algorithms being executed.

Tapping the view starts the animation, executing all the supported sorting algorithms. After the animations are done, the same algorithms are again executed without animations nor delays. Execution time is measured and then displayed as each algorithm finishes. After this, user can restart the whole thing again by tapping the screen.

Implementation of the Bubble sort algorithm.

Bubble sort performs poorly in real world use and is used primarily as an educational tool. Note that using very large arrays slows down the sorting using BubbleSort considerably.

See https://en.wikipedia.org/wiki/Bubble_sort

Heapsort is an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region.

Unlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure (binary tree) to more quickly find the largest element in each step.

Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort.

See https://en.wikipedia.org/wiki/Heapsort

LampSort implements the non-recursive version of QuickSort.

The algorithm uses two stacks to keep lower and higher indexes between which sorting happens, and sorts these ranges. See the animation in action on how this method behaves.

For more information, see e.g. https://medium.com/concerning-pharo/lampsort-a-non-recursive-quicksort-implementation-4d4891b217bd

Block sort, or block merge sort, is a sorting algorithm combining at least two merge operations with an insertion sort to arrive at O(n log n) in-place stable sorting. It gets its name from the observation that merging two sorted lists, A and B, is equivalent to breaking A into evenly sized blocks, inserting each A block into B under special rules, and merging AB pairs.

WikiSort by Mike McFadden is an implementation of “block merge sort”, which is a stable merge sort based on the work described in “Ratio based stable in-place merging”, by Pok-Son Kim and Arne Kutzner. It’s generally as fast as a standard merge sort while using O(1) memory, and can be modified to use additional memory optionally provided to it which can further improve its speed.

The implementation here is a Swift port of Java implementation by Mike McFadden in https://github.com/BonzaiThePenguin/WikiSort/blob/master/WikiSort.java

For details and commented code, see the original Java version.

Note that the Java version has a Range class, here we are using the Swift Range<Int> instead.

Native Swift sort in Foundation library is Tim sort.

This class here uses it just in the end of the demo, sorting a large array without animation.

One could take the source code for the library implementation and restructure it so that it can be executed step by step as the other sort methods implemented here. Then this could also be animated. This is left as an exercise to the reader.

Radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix.

For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered.

For this reason, radix sort has also been called bucket sort and digital sort.

This method implements the LSD algorithm (Least Significant Digit). Implementation has places for optimization, exercise left for the reader.

The algorithm is a port from code implemented in another language from Stackoverflow. See comment on realAlgorithm() for details.

Implements the Shell sort algorithm. Shell sort is an in-place comparison sort.

Sorting is done one “gap” at a time. A gap can be thought of as a number of interleaved lists, each individually sorted.

In this implementation, gap is taken to be the middle point of the array to sort.

Note that this method uses the SwappedItem Operation.move rather than Operation.swap – it moves the value in the first number to the index specified in the second number in SwappedItems. Using .swap operation is more common in the current implementations, as .move is used currently only by ShellSort.

See https://en.wikipedia.org/wiki/Shellsort

Records the timing of sort methods executed in a tight loop. The results are shown in the UI after animating the results.

Structure defining the operation when sorting an Int array. There are two kinds of operations. You can either swap the values, indicated by the indexes first and second. Or you can move the value in first variable to the index specified by the second index value. currentIndex1 and currentIndex2 are indexes to the array the sorting method is currently “keeping focus on”. These are drawn as small circles in the centerline of the numbers.

A Stack data structure, implementing Stackable protocol.

The view displaying the results from executing the “real” sorting algorithms without the delays caused by the animations and step by step execution of the algorithms.