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 position17. Selection sort
and continue.18. Selection sort
Four is19. Selection sort
the lowest value20. Selection sort
in this pass,21. Selection sort
so we swap it22. Selection sort
with the first unordered value.23. Selection sort
We continue24. Selection sort
doing25. Selection sort
the same26. Selection sort
until27. Selection sort
all28. Selection sort
elements29. Selection sort
are30. 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 right36. Insertion sort
and insert37. 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 place45. Insertion sort
number one.46. Insertion sort
We repeat the same steps47. Insertion sort
with48. 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
or
By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.