How does Python insertion sort work?

Question

Here's a Python implementation of insertion sort, I tried to follow the values on paper but once the counting variable i gets bigger than len(s) I don't know what to do, how/why does it still run?

def sort_numbers(s):
    for i in range(1, len(s)):
        val = s[i]
        j = i - 1
        while (j >= 0) and (s[j] > val):
            s[j+1] = s[j]
            j = j - 1
        s[j+1] = val

def main():
    x = eval(input("Enter numbers to be sorted: "))
    x = list(x)
    sort_numbers(x)
    print(x)

Answer 1

Or, this one:

def ins_sort(k):
    for i in range(1,len(k)):    #since we want to swap an item with previous one, we start from 1
        j = i                    #create i's copy (or not)
        temp = k[j]              #temp will be used for comparison with previous items, and sent to the place it belongs
        while j > 0 and temp < k[j-1]: #j>0 bcoz no point going till k[0] since there is no seat available on its left, for temp
            k[j] = k[j-1] #Move the bigger item 1 step right to make room for temp
            j=j-1 #take k[j] all the way left to the place where it has a smaller/no value to its left.
        k[j] = temp
    return k

Answer 2

Consider [3, 2, 1]

The loop starts with 3. Since it is the first item in the list there is nothing else to do.

[3, 2, 1]

The next item is 2. It compares 2 to 3 and since 2 is less than 3 it swaps them, first putting 3 in the second position and then placing 2 in the first position.

[2, 3, 1]

The last item is 1. Since 1 is less than 3 it moves 3 over.

[2, 3, 3]

Since 1 is less than 2 it swaps moves 2 over.

[2, 2, 3]

Then it inserts 1 at the beginning.

[1, 2, 3]

Answer 3

To see how that implementation works, check it out visualized here: http://goo.gl/piDCnm

However, here is a less confusing implementation of insertion sort:

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

Answer 4

a recursive implementation

def insert(x, L):
    if [] == L:      return [x]
    elif x <= L[0]:  return [x] + L
    else:            return [L[0]] + insert(x,L[1:])

def insertion_sort(L):
    if [] == L:  return []
    else:        return insert(L[0], insertion_sort(L[1:]))

# test
import random

L = [random.randint(1,50) for _ in range(10)]

print L
print insertion_sort(L)

Answer 5

If we consider an array from left to right [LeftMost, ..., RightMost], an insertion sort performs the following procedure for each item:

1. Get the current value i.
2. Get the value j (where j = i-1 in the first iteration, or basically the first element to the left of i). In the first iteration of the while array[i] and array[j] are to consecutive elements. For example, if array = [... 60, 100, 50, ...], and array[i] is 50, then array[j] is 100.
3. If the previous value is greater than the current one, then it swaps the two values. Basically if you had something like [..., 60, 100, 50, ...] before this operation takes place, you will end up with [..., 60, 50, 100, ...]. The idea is that you move each item i left as long as there are elements to the left of it that are lower.

   This is the key of the sort algorithm. Once you are done processing at item i, you have a sorted array from where it originally was all the way to the beggining (left most).

4. Decrease the value of j by one. and go back to step 1 (In this example, this will lead you to compare 50 and 60 and swap them).

If you take a look at the code carefully, you never get a the point where i >= len(s) (range is a function that creates a list, and the value i is not changed inside the loop). You can think of the variable i as an imaginary arrow, pointing to a position in the array that has all sorted elements to its left. The variable j simply moves to the left with i fixed, to swap the original array[i] value until it finds another value that is equal or lower than it.

Sidenote (not important to understand the algorithm, but could be useful): With that in mind, you can deduce that this algorithm's complexity (measured in worst case comparisons) is O(N^2) where N = len(s). It is similar to having two nested for statements.

This video does a great job explaining the above, and you know what they say, an image is worth 1000 words.

Answer 6

There are a few pieces of information that help to understand insertion sort.

