Sorting Algorithms
As a new developer from a Bootcamp, it is easy to get used to simply using the built-in sorting methods in the language, or simply using linear search to anything else.
But since I left school, I had to learn more about algorithms and how machines, memory and well, development, actually works, and how doing the thing that cost the least amount of memory/time, is the best solution in the long term.
You will be constantly Sorting data, either to show to the user or for internal reasons and Searching when you want to show specific data, you can do it in a lot of different ways, and it will always have tradeoffs, so there isn’t the best way of dealing with all the possibilities.
In this article, I will be talking about the different sorting algorithms, but there is going to be a follow up in how to do searching algorithms.
Sorting
Selection Sort
Find the smallest item between the nth item and last item and swap the smallest item with the item.
It means it will get the first element and compare to each element in the array until it finds something smaller than itself, and when it does it will change places with the element.
You can see in the video it is not a very effective way or sorting elements because you will always have to compare each element to everything else in the array, it might be inexpensive in an array with 10 items, but when you start scaling, you will lose a lot of time.
Here is an example of how to implement selection sort in Python:
Best case scenario: n², Worst case scenario: n²
Bubble Sort
Sorting numbers by comparing itself with the one next to it. In this way, you end up bubbling the biggest numbers to the right side of the array, which gives it the name.
It is known as bubble sort because if a number is greater than the following consecutive number, it will look like the number is bubbling through the array.
Here is an example of how to implement bubble sort in Python:
Best case scenario: n, Worst case scenario: n²
Insertion Sort
It gets each element and starts comparing the element from left to the one in the right and you shift the element to the right position. It will be done with one element at a time, but it will compare with all the elements in the “sorted” part of the array.
The worst-case scenario is if the array is reversed. For this, it is only efficient if you are using a small amount of data.
Example in Python:
Best case scenario: n, Worst case scenario: n²
Merge Sort
Split the full array into subarrays, then merge those subarrays back together in the correct order, for example, if you have one array with 4 elements, you will end up with 4 arrays with one element, and then, you will start joining them in the correct order.
Example in Python:
Best case scenario: n log n, Worst case scenario: n log n
Now it is your time
Reading about algorithms and understanding them is one thing, implementing them is another feature.
So try to sort an array using the different methods show here to see if you fully understand how they look.
