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.
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):
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.
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.