First of all, i never gets bigger than len(s). In fact, it never is equal to it, either. What range(1, len(s)) does is produces an immutable sequence over which you can iterate. What you will have underneath the following statement (let's assume len(s) = 3):

for i in range(1, len(s)):
    ...

is something like this:

for i in (1, 2):
    ...

You can verify that yourself:

>>> list(range(1, 3))
>>> [1, 2]

So you will iterate two times, first time with i = 1, and the second time with i = 2.

Second, it helps to remind yourself that a list you are sorting consists, in essence, of two parts: the part that is sorted (list[0:i-1]), and the part that is yet to be sorted ([list[i:]). What you are trying to achieve with insertion sort on every iteration is finding a place to put a current value inside a sorted list. We'll get to that shortly.

Third, the algorithm can be thought of as doing two quite distinct tasks. First one is to iterate over all members in a list and ensure that the list is sorted. That's the part that outer loop concerns itself with (of course, inner loop is involved in actual checks, but it helps to make that simplification). The other one is to find appropriate positions for elements in a list so that a list would be sorted. I.e., if you have a list letters = ['a', 'b', 'd', 'c'], 'c' should obviously go to letters[2] and 'd' needs to take 'c''s former place if the list is to be sorted in ascending order. That is the part that inner while loop does.

How the while loop (and s[j+1] = val statement) ensures that list is sorted is quite clever, actually. First, it makes sure that we're not overreaching (j >= 0 condition). That is, that we're not selecting s[-1] element, which in Python would be the last element in the list, and other languages, like Java, ArrayIndexOutOfBounds exception. Then, it asks: is the number that I'm holding lower than the one before it? If so, it means the list is not sorted and we need to move the bigger number one place towards the end of a list (to the right if you will). Note, the element with which we are comparing other elements remains the same. We are holding it in val variable. So we need not concern ourselves with accidentally losing it by overwriting it when moving values.

Now, once we move the bigger value to the right, we decrement j and ask the same question again: is the value at s[j] bigger than the one that we have in val? We continue to do so until we find the value that's lower than what we have in val, or we reach s[0] without finding lower value. That means that what we hold is the lowest number in a list. Either way, we break out of the while loop and overwrite s[j+1] with a value that we have, so that we do not lose value in val.

To see how it looks in practice, consider a list: [2, 3, 4, 5, 1]. Let's say we iterate until we reach number 1, at which point we enter while loop, since 5 > 1. The steps taken would be:

2, 3, 4, 5, 1   # val = 1, s[j] = 5, j = 3       5 > 1
2, 3, 4, 5, 5   # val = 1, s[j] = 4, j = 2       4 > 1
2, 3, 4, 4, 5   # val = 1, s[j] = 5, j = 1       3 > 1
2, 3, 3, 4, 5   # val = 1, s[j] = 5, j = 0       2 > 1
2, 2, 3, 4, 5   # val = 1, s[j] = 5, j = -1      break out of while
1, 2, 3, 4, 5   # val = 1, s[j] = 5, j = -1      put val into s[0]

And that's basically it. Iterate over the loop, check that values before the current one are lower than the one we're holding, and if not, move those values to the right to make space for our value. And there you have it - insertion sort.

Edit: there is a very nice, visual explanation on code review if you're still finding it hard to see how it works.

Answer 7

def insertionsort(list):
    for i in range(1,len(list)):
        temp=list[i]
        j=i-1
        while temp<+list[j] and j>=0:
            list[j+1]=list[j]
            j=j-1
        list[j+1]=temp
    return list
list=eval(raw_input('Enter a list:'))
print insertionsort(list)

This will help you.

Answer 8

Try this one, works for both increasing and decreasing order:

import operator

def insertion_sort(arr, reverse=False):
    # check if array is empty or not
    if arr is None:
        raise TypeError("Data cannot be none")

    n = len(arr)
    # if length of array is less than two it is already sorted
    if n < 2:
        return arr

    lgt = operator.gt if reverse else operator.lt

    # Traverse through 1 to len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i-1
        while j >= 0 and lgt(key, arr[j]):
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

li = [1, 4, 8, 9, 42, 0, 36]
print(insertion_sort(li))

Answer 9

The python range(start, end) function starts counting from start to end - 1. That is, end will never be part of the range() values. So if you have, for example, range(len(A)), and A is an array (in Python, a list) of 10 integers, len(A) will be 10, and range(len(A)) will return (0,1,2,3,4,5,6,7,8,9) so you can index every element in A.

In your case, i never gets bigger than len(s) - 1.

Following your code on paper can be useful, but you have to make sure that the programming language does exactly what you think it does, and sometimes the implementation isn't intuitive. A fast and simple way of tracing your program values is to use print statements. For example:

def sort_numbers(s):
    for i in range(1, len(s)):

        # let's see what values i takes on
        print "i = ", i

        val = s[i]
        j = i - 1
        while (j >= 0) and (s[j] > val):
            s[j+1] = s[j]
            j = j - 1
        s[j+1] = val

Answer 10

def insertionSort(alist):
    for index in range(1, len(alist)):

        currentvalue = alist[index]
        position = index

        while position > 0 and alist[position-1] > currentvalue:
            alist[position] = alist[position-1]
            print(alist)
            position -= 1

        alist[position] = currentvalue

alist = [int(i) for i in input().split()]       
insertionSort(alist)

Answer 11

__author__ = 'Dharmjit'  
def InsertionSort(list):  
    for index in range(1,len(list)):  
        curr = list[index]  
        position = index  

        while position > 0 and list[position-1] > curr:  
            list[position] = list[position-1]  
            position = position - 1  

        list[position] = curr  
    return list  

l = [2,1,5,3,9,6,7]  
print(InsertionSort(l))  
[1,2,3,5,6,7,9]  

You can see the whole concept here- http://pythonplanet.blogspot.in/2015/07/sorting-algorithm-1-insertion-sort.html

Answer 12

def insertion(x):
    for i in range(1, len(x)):
        while x[i - 1] > x[i] and i >= 0:
            x[i - 1], x[i] = x[i], x[i - 1]
            i -= 1
    return x

Something like that

Answer 13

A simple combination of list slicing and bubble sort

s = [54,26,93,17,77,31,44,55,20]

for i in range(1,len(s)+1):
    b = s[0:i]
    a = b
    count = 0

    while count<len(a):                  # while loop to perform the for loop len(a) number of times-like in bubble sort
        for j in range(len(a)-1):        # for loop compares every j'th element with next element
            if a[j] >= a[j+1-len(a)]:
                temp = a[j]
                a[j] = a[j+1-len(a)]
                a[j+1-len(a)] = temp

        count = count+1
print a    

Answer 14

+An alternative with two for loops and descriptive names.

def insertionSort(list):
  for outerIndex in range(len(list)):
    for innerIndex in range(outerIndex, 0, -1):
      if list[innerIndex] >= list[innerIndex - 1]:
        break
      list[innerIndex], list[innerIndex - 1] = list[innerIndex - 1], list[innerIndex]
  return list

print insertionSort([3, 1e-10, 7e5, 2.3, 100, -2.5, 12.1])
# => [-2.5, 1e-10, 2.3, 3, 12.1, 100, 700000.0]

Answer 15

Insertion Sort via Recursion:

k=1# def insertionsort(a): # should be written before k=1
c=a[:]
def swap(k,c,a):
    if c[k-1] > c[k]:
        c[k-1] = a[k]
        c[k] = a[k-1]
        a = c[:]
        if max(c[:k])!= c[k-1]:
            swap(k-1,c,a)
    if k < len(a)-1:
       return swap(k + 1, c,a)
    return c
return swap(k,c,a)

print(insertionsort(b))

Answer 16

Simple way to sort an array.

# Mutate the constant input 
# loop into the array
# check if the array[j] have to be greater than 0 and a[j] is less than a[j - 1] 
# then swap values and decrease the value swapped.

def insertionSort(array):
  a = array
  for i in range(0,len(a)):
    j = i
    while j > 0 and a[j] < a[j - 1]:
      a[j], a[j - 1] = a[j - 1], a[j]
      j -= 1
  return a

# input-> [2,1,3] then array[j] > 0 and array[j] < array[j - 1] -> swap -> decrease j

Answer 17

def ins(l):
    for i in range(1, len(l)):
        current_index = i
        current_value = l[i]
        while current_index > 0 and current_value < l[current_index - 1]:
            l[current_index] = l[current_index - 1]
            current_index -= 1
        l[current_index] = current_value
    print(l)

Answer 18

def insertSort(list):
  for i in range(0, len(list)):
    index = list[i] // index holder for swapAt position
    while i > 0 and index < list[i - 1]:
      list[i] = list[i - 1]
      i = i - 1
      list[i] = index
  return list

print(insert([3,3,6,1,7,2,8])) -> [1, 2, 3, 3, 6, 7, 8]

Answer 19

def sort_numbers(list):
    for i in range(1, len(list)):
        val = list[i]
        j = i - 1
        while (j >= 0) and (list[j] > val):
            list[j+1] = list[j]
            j = j - 1
        list[j+1] = val

n = int(input("Enter the no. of elements"))
list = []
for i in range(0,n):
  t = int(input())
  list.append(t)

sort_numbers(list)

print list

Answer 20

I have looked through a number of these posts and i think that people are over complicating this issue. please correct me if i have done this wrong but this is my interpretation of the sort.

def insert(L): # this creates the definition and assines the list that you input to L
    for i in range(len(L)): # this then loops the next code for the length of the list
        while i > 0 and L[i] < L[i-1]: # this is the main part of the code where it checks
        # if the value from the list is less than the one before it and if it is then it 
        # swaps them around 
            L[i-1], L[i] = L[i], L[i-1] # this code just swaps round the values
            print (L)# prints the list out at the end of each part



L = [5,2,3,7,6,9,7]
insert(L)

Using this it outputs:

[2, 5, 3, 7, 6, 9, 7]
[2, 3, 5, 7, 6, 9, 7]
[2, 3, 5, 6, 7, 9, 7]
[2, 3, 5, 6, 7, 7, 9]

The print function can also be removed from line and can be placed outside the for loop so that it only prints the list at the end. Which would only give the last line:

[2, 3, 5, 6, 7, 7, 9]

Answer 21

`enter code here`
def insertion_sort(data):
n = len(data)
for i in range(n):
    index = i
    value = data[i]
    while data[index] < data[index-1] and index > 0:
        #print("index : " ,index)
        data[index] = data[index-1]
        data[index-1] = value
        #print(f"DATA[index-1] : { data[index-1] } DATA[index] : { data[index] } " )
        index -= 1
        
    data[index] = value

return data;
    
if __name__ == "__main__":
data = []
size = int(input("How many data you want to enter ? : "))

print("\n-----------------INITIALISING----------------")
for i in range(size):
    temp = int(input(f"Enter element { i + 1 } : "))
    data.append(temp)
    
print("\n-----------------BEFORE SORTING DATA----------")
print(data)

print("\n-----------------AFTER SORTING DATA-----------")
print(insertion_sort(data))

Answer 22

    def insertie(x):
    nrc=0
    nrm=0
    for i in range(0,len(x)):
        aux=x[i]
        nrm=nrm+1
        j=i-1
        while j >= 0 and aux < x[j]:
            nrc=nrc+1
            x[j+1]=x[j]
            nrm=nrm+1
            j=j-1
        nrc=nrc+1
        x[j+1]=aux
        nrm=nrm+1
    return x

x=[7,5,4,9,1,4,0,1]
print insertie(x)