How to implement insertion sort in Python
Algorithm
-
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 - 1while j >= 0 and arr[j] > key:# Swap:arr[j + 1] = arr[j]arr[j] = key# Decrement 'j':j -= 1return arrarray = [5, 2, 12, 12, 1]print("Original array: %s" % array)print("Sorted array: %s" % insertion_sort(array))
Copyright ©2024 Educative, Inc. All rights reserved
TRENDING TOPICS
