Implementation (Part 2)
Lesson 6 of 9 in Coddy's Insertion Sort - DSA Series course.
Scenario: Sorting [5, 2, 9, 1, 5]
Step 1: Initial State
- Original Array: [5, 2, 9, 1, 5]
- Imagine this as our hand of cards (or array of numbers).
Step 2: First Element (i=1, key=2)
- We start with the second card (element): key = 2.
- Compare 2 with 5 (the only sorted element so far).
- Since 2 is smaller, we shift 5 to the right and insert 2 in its place.
- Updated Array: [2, 5, 9, 1, 5]
Step 3: Second Element (i=2, key=9)
- Move to the next card: key = 9.
- Compare 9 with 5.
- Since 9 is greater, no need to shift.
- Updated Array: [2, 5, 9, 1, 5] (no change)
Step 4: Third Element (i=3, key=1)
- Move to the next card: key = 1.
- Compare 1 with 9, then with 5.
- Shift 9 and 5 to the right, making space for 1.
- Updated Array: [1, 2, 5, 9, 5]
Step 5: Fourth Element (i=4, key=5)
- Move to the next card: key = 5.
- Compare 5 with 9.
- Since 5 is smaller, no need to shift.
- Updated Array: [1, 2, 5, 9, 5] (no change)
Step 6: Fifth Element (i=5, key=5)
- Move to the last card: key = 5.
- Compare 5 with 9.
- Since 5 is smaller, no need to shift.
- Updated Array: [1, 2, 5, 5, 9]
Final Result:
- Sorted Array: [1, 2, 5, 5, 9]
In each step, we're picking a card (element), comparing it with the sorted ones, and placing it in the right spot, shifting others if needed. We repeat this process until the entire array is sorted.
Challenge
EasyNow, implement the inner loop, which does the sorting for each element.
Complete the sort inside the function insertionSort.
The function should also print the elements of the array at the end, one by one, with a new line in between.
Use the previous lessons and the hint as reference :)
Try it yourself
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
print(key)
All lessons in Insertion Sort - DSA Series
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity