Insertion Sort Example

Insertion Sort Example:

Initial Array: [6, 8, 3, 2, 7, 5, 1, 4]

First Iteration: [6][ 8, 3, 2, 7, 5, 1, 4]

Step-by-Step Process:

1. Start with the second element (index 1) and compare it with the previous elements, inserting it into the correct position.

Iteration 1 (Index 1: 8):

• Current element: 8

• Compare 8 with 6 (previous element). Since 8 > 6, it stays in its place.

• Array after iteration 1: [6, 8][ 3, 2, 7, 5, 1, 4]

Iteration 2 (Index 2: 3):

• Current element: 3

• Compare 3 with 8: 3 < 8 → shift 8 to the right.

• Compare 3 with 6: 3 < 6 → shift 6 to the right.

• Insert 3 at index 0.

• Array after iteration 2: [3, 6, 8][ 2, 7, 5, 1, 4]

Iteration 3 (Index 3: 2):

• Current element: 2

• Compare 2 with 8: 2 < 8 → shift 8 to the right.

• Compare 2 with 6: 2 < 6 → shift 6 to the right.

• Compare 2 with 3: 2 < 3 → shift 3 to the right.

• Insert 2 at index 0.

• Array after iteration 3: [2, 3, 6, 8][ 7, 5, 1, 4]

Iteration 4 (Index 4: 7):

• Current element: 7

• Compare 7 with 8: 7 < 8 → shift 8 to the right.

• Compare 7 with 6: 7 > 6 → stop shifting.

• Insert 7 at index 3.

• Array after iteration 4: [2, 3, 6, 7, 8][ 5, 1, 4]

Iteration 5 (Index 5: 5):

• Current element: 5

• Compare 5 with 8: 5 < 8 → shift 8 to the right.

• Compare 5 with 7: 5 < 7 → shift 7 to the right.

• Compare 5 with 6: 5 < 6 → shift 6 to the right.

• Compare 5 with 3: 5 > 3 → stop shifting.

• Insert 5 at index 2.

• Array after iteration 5: [2, 3, 5, 6, 7, 8][ 1, 4]

Iteration 6 (Index 6: 1):

• Current element: 1

• Compare 1 with 8: 1 < 8 → shift 8 to the right.

• Compare 1 with 7: 1 < 7 → shift 7 to the right.

• Compare 1 with 6: 1 < 6 → shift 6 to the right.

• Compare 1 with 5: 1 < 5 → shift 5 to the right.

• Compare 1 with 3: 1 < 3 → shift 3 to the right.

• Compare 1 with 2: 1 < 2 → shift 2 to the right.

• Insert 1 at index 0.

• Array after iteration 6: [1, 2, 3, 5, 6, 7, 8][ 4]

Iteration 7 (Index 7: 4):

• Current element: 4

• Compare 4 with 8: 4 < 8 → shift 8 to the right.

• Compare 4 with 7: 4 < 7 → shift 7 to the right.

• Compare 4 with 6: 4 < 6 → shift 6 to the right.

• Compare 4 with 5: 4 < 5 → shift 5 to the right.

• Compare 4 with 3: 4 > 3 → stop shifting.

• Insert 4 at index 3.

• Array after iteration 7: [1, 2, 3, 4, 5, 6, 7, 8]

Final Sorted Array:

[1, 2, 3, 4, 5, 6, 7, 8]

Summary of Key Points:

• Insertion sort works by iterating through the array, picking one element at a time, and shifting larger elements to the right to make space for the current element to be inserted in its correct position.

• The algorithm sorts the array incrementally, ensuring that the left portion of the array is sorted at each step.

Insertion Sort Slide Deck - This pdf presentation has more examples to practice with.