Trusted answers to developer questions
Trusted Answers to Developer Questions

RELATED TAGS

How to implement insertion sort in Python

Educative Answers Team

Algorithm

  1. Choose a key, starting from index 11 to n1n-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))

RELATED TAGS

Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time

Copyright ©2022 Educative, Inc. All rights reserved.

soc2