Understanding Insertion Sort: A Question-Driven Approach

In this blog post, we'll take a question-driven approach to understand the fundamentals of the insertion sort algorithm. I came up with this approach when I was trying to find a better way to understand the insertion algorithm and others that I will soon be learning about. I wanted to build a strategy that I could apply to most, if not all, of the algorithms I will be learning. While I was thinking about this, I was sure that I might have to use first principles thinking

Inspired by first principles thinking, this approach involves first trying to grasp the algorithm, whether our initial understanding is vague or clear. We then identify the tiny concepts or mechanics involved that make up the algorithm. By forming questions around these mechanics or tiny concepts. We are essentially trying to understand the working of the algorithm from small different perspectives with a focus on trying to solve the questions that we formed on our own.

The answer you form may or may not initially resemble the syntax used in the actual algorithm. The goal should be to answer the question on your own, regardless of whether the syntax is close or not. Once you have a clear understanding, you can then convert, merge your answer(s) to use syntax, similar to the actual implementation of the algorithm. I believe this process allows you to explore alternative forms of code , grasp why a specific syntax is being used, deal with edge cases in a better way on your own.

I believe this method ensures that we understand the theory and the reasoning behind each line of code, making the implementation process more intuitive and meaningful. The following questions and the thought process which i went through helped me understand Insertion Sort better and enabled me to code it effectively.

For you, the questions might be different; they could be more, fewer, or entirely different. Some might say this is akin to reverse engineering, whatever you call it, this method enabled me get a thorough understanding of the Insertion Sort algorithm. I hope it does the same for you for any other other algorithm. Soo, let’s dive in!

Insertion Sort Implementation

This is the form of code we will eventually implement for Insertion Sort.

def insertion_sort(values):

    for new_value_index in range(1,len(values)):

        new_value = values[new_value_index]

        index = new_value_index-1
        while index>=0:
            if values[index]<new_value:break
            values[index+1] = values[index]
            index-=1

        values[index+1] = new_value

Questions

Given a sorted list, using while loop, print values from right to left.

values = [4,8,12,16,20,24,30]
# given a sorted list, using while loop, print values from right to left.

index = len(values)-1
while index>=0:
    print(values[index],end = " ")
    index-=1

Given a sorted list and a new value, find the index at which the new value is to be inserted to keep the list sorted.

values = [4, 8, 12, 16, 20, 24]
new_value = 14

# using while loop, if traversing from right to left

index = len(values)-1
while index>=0:
    if values[index]<new_value: break
    index-=1

print(values,new_value,index)

Given a sorted list and a new value, insert the new value to the list so it remains sorted.

values = [4, 8, 12, 16, 20, 24]
new_value = 14

# if traversal from right to left

index = len(values)-1
while index>=0:
    if values[index]<new_value:break
    index-=1

values = values[:index+1] + [new_value] + values[index+1:]
print(values)

Given a sorted list, then appended with a new value, move the new value to the given index position.

values = [4, 8, 12, 16, 20, 24, 30]

new_value = 14

values.append(new_value)

given_index = 3

# above given

n = len(values)-1

index = n-1
while index>given_index:
    values[index+1] = values[index]
    index-=1

print(values)

values[given_index+1] = new_value

print(values)

Given a sorted list, then appended with a new value, sort the list.

values = [4, 8, 12, 16, 20, 24, 30]

new_value = 14

values.append(new_value)

print(values)

### given a sorted list, then appended with new value, sort the list
####

n = len(values)-1
new_value = values[-1]

# find the index at which the value is to be inserted
# right to left
index = n-1
while index>=0:
    if values[index]<new_value:break
    index-=1
given_index = index 
print("given_index : "  , given_index)

# move the values forward by one step until we reach the given index
index = n-1
while index>given_index:
    values[index+1] = values[index]
    index-=1

values[index+1] = new_value

print(values)

Given a sorted list, then appended with a new value(s), sort the list.

values = [4, 8, 12, 16, 20, 24, 30]

new_values = [14,32]

values += new_values

print(values)

# given a sorted list, then appended with two new value(s), sort the list

n = len(values)-1

new_value_start_index = n - 1

print(new_value_start_index, values[new_value_start_index])

for new_value_index in range(new_value_start_index,len(values)):

    new_value = values[new_value_index]

    index = new_value_index-1
    while index>=0:
        if values[index]<new_value: break
        values[index+1] = values[index]
        index-=1

    values[index+1] = new_value

print(values)

Given a list, sort it.

import random

values = random.sample(range(10,90), k = 10)

values

print(values)

for new_value_index in range(1,len(values)):
    new_value = values[new_value_index]

    index = new_value_index-1
    while index>=0:
        if values[index]<new_value:break
        values[index+1] = values[index]
        index-=1
    values[index+1] = new_value

print(values)

Insertion Sort Implementation

def insertion_sort(values):
    for new_value_index in range(1,len(values)):
        new_value = values[new_value_index]

        index = new_value_index-1
        while index>=0:
            if values[index]<new_value:break
            values[index+1] = values[index]
            index-=1
        values[index+1] = new_value

Additional Resources

While I initially worked through a comprehensive set of questions to understand the algorithm better, the above are a set of questions that I think are important to understand Insertion Sort in a better way. Including all of the questions that I worked on would make the post quite lengthy.

For those interested in seeing all of the questions, I have created a Jupyter Notebook containing the full set of questions with my own answers, which enabled me to understand the implementation of Insertion Sort completely.

I encourage you to check out the notebook if you want to delve further.

Corrections and suggestions are welcome.

The above is the detailed content of Understanding Insertion Sort: A Question-Driven Approach. For more information, please follow other related articles on the PHP Chinese website!