How to implement insertion sort in Python

Algorithm

  1. Choose a key, starting from index 11 to n−1n-1, where nn is the length of the array.

  2. Keep swapping the key with all the larger values on its left side until a value less than or equal to the key occurs, or index 00 is reached.

  3. Select the next index as the key. Repeat step 2.

Dry run

Set key = index 1
1 of 17

Implementation

def insertion_sort(arr):
for i in range(1, len(arr)):
# Set key:
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
# Swap:
arr[j + 1] = arr[j]
arr[j] = key
# Decrement 'j':
j -= 1
return arr
array = [5, 2, 12, 12, 1]
print("Original array: %s" % array)
print("Sorted array: %s" % insertion_sort(array))
Copyright ©2024 Educative, Inc. All rights reserved