COSC 130: Data Structures
Sorting Algorithms
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:
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.