Insertion Sort - Sorting Algorithms 2024

Insertion sort

1. Insertion Sort

2. 90 70 23 18 13
Make sure all the elements in the
Orange Window
are Sorted

3. 90 70 23 18 13
1.Start from Left to Right
2.Increase the window size by one
3.After each increase, Move elements
GREATER THAN the new element
one step forward.

4. 6 9 18 27 13
For Example,
We need to move 18 & 27 one step
To make free space for the 13
6 9 18 27

5. 90 70 23 18 13
Window is sorted.
→ Increase its size by one.

6. 90 70 23 18 13
→ Set current to the newly added element.
→ compare current to all the elements to
its left one by one
Current ⇒ 70

7. 90 70 23 18 13
Current < 90
Yes ⇒ copy 90 to the right
Current ⇒ 70

8. 90 90 23 18 13
No more elements GREATER Than
Current
⇒ Add 70 to the place where ( all the
elements to its left are SMALLER )
Current ⇒ 70

9. 70 90 23 18 13
all the elements in theOrange Window
are Sorted.
⇒Increase the window size by one
⇒ set “ Current “ to the new element
Current ⇒ 70

10. 70 90 23 18 13
Current < 90
Yes ⇒ copy 90 to the right
Current ⇒ 23

11. 70 90 90 18 13
Current < 70
Yes ⇒ copy 70 to the right
Current ⇒ 23

12. 70 70 90 18 13
No more elements GREATER Than
Current
⇒ Add 23 to the place where ( all the
elements to its left are SMALLER )
Current ⇒ 23

13. 23 70 90 18 13
all the elements in theOrange Window
are Sorted.
⇒Increase the window size by one
⇒ set “ Current “ to the new element
Current ⇒ 23

14. 23 70 90 18 13
Current < 90
Yes ⇒ copy 90 to the right
Current ⇒ 18

15. 23 70 90 90 13
Current < 70
Yes ⇒ copy 70 to the right
Current ⇒ 18

16. 23 70 70 90 13
Current < 23
Yes ⇒ copy 23 to the right
Current ⇒ 18

17. 23 23 70 90 13
No more elements GREATER Than
Current
⇒ Add 18 to the place where ( all the
elements to its left are SMALLER )
Current ⇒ 18

18. 18 23 70 90 13
all the elements in theOrange Window
are Sorted.
⇒Increase the window size by one
⇒ set “ Current “ to the new element
Current ⇒ 18

19. 18 23 70 90 13
Current < 90
Yes ⇒ copy 90 to the right
Current ⇒ 13

20. 18 23 70 90 90
Current < 70
Yes ⇒ copy 70 to the right
Current ⇒ 13

21. 18 23 70 70 90
Current < 23
Yes ⇒ copy 23 to the right
Current ⇒ 13

22. 18 23 23 70 90
Current < 18
Yes ⇒ copy 18 to the right
Current ⇒ 13

23. 18 18 23 70 90
No more elements GREATER Than
Current
⇒ Add 13 to the place where ( all the
elements to its left are SMALLER )
Current ⇒ 13

24. 13 18 23 70 90
Reached the end of the array ⇒ Done

25. Sort only until the element “ 5 “
12, 11, 13, 5, 6

26. → 12, 11, 13, 5, 6⇒ current = 12
→ 12, 11, 13, 5, 6⇒ current = 1111 < 12 YES
→ 12, 12, 13, 5, 6
→ 11, 12, 13, 5, 6
→ 11, 12, 13, 5, 6⇒ current = 1313 < 12 NO
→ 11, 12, 13, 5, 6 ⇒ current = 55 < 13 YES
→ 11, 12, 13, 13, 6⇒ current = 55 < 12 YES
→ 11, 12, 12, 13, 6⇒ current = 55 < 11 YES
→ 11, 11, 12, 13, 6
→ 5, 11, 12, 13, 6
12, 11, 13, 5, 6

27. → 5, 11, 12, 13, 6 ⇒ current = 6
→ 5, 11, 12, 13, 6 ⇒ current = 66 < 13 YES
→ 5, 11, 12, 13, 13 ⇒ current = 66 < 12 YES
→ 5, 11, 12, 12, 13 ⇒ current = 66 < 11 YES
→ 5, 11, 11, 12, 13 ⇒ current = 66 < 5 NO
→ 5, 6, 11, 12, 13 ⇒ current = 6
12, 11, 13, 5, 6

28. Your Turn !
2, 5, 8, 12, 7

29. → 2, 5, 8, 12, 7⇒ current = 2
→ 2, 5, 8, 12, 7⇒ current = 55 < 2 NO
→ 2, 5, 8, 12, 7⇒ current = 88 < 5 NO
→ 2, 5, 8, 12, 7⇒ current = 1212 < 8 NO
→ 2, 5, 8, 12, 7 ⇒ current = 77 < 12 YES
→ 2, 5, 8, 12, 12⇒ current = 77 < 8 YES
→ 2, 5, 8, 8, 12 ⇒ current = 77 < 5 NO
→ 2, 5, 7, 8, 12
2, 5, 8, 12, 7

30. 2 Exit Points
1. Current is NOT less than compared
element.
2. We’ve reached the start
( we then increase the window size )

31. Problems with Insertion Sort

32. 252421201915121097
252421201915121097
Current = 10
252524212019151297

33. 252421201915121097
252421201915121097
102524212019151297
Current = 10