Implementation of Insertion Sort Algorithm in python-CodePudding

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.

CodePudding user response：

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.

CodePudding user response：

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