5
\$\begingroup\$

I'm learning about algorithms and have been recently experimenting with insertion sort via recursion in Python.

My code works fine, but I was wondering if there are any possible improvements that can be made. I am especially interested in ways to reduce the actual content of the code (i.e. make it shorter) or improve the speed.

def insertionsort(alist):
    i = len(alist)
    if i > 2:
        temp = alist[:i-1]
        insertionsort(temp)
        alist[:i-1] = temp[:i-1]

    k = len(alist) - 1
    m = len(alist)

    while k >= 1 and alist[k-1] > alist[k]:
        front = alist[k]
        back = alist[k - 1]
        alist[k] = back
        alist[k-1] = front

        k = k - 1


A = [4, 1, 6, 3, 9, 10]
insertionsort(A)

print(A)
\$\endgroup\$

migrated from stackoverflow.com Jul 24 '15 at 6:53

This question came from our site for professional and enthusiast programmers.

6
\$\begingroup\$

Starting with the low-hanging fruit: A variable called 'temp' is a big sign that you can do better. If you were to set up your code so that it returned a new list rather than modifying it in place, you could do this:

alist[:i-1] = insertionsort(alist[:i-1])

The rest of your code assumes that we will be working on the original, but the easiest fix for that is to make a copy at the earliest opportunity. If you do that early (and with an appropriate comment), and you don't need the original list anymore (you don't), then you can reuse the name alist without losing clarity. Unfortunately, copying the list is bad for performance, but readability needs to come first. But way down the bottom, I will point out a bigger improvement that will mean we don't actually have to choose between performance and readability here.


You can also eliminate that i: Python allows negative indices to all builtin sequences, which are defined to count from the back. So the above line is just:

alist[:-1] = insertionsort(alist[:-1])

and the condition above it can test against len(alist) explicitly.


In your second loop, you use four lines to swap two list elements. This can be more idiomatically done in one line using tuple assignment:

alist[k], alist[k-1] = alist[k-1], alist[k]

But we can do better even then this - we don't need to do all these swaps at all. Instead, find where the last element should go, and put it directly there. This is exactly the type of job the bisect module is good for:

candidate = alist.pop()
bisect.insort(alist, candidate)

And this replaces the whole second while loop.


So so far we have:

def insertionsort(alist):
    # work on a copy instead of the original
    alist = alist[:]

    if len(alist) > 2:            
        alist[:-1] = insertionsort(alist[:-1])

    candidate = alist.pop()
    bisect.insort(alist, candidate)

    return alist

A = [4, 1, 6, 3, 9, 10]
A = insertionsort(A)

print(A)

I said before that copying is potentially bad for performance (each copy takes time). And we're doing a lot of it. This line:

alist[:-1] = insertionsort(alist[:-1])

makes a new list containing all but the last element, which the recursive call will promptly clone (in its entirety). So that's two copies for each element after the second. It would be better if we could tell the recursive call to only treat up to a certain point in the list, and everything after that. To do this, we put the bulk of the code into a helper function:

def insertionsort(alist):
    def sort_helper(alist, hi):
        if hi > 1:            
            sort_helper(alist, hi-1)

        candidate = alist.pop(hi)
        bisect.insort(alist, candidate, hi=hi)

    alist = alist[:]
    sort_helper(alist, len(alist)-1)
    return alist

A = [4, 1, 6, 3, 9, 10]
A = insertionsort(A)

print(A)

Note that the first condition changed from testing a length to testing a position, and that the helper function works completely in-place. This makes one copy, in the outer function. You can also change it back to an in-place sort like your original code by deleting two lines, and it will make zero copies. This is probably the best a recursive insertion sort can be.

