Insertion Sort—Python

Insertion sorts are a common sorting technique that many computer science students are asked to learn. Here is a Python implementation of an Insertion Sort.

def insertion_sort(items):
    for i in range(2, len(items) - 1):
        item = items[i]
        j = i
        while (items[j - 1] > item) and (j >= 1):
            items[j] = items[j - 1]
            j -= 1
        items[j] = item

if __name__ == '__main__':
    items = ['Bob Belcher', 'Linda Belcher', 'Tina Belcher', 'Gene Belcher', 'Louise Belcher']
    print(items, '\n')

    print('Sorting...')
    insertion_sort(items)
    print(items)

Insertion sorts use nested loops and test if an item at the end of the list is less than an item in the front of the list. If they are, the code does a swap.

When run, we get this output:

['Bob Belcher', 'Linda Belcher', 'Tina Belcher', 'Gene Belcher', 'Louise Belcher'] 

Sorting...
['Bob Belcher', 'Gene Belcher', 'Linda Belcher', 'Tina Belcher', 'Louise Belcher']
Advertisements

2 thoughts on “Insertion Sort—Python”

  1. I had a few queries:

    1. Why did your range start from 2?
    2. You are taking strings here. 1D strings. What if they were 2D and how will you sort that? Like be it any format (strings or int values). Is sorting for 2D lists possible?

    Like

    1. We start at 2 because of the nested loop. You’ll notice that the variable j starts at i on line 4. Then on line 5, we have j – 1, followed by j – j again on line 6. If we started at 1 rather than two, we would end up with a negative index on line 6, but by starting at 2, we end up at 0, which is the start of the list.

      It is possible to sort 2D lists. However, you have to decide what a sorted 2D list looks like. Do you sort by columns or rows first? I’ll do a post on this topic since it’s more involved.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s