Insertion Sort in Python Using List and String

Insertion Sort in Python Using List and String

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:

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).

insertion sort algorithm

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:

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.

4 Comments

  1. There are little mistakes in the code for sorting the string
    Line 23: arr = [i for i in arr] instead of arr = [i for i in sample_string]
    Line 25: print("Origional String: " sample_string) instead of print("Original String: ", sample_string)

  2. What is the time complexity of the insertion sort algorithm, and how does it compare to other sorting algorithms?

Leave a Reply

Your email address will not be published. Required fields are marked *