\$\endgroup\$
  • \$\begingroup\$ Thank you. I'm still unsure about the role of this helper function - could you please perhaps explain it more? \$\endgroup\$ – genesis Jul 24 '15 at 23:24
  • \$\begingroup\$ The helper function exists so that it can take an extra argument that it doesn't make sense to expose to the main function (because it's an implementation detail). The extra argument lets you partition the list into 'already sorted' and 'still unsorted' without copying it. It plays the same role as a loop variable in an iterative version. \$\endgroup\$ – lvc Jul 25 '15 at 0:27
  • \$\begingroup\$ Sure the code works? I tried it in Python with the helper function, doesn't seem to be sorting? \$\endgroup\$ – genesis Jul 25 '15 at 16:50
  • \$\begingroup\$ Because I forgot to update the test to reflect that it now returns the sorted list rather than sorting in-place. Fixed. \$\endgroup\$ – lvc Jul 26 '15 at 0:35
  • \$\begingroup\$ I like your intermediary version since it more or less mirrors the pseudo code of the selection sort. Can that be further refined to make it more intuitive? For e.g. I like the one for selection sort given at j.mp/recursiveSelectionSort. \$\endgroup\$ – lifebalance Jul 4 '17 at 21:52
5
\$\begingroup\$

A simple in-place, iterative version:

import bisect

def insertsort(l):
    for nsorted in range(1, len(l)):
        bisect.insort(l, l.pop(), hi=nsorted)

then, there are two ways one can think about a recursive version: a bottom-up one, where you grow the number of sorted elements from the left:

def bottomup_insertsort(l, nsorted=1):
    if nsorted >= len(l):
        return
    bisect.insort(l, l.pop(), hi=nsorted)
    bottomup_insertsort(l, nsorted + 1)

...and a maybe more elegant top-down version, where you call insertsort on a list after taking away the last element (inspired by lifebalance's approach, but in-place and returning None following typical Python conventions):

def topdown_insertsort(l):
    if len(l) > 1:
        candidate = l.pop()
        insertsort(l)
        bisect.insort(l, candidate)

All these approaches modify the list in-place, which is more efficient and less functional in style, since it obviously relies on side effects. Of course, depending on the point of the exercise one may prefer other solutions. For practical questions, of course, the wonderful list.sort() Timsort implementation is very very hard to beat.

\$\endgroup\$
  • \$\begingroup\$ Edited for a slightly more readable recursive version. \$\endgroup\$ – della Jul 6 '17 at 14:42
  • \$\begingroup\$ ...and edited again to pop from the right to use l.pop() which is cheaper than l.pop(idx). \$\endgroup\$ – della Jul 6 '17 at 14:50
  • \$\begingroup\$ In that case, if len(l) == 1: should also work? But nsorted == len(l) (number of sorted elements?) is more intuitive. \$\endgroup\$ – lifebalance Jul 6 '17 at 17:08
  • \$\begingroup\$ Thanks again! Python simply outshines other languages in how it closely merges into actual pseudo-code! \$\endgroup\$ – lifebalance Jul 6 '17 at 17:15
  • 1
    \$\begingroup\$ Came back on this after more than two years and I realized that lifebalance had a great point. Now there are two styles of recursive implementation in the answer. \$\endgroup\$ – della Sep 16 at 13:09
2
\$\begingroup\$

I further refactored Ivc's intermediary solution. This sure should satisfy OP's desire for shorter code!

import bisect 

def insertsort(L):
    if len(L) == 1:  
        return L

    candidate = L.pop()
    bisect.insort(insertsort(L), candidate)
    return L
\$\endgroup\$
  • \$\begingroup\$ Not just shorter, this is actually quite nice. It's a.but more than just a refactor of my intermediate code, since it works completely in place like the OPs code. As such, it should probably return None, which makes it a little shorter again by changing the first return L to just return, and remove the else and the second return. \$\endgroup\$ – lvc Jul 5 '17 at 11:52
  • \$\begingroup\$ Oh, see I what you mean...will put in those edits as suggested by you. \$\endgroup\$ – lifebalance Jul 5 '17 at 13:34
  • \$\begingroup\$ I had to put the return back, otherwise a run time error occurs. I did remove the else part \$\endgroup\$ – lifebalance Jul 5 '17 at 13:57
  • \$\begingroup\$ Thanks. A long time passed, but I edited my answer to include this elegant approach. However, my solution returns None as lvc was asking. \$\endgroup\$ – della Sep 16 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.