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.

2015 InsertionSort_1.png

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

2015 InsertionSort_2.png

2015 InsertionSort_3.png

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

2015 InsertionSort_4.png

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

2015 InsertionSort_5.png

2015 InsertionSort_6.png

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

2015 InsertionSort_7.png

2015 InsertionSort_8.png

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

2015 InsertionSort_9.png

2015 InsertionSort_10.png

2015 InsertionSort_11.png

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:

2015 InsertionSort_12.png

2015 InsertionSort_13.png

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

2015 InsertionSort_14.png

Doing a test

2015 InsertionSort_15.png

2015 InsertionSort_16.png

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

2015 InsertionSort_17.png

... testing with a larger example

2015 InsertionSort_18.png

2015 InsertionSort_19.png

2015 InsertionSort_20.png

2015 InsertionSort_21.png

2015 InsertionSort_22.gif

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

2015 InsertionSort_23.png

2015 InsertionSort_24.png

2015 InsertionSort_25.png

2015 InsertionSort_26.gif

2015 InsertionSort_27.png

2015 InsertionSort_28.png

Having a closer look at the fitted function we recognize, that the coefficient for 2015 InsertionSort_29.png is about 2015 InsertionSort_30.png. But x varies from 0 to 1000, so x squared is 2015 InsertionSort_31.png. But the coefficient for x is 2015 InsertionSort_32.png so for x=1000 we hat a value about 2015 InsertionSort_33.png. 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:

2015 InsertionSort_34.png

2015 InsertionSort_35.png

2015 InsertionSort_36.png

2015 InsertionSort_37.gif

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

2015 InsertionSort_38.png

2015 InsertionSort_39.png

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

2015 InsertionSort_40.png

A short test:

2015 InsertionSort_41.png

2015 InsertionSort_42.png

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

2015 InsertionSort_43.png

Here, too, a short test

2015 InsertionSort_44.png

2015 InsertionSort_45.png

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

2015 InsertionSort_46.png

2015 InsertionSort_47.png

2015 InsertionSort_48.png

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

2015 InsertionSort_49.png

2015 InsertionSort_50.png

2015 InsertionSort_51.gif

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

2015 InsertionSort_52.png

2015 InsertionSort_53.gif

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


2015 InsertionSort_54.png

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

2015 InsertionSort_55.png

2015 InsertionSort_56.png

Created with the Wolfram Language