lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

pythonIntroAlgorithms1Chapter2Title

lesson13Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

lesson18Title

lesson19Title

pythonIntroAlgorithms1Chapter1Title

pythonIntroAlgorithms1Chapter3Title

pythonIntroAlgorithms1Chapter4Title

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        # Insert the key at its appropriate position
        arr[j + 1] = key
    return arr


# Example usage
example_array = [12, 11, 13, 5, 6]

sorted_array = insertion_sort(example_array)

print("Sorted array:", sorted_array) # Sorted array: [5, 6, 11, 12, 13]

# Understanding Insertion Sort in Depth

## 1. Setting Up the Loop

Iterate over each element in the array, assuming the first element is already sorted.

```python title="Setting Up the Loop"
for i in range(1, len(arr)):
```

<br />

## 2. Selecting the Current Element and Finding the Correct Position

Select the current element, compare it with the previous elements, and find the appropriate position.

```python title="Selecting the Current Element and Finding the Correct Position"
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
    arr[j + 1] = arr[j]
    j -= 1
arr[j + 1] = key
```

<br />

## Time Complexity

1. `Worst-case time complexity`: O(n^2)

   - The worst-case occurs when the input array is sorted in reverse order. In this case, every new element needs to be compared with all previous elements in the already sorted portion of the array, requiring approximately (nxn) comparisons for n elements.

2. `Best-case time complexity`: O(n)

   - This happens when the array is already sorted. Here, the correct position for each new element in the already sorted portion can be found immediately, requiring only one comparison per element. Thus, n comparisons are needed for an array of size n.

3. `Average time complexity`: O(n^2)

   - In general cases where the array elements are arranged randomly, the average number of comparisons required is proportional to n^2.

Understanding Insertion Sort in Depth