Insertion Sort in Python Using List and String

Insertion is one of the basic sorting algorithms. This sorting technique takes elements one by one from the list (array) and inserts them in the correct order in the new sorted list.

In the insertion sort algorithm, every step moves an element from the unsorted section (subarray) to the sorted section (subarray) until all the elements are sorted in the list.

To understand the working of the insertion sort, let’s check the algorithm.

Algorithm [Step-by-Step Procedure]:

• Step 1: Assume that the first element in the list is in the sorted section of the list and remaining all elements are in the unsorted section.
• Step 2: Consider the first element from the unsorted list and insert that element into the sorted list in the order specified (ascending or descending)
• Step 3: Repeat the above steps until all the elements from the unsorted list are moved to the sorted list.

This is one of the very important data structure coding interview questions.

If you understand the algorithm, you can write code in any programming language.

Insertion Sort in Python Using List

Prerequisite:

• In the below Python code, we are using Python while and for a loop.
• Python list to store the elements to sort.

Python Code with Example:

# This function takes unsorted array as an input 
# and returns sorted array.
def insertion_sort(arr):

    #loop over all the elements in the list 
    for i in range(1, len(arr)): 
  
        val = arr[i]
  
        # move elements of list [0..i-1], that are 
        # greater than val, to one position ahead 
        # of the current position 
        j = i-1
        while j >=0 and val < arr[j] : 
            arr[j+1] = arr[j] 
            j -= 1
        arr[j+1] = val
    
    return arr

#given array
arr = [74, 14, 13, 42, 7]

sorted_arr = insertion_sort(arr)
print(sorted_arr)

Output:

[7, 13, 14, 42, 74]

Here is the execution of insertion sort at each stage (iteration).

By tweaking few lines of code, we can also sort the string in Python.

Insertion Sort for String in Python

# This function takes unsorted array as an input 
# and returns sorted array.
def insertion_sort(arr):

    #loop over all the elements in the list 
    for i in range(1, len(arr)): 
  
        val = arr[i]
  
        # move elements of list [0..i-1], that are 
        # greater than val, to one position ahead 
        # of the current position 
        j = i-1
        while j >=0 and val < arr[j] : 
            arr[j+1] = arr[j] 
            j -= 1
        arr[j+1] = val
    
    return arr

#given string
sample_string = "csestack"
arr = [i for i in sample_string]
sorted_arr = insertion_sort(arr)
print(f"Origional String: {sample_string}")
print(f"Sorted String: {''.join(sorted_arr)}")

Output:

Origional String: csestack
Sorted String: acceksst

To sort the given string, we are converting the string into the list and then sorting the list. The sorted list is converted back into the string.

There are already inbuilt functions to sort the list in Python. But, understanding the algorithm is important. Insertion sort algorithm is asked in many job interviews to test candidate’s logic-building skills and algorithm understanding.

For practice, you can apply insertion sort to sort the characters in the string. Let’s try and share your code in the comment section.

Check Other Sorting Algorithms:

• Selection Sort in Python
• Quick Sort in Python

This tutorial is all about the simple program for insertion sort in Python using list and string. If you have any doubt, let me know in the comment section.