Sorting Algorithms with Mathematica (still under construction)

Sorting is one of the fundamental algorithmic problems to be solved with a variety of different algorithms. Some of them are covered here. Especially they are analyzed in terms of their run-time-behavior. Besides this wo look at different implementations (in Mathematica) and how the specific implementation influences the run-time of the algorithms.

This section deals with various sorting algorithms implemented in different ways in Mathematica. We here investigate the time-complexity of the implemented sorting algorithms. One my ask why to do this,because these algorithms are well known and coded hundreds of times. All true, but nevertheless my own experience is, that it is easy to implement for instance a merge sort algorithm, which is easy to code (especially in Mathematica), but is by no way sure that the coded and tests algorithm has the desired complexity, in this case an n Log(n) complexity.

There are a lot of traps and pitfalls (a lot of them a got to know), and I will show a few of them. Since sorting of long lists may be a time consuming job I stored a lot of calculated sorting times in a Dataset, a special structure within Mathematica, so the data can be used to visualize the results of different algorithms. As usual (for me) the code is optimized for readability and not for compactness.

The Dataset of timing results

First we go into the structure of the Dataset used to store the sorting results. The structure of this dataset is simple, it consists of the following entries (keys):


  1. length: The length of the list which was sorted
  2. time: run time to sort the list
  3. algorithm: name of the algorithm used
  4. machine: machine on which the result was computed

The entry for machine actually ist mostly „MacBookAir“, or “MacBokkPro“, my working machines. this entry is for „future reference“. Maybe I do some comparison between different machines…

The sorting notebook need a package calls „sortingUtilities“. This package, written in Wolfram Language, contains exactly that, utilities e.g. for determination of rund-time, plotting results, etc. etc. The package can be downloaded here

Download Notebook

My Image

Bubble Sort

The first algorithm to be analyzed is the well known bubble sort. The first implementation is straightforward with two Do-loops. We count the number of exchange operations and doe a run time analysis. This shows, as expected, a quadratic complexity.
Next we compare this implementation with another one with two For-loops. this shows that the run-time with For-loops is a bit greater than with Do-loops.
Lastly we implement this algorithm with a rule-based (repeated replacement) and a recursive approach. These implementations are very clear, but, of course, have poor performance.
The overall picture is shown here on the right side of this page.

My Image

Download


Insertion Sort

The next algorithm to be analyzed is the insertionSort algorithm. This algorithm inserts a new element in a sorted list, like some people do when taking cards from a card deck. This algorithm is also very simple and has a quadratic complexity in time.
I have implemented two versions, one uses the Mathematica Command Position to determine the position where to insert the new element, the other uses a „homegrown“ myPosition, to avoid the usage of the build in function. The results show, as expected, that the usage of the build in functions leads to a better performance.
But as one can see in the picture to the right of this text, insertionSort is by far better than bubbleSort.
.

Download


Open Notebook in Browser
PDF
Notebook
Stacks Image 4508
RapidWeaver Icon

Made in RapidWeaver