Selection Sort and Insertion Sort

1. Selection Sort and Insertion Sort

Let's study selection sort and insertion sort.

2. Selection sort

Let's begin with selection sort. We start at the first position and move the pointer until the end of the list, determining the lowest value. When we start,

3. Selection sort

the first number is the lowest. In this example, it is the number four.

4. Selection sort

We keep moving and compare the next item with number four. As three is smaller than four,

5. Selection sort

three becomes the lowest value.

6. Selection sort

We keep moving and compare seven with three. Since seven is greater than three, we continue.

7. Selection sort

One is smaller than three,

8. Selection sort

so we mark it as the lowest value.

9. Selection sort

We then compare one with five. Since five is greater than one, we do nothing. When we reach the end,

10. Selection sort

we swap the lowest value with the first unordered value, which in this case,

11. Selection sort

is located at index zero.

12. Selection sort

The lowest value has been correctly moved, so we continue with the second pass.

13. Selection sort

Again,

14. Selection sort

we determine the lowest value.

15. Selection sort

In this case, since three is the lowest value,

16. Selection sort

we keep it in its position

17. Selection sort

and continue.

18. Selection sort

Four is

19. Selection sort

the lowest value

20. Selection sort

in this pass,

21. Selection sort

so we swap it

22. Selection sort

with the first unordered value.

23. Selection sort

We continue

24. Selection sort

doing

25. Selection sort

the same

26. Selection sort

until

27. Selection sort

all

28. Selection sort

elements

29. Selection sort

are

30. Selection sort

sorted.

31. Selection sort - implementation

Let's implement selection sort in Python. We start with a loop that iterates over all the elements of the list, except the last one. That is because, at that point, the list will be already sorted. At the beginning of the iteration, we save the first value as the lowest value, and record index of this value. Then, we begin another loop that begins on the next position of the i variable. For each element, we check if its value is less than the lowest value we have found so far. If yes, we save its index and its value. When the inner loop finishes, we swap the lowest value with the first unordered value in the list. We continue until we reach the end. We return the sorted list.

32. Selection sort - complexity

Selection sort has a complexity of n-squared in the worst, average, and best cases.

33. Insertion sort

Let's move on to insertion sort.

34. Insertion sort

We start by comparing the first and second elements. As three is less than four,

35. Insertion sort

we shift the four to the right

36. Insertion sort

and insert

37. Insertion sort

three before four.

38. Insertion sort

Then, we continue to seven and compare it with four. As seven is greater,

39. Insertion sort

we leave it where it is.

40. Insertion sort

We continue and compare one with seven. As seven is greater than one,

41. Insertion sort

we shift seven to the right. Four is also greater than one,

42. Insertion sort

so we also shift it to the right.

43. Insertion sort

We do the same with number three,

44. Insertion sort

and finally, we place

45. Insertion sort

number one.

46. Insertion sort

We repeat the same steps

47. Insertion sort

with

48. Insertion sort

five.

49. Insertion sort - implementation

Let's study the implementation of insertion sort in Python. We start a loop that begins at position number one and goes until the end of the list. We store the number we want to order, and set j to the value of i minus one. We start another loop that runs while the value of j is greater or equal to zero and number_to_order is less than the value at j index. If so, we shift the value at the j index to the right and decrement j by one. At the end of the inner loop, we move the number we are ordering to its correct position. When the outer loop finishes, we return the ordered list.

50. Insertion sort - complexity

Insertion sort has a complexity of n-squared in worst and average cases but Omega of n in best case.

51. Let's practice!

Let's practice!

Create Your Free Account

By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.