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

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.

• ###### empty_space138
July 12, 2021 at 7:01 pm

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

• ###### Aniruddha Chaudhari
July 13, 2021 at 9:03 am

Thanks for those corrections. Addressed. I would have liked knowing your real name though 😀 Keep coding!

• ###### Aniruddha Chaudhari
July 13, 2021 at 9:04 am

Updated print statement with `f-string`. I think this is the better way of doing it.