Insertion Sort is a much better sort than Bubble. Before we code, like before, let's take a look at the performance difference:

./sortingpractice.py 1234 23453
Beginning Bubble Sort . . . ( N =  1234 )
Bubble Sort finished in  0.17203855514526367 seconds
Beginning Merge Sort . . . ( N =  1234 )
Merge Sort finished in  0.001811981201171875 seconds
Beginning Insertion Sort . . . ( N =  1234 )
Insertion Sort finished in  0.0010004043579101562 seconds

Running the script only once, you can see that the difference between Insertion is actually better than Merge at n=1234. For smaller arrays, this is the case. As n gets larger, eventually merge sort is better than insertion sort.

From the insertion sort Wikipedia page:
To perform an insertion sort, begin at the left-most element of the array and invoke Insert to insert each element encountered into its correct position. The ordered sequence into which the element is inserted is stored at the beginning of the array in the set of indices already examined. Each insertion overwrites a single value: the value being inserted.

In other words, we take an element, and start looking at the left side of the array. If the element is smaller, leave it. Otherwise, check the next one.

Now, let's get to the implementation! 

Insertion sort is relatively small, in comparison to merge sort.

def insertSort(arr):
    start = time.time()
    print('Beginning Insertion Sort . . . ( N = ', len(arr), ')')
    for idx in range (1, len(arr)):
        target = idx
        while target > 0 and arr[target-1] > arr[target]:
            arr[target-1] = arr[target]
            target =- 1
        idx =+ 1
    end = time.time()
    print('Insertion Sort finished in ', end-start ,'seconds')

Just like the algorithm above says, we want to take the number at the current index in the array (target), and check it against the first numbers in the array. Once there's a number to the left of the target index that's lower than the current number, we just drop the number in the new index.

You can find the source code on GitHub.

Tags
Category