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 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.
If you understand the algorithm, you can write code in any programming language.
Insertion Sort in Python Using List
- 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)
[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 arr] sorted_arr = insertion_sort(arr) print("Origional String: " sample_string) print("Sorted String: ", "".join(sorted_arr))
Origional String: csestack Sorted String: acceksst
To sort the given string, we are converting the string into the list and then sorting the list. 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 simple program for insertion sort in Python using list and string. If you have any doubt, let me know in the comment section.