Trusted answers to developer questions
How to implement insertion sort in Python
Educative Answers TeamAlgorithm
-
Choose a key, starting from index to , where is the length of the array.
-
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 is reached.
-
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))
RELATED TAGS
implement
insertion
sort
python
algorithm
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES
View all Courses
Keep Exploring
Related Courses
