CodeGym /Java Course /Python SELF EN /Insertion Sort

Insertion Sort

Python SELF EN

Level 58 , Lesson 1

Available

6.1 Insertion Sort Definition

Insertion Sort is a sorting algorithm that builds a sorted array (or list) one element at a time. It takes each element from the unsorted part and inserts it in the correct position in the sorted part.

How it works:

Start from the second element in the array (the first element is assumed to be sorted).
Compare the current element with the previous elements and move it to the left until you find the right spot.
Repeat the process for all elements, placing each new element in its correct position in the sorted part of the array.

Time and Space Complexity of Insertion Sort

Time Complexity:

In the worst case: O(n^2) — occurs when elements are initially ordered in reverse.
On average: O(n^2) — occurs for a random arrangement of elements.
In the best case: O(n) — occurs when elements are already sorted.

Space Complexity:

O(1) — since the algorithm uses a constant amount of additional memory (just a few variables to store temporary values).

6.2 Algorithm Workflow

At each step of the algorithm, we have the following situation:

We have a current element with index i.
All elements to its left are already sorted from smaller to larger.
We try to insert our current element into the sorted part of the array so the sorting order is maintained.

Trying to insert an element into the sorted part of the array looks like this:

Variable j takes values from i - 1 to 0 in the loop.
If the current (i-th) element is smaller than the j-th, we shift the value of the j-th element one position to the right.

Example: current situation:

Green marks already sorted elements.
Pink indicates elements not yet sorted.
The current element at index 5 is marked in brown.

We try to find the correct place for our current element in the sorted part of the array.

Step 1 — save the value of the current element in the variable key.

Step 2 — is element No4 greater than key? (Is 10 greater than 5?) Then move element No4 to the right:

Step 3 — is element No3 greater than key? (Is 8 greater than 5?) Then move element No3 to the right:

Step 4 — is element No2 greater than key? (Is 6 greater than 5?) Then move element No2 to the right:

Step 5 — is element No1 greater than key? (Is 4 greater than 5?) No. Then place the element key where element No2 was.

Once we have placed element No5 in the right spot, we move onto element No6 and try to find its place in the sorted part of the array:

Then we take the seventh element:

Then the eighth:

6.3 Implementing the Insertion Sort Algorithm

This is what the algorithm looks like in Python:


def insertion_sort(arr):
    # Go through all elements in the array, starting from the second one
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Move elements arr[0..i - 1], which are greater than the key, one position forward
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key  # Insert the key in the correct place
    return arr  # Return the sorted array
        
# Example usage:
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Sorted array:", sorted_arr)
# Output: Sorted array: [5, 6, 11, 12, 13]

Explanation: