Insertion Sort

We are going to implement the well known algorithm insertion sort. The first step is the insertion of an element in an sorted list. This can be done with at variety of different approaches.

First we do so by working out an example. Suppose we have the already sorted list sorted as:

Now we are going to insert another element, in this list

We do so by going through the list and searching for an element greater than the element to be inserted, and place the new element then in the appropriate place.

The position where the insertion should take place can easily be determined with the help of the Mathematica Position command

The output says that the elements at the positions pointed out in pos are greater than the element to be inserted, so we have to insert the element before the first found position

But what, if the element to be inserted is greater than all of the elements in the sorted list?

So no position could be found at which an element greater than the to be inserted element exist. Therefore in this case the element has to be inserted at the end of the list:

So we can define a function insert which inserts an element in a sorted list

Doing a test

O.K:, this looks good, so ... now putting the pieces together...

... testing with a larger example

It is easy to guess that we here have a quadratic behaviour, so we try a quadratic fitting at first

Having a closer look at the fitted function we recognize, that the coefficient for is about . But x varies from 0 to 1000, so x squared is . But the coefficient for x is so for x=1000 we hat a value about . This shows that we have indeed a pure quadratic model. but the coefficient ag the linear term shows, that the dependency should be purely quadratic, so we give that a try:

This looks good. A comparison with a formerly defined BubbleSort shows that the insertion sort we defined here is by far superior to the bubble sort. We therefore use a convenience function to extract the timing data from a dataset

So, by the way: Do not use bubbleSort!

The conjecture is, that this is due to the usage of the build in function Position, we used in the implementation of insertionSort. So we make an implementation with a (o.k. quick and dirty) function myPosition which determines the position where the new element has to be inserted (this also could be done via the Mathematica function Scan, but here we use elementary functions).

A short test:

Good. Now we can simply make a new function insert which uses our “new” myPosition function.

Here, too, a short test

Now for the definition of an insertion sort with a “home made” position:

O.k. it works, now for the timing:

As expected we experience a far better performance with the build in function Position, than with the “home made” myPosition.  So we compare the algorithms directly

This shows that insertion sort, even with a “self-made” part, is better than bubble sort.

Init

To determine the timing of an algorithm we use the following function:

We have a lot of results for various sorting algorithms in a dataset, this is now read in (we have to look at different locations, depending on the machine we use):