Making "Insertion sort" algorithm more efficient - Python 3.5.2

Question

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.

1. How did you "measure" ? did you do it properly with timeit ? 2. if you want an efficient sorting algorithm don't use O(n^2) algorithms: use merge or quicksort. And if you know the range of the numbers you might be able to achieve linear time with radix or bucket sort — Nir Alfasi
– Nir Alfasi, Commented Nov 11, 2017 at 18:05
I just used time.clock(). It may not be accurate, but it's just to prove that it's slower than the other code. Again, as I've stated at the bottom, this is just for school work. I'm not looking for the most efficient algorithm, but thank you for the advice. — Maximillion Billiony
– Maximillion Billiony, Commented Nov 11, 2017 at 19:04

Mark Tolonen · Accepted Answer · 2017-11-11 19:11:52Z

3

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

answered Nov 11, 2017 at 19:11

Mark Tolonen

181k26 gold badges182 silver badges278 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Maximillion Billiony Over a year ago

I see, this is very helpful, thank you so very much! I think I can apply these techniques to make my other algorithms more efficient as well! Update - You cut the time to 40% of the original!

Collectives™ on Stack Overflow

Making "Insertion sort" algorithm more efficient - Python 3.5.2

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related