CODEWITHSUNDEEP
algorithmpython-3.xoptimizationinsertion-sort
Maximillion Billiony
Maximillion Billiony

Reputation: 40

Making "Insertion sort" algorithm more efficient - Python 3.5.2

I've attempted coding the insertion sort algorithm in python -

def insertion(list):
    checked = 2
    while (checked <= len(list)):
        for i in range(checked-1):
            if list[checked-1] < list[i]:
                list.insert(i, list[checked-1])
                del list[checked]
        checked+=1
    return list

I measured the time it took to perform a 1000 item sort - 106.08099999999997 thousandths of a second

I found this to be rather slow since -

def bubbleSort(alist,n):
    for j in range(1,n):
        nextnum = alist[j]
        i = j - 1
        while i>=0 and alist[i]>nextnum:
            alist[i + 1] = alist[i]
            i = i - 1       
        alist[i + 1] = nextnum

Only took - 83.71800000000007 thousandths of a second

Is there any way I could make my code more efficient / would I have to use a different code? If so, which insertion sort implementation is the quickest in python? I'm aware that insertion sort isn't usually the best algorithm to use. This is just for my school work, so that I can understand the algorithms we learn better.

Upvotes: 0

Views: 2670

Answers (1)

Mark Tolonen
Mark Tolonen

Reputation: 177610

Inserting and deleting from a list is more expensive than just swapping the contents of locations. This is faster than the bubble sort:

def insertion(M):
    for i in range(1,len(M)):
        for j in range(i):
            if M[i] < M[j]:
                M[j],M[j+1:i+1] = M[i],M[j:i]
                break

Note this uses the "swap" syntax of a,b = b,a which swaps the checked value to the insertion location and swaps the remaining values ahead one in the list. Also, once the swap is made, break from the inner loop. No need to continue checking for the insertion location. You could also check that the value to be swapped is already greater than or equal to the previously sorted values with the following and skip the inner loop when true:

def insertion(M):
    for i in range(1,len(M)):
        if M[i] >= M[i-1]:
            continue
        for j in range(i):
            if M[i] < M[j]:
                M[j],M[j+1:i+1] = M[i],M[j:i]
                break

Upvotes: 3

Related Questions