Summary - Insertion sort

Implement insertion sort in a mini task.

Summary - Insertion sort

In this group you learned insertion sort's logic, shifting, full sorting and advantages. Complexity is O(n^2), best case O(n).

Insertion sort is preferred for nearly sorted arrays and small data. It sorts in-place and does few writes.

Exercise Full insertion sort

Write insertion_full(arr). Sort with for and while. Print [1, 1, 2, 3, 4, 5, 6, 9] with print(insertion_full([3, 1, 4, 1, 5, 9, 2, 6])).

Show example solution

def insertion_full(arr):
    # Fully sort
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = key
    return arr
print(insertion_full([3, 1, 4, 1, 5, 9, 2, 6]))

Test yourself

Summary - Insertion sort: match the terms

Insertion sort

Place correctly
Shifting

Move right
Best

O(n)
In-place

No extra memory

Insertion sort

Insertion sort places each element in the ____ part.

Show answer

Insertion sort places each element in the sorted part.

How long does insertion sort take on nearly sorted arrays?
- O(n^2)
- O(1)
- O(n log n)
- O(n)
Show answer

O(1) — On nearly sorted arrays it is O(n).

Next lesson: Project: Overview

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies