Implementation of Insertion Sort Algorithm in python

Question

I was trying to implement the insertion sort algorithm in python and was able to code it as below, I am not getting the whole array sorted and was wondering if this implementation has the proper thought process behind it, if not I would greatly appreciate if someone can help me in understanding it as the function is considering the sorted part of the array when inserting an element from the unsorted part. Also, in your review kindly consider if the implementation is correct and if so what can make my solution output correct.

def insertion_sort(array):
    for i in range(1, len(array)):
        for j in reversed(range(1, i)):
            if array[j-1] > array[j]:
                temp = array[j-1]
                array[j-1] = array[j]
                array[j] = temp
    return array

to_sort = [4, 3, 1, 5, 6, 2]
print(insertion_sort(to_sort))

This is the output I got: [1, 3, 4, 5, 6, 2]

tl;dr: Insertion Sort algorithm not giving perfect output. Is implementation correct and what can be done to fix the output.

trincot · Accepted Answer · 2022-07-15 06:18:21Z

The goal of your function would be to shift array[i] into the sorted partition, but it actually does that for array[i-1], because the inner loop starts with j equal to i-1.

So the easy fix is to change:

    for j in reversed(range(1, i)):

to:

    for j in reversed(range(1, i + 1)):

Improvements

More Pythonic would be to use the capability of range to produce a descending range:

    for j in range(i, 0, -1):

When the if condition is not true, it is useless to continue the inner loop, as then it is guaranteed that the if condition will never be true in the rest of the inner loop's iterations. So add a break:

        if array[j-1] <= array[j]:
            break
        temp = array[j-1]
        array[j-1] = array[j]
        array[j] = temp

As these swaps will always move the same value to the left, i.e. array[j] will always be the value that originally was at array[i], it is less costly to first find the index where array[i] should be moved to, and then perform a single rotation to get it there.

def insertion_sort(array):
    for i in range(1, len(array)):
        temp = array[i]
        for k in range(i - 1, -1, -1):
            if array[k] <= temp:
                break
        else:
            k = -1
        # rotate
        array[k+2:i+1] = array[k+1:i]
        array[k+1] = temp
    return array

I used k here, so not to confuse it with the meaning of j in the original code: k is j - 1.

This search for k (or j) can be done with a call to next:

def insertion_sort(array):
    for i in range(1, len(array)):
        temp = array[i]
        j = 1 + next((k for k in range(i - 1, -1, -1) if array[k] <= temp), -1)
        array[j+1:i+1] = array[j:i]
        array[j] = temp
    return array

This is precisely what I was looking for, it turns out understanding what you write down in code is as important as coding a solution.

ThePunisher · Accepted Answer · 2022-07-14 23:35:37Z

1

You are never touching the last element of the array, I suggest changing len(array) with len(array)+1, i.e.,

def insertion_sort(array):
    for i in range(1, len(array)+1):
        for j in reversed(range(1, i)):
            if array[j-1] > array[j]:
                temp = array[j-1]
                array[j-1] = array[j]
                array[j] = temp
    return array

This is because i has maximum value len(array)-1 and j has as maximum value i-1, which is len(array)-2. However, the last element in the array has index len(array)-1.

answered Jul 14, 2022 at 23:35

ThePunisher

2162 silver badges7 bronze badges

1 Comment

Blckknght Over a year ago

I think putting the +1 on the second loop is better. The first iteration of the outer loop in your code is wasted, since range(1, 1) is empty. Using i+1 in the second loop doesn't have any wasted iterations.

Collectives™ on Stack Overflow

Implementation of Insertion Sort Algorithm in python

2 Answers 2

Improvements

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Improvements

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related