I’ve spent some time last week on data structure and algorithm, so in this blog post I’m going to write down some fundamental logic of some common sorting algorithms.
Let’s say that we have an array here [6,5,3,1,8,7,2,4], how would you move these elements around?
Bubble sort
We look at the first element 6 and the second one 5, 6 is greater than 5 so we swap them out. After this action the original array will change from [6,5,3,1,8,7,2,4] to [5,6,3,1,8,7,2,4] and we keep on going to compare the second element 6 and third element 3 and so on. After the first round of bubbling up the array becomes like this [5,3,1,6,7,2,4,8]. At this point we’ve succssfully bubbled up the largest number element in this array which is 8. Then we go from the beginning and we’ll get [3,1,5,6,2,4,7,8] and [1,3,5,2,4,6,7,8] and we keep looping finally we will get the sorted array [1,2,3,4,5,6,7,8].
How do you think of bubble sort? Easy and ineffecient right? The only up side of bubble sort is that we don’t create any data structure so the space complexity is O(1).
Selection sort
Selection sort is very similar to bubble sort but instead of bubbling up the largest element to the end, selection sort selects the smallest item to the beginning.
For [6,5,3,1,8,7,2,4], we look at the first element 6 and now it’s the smallest item and we look at the next one 5, now we hold 5 as the smallest item and go on until we loop through the whole array and determine that 1 is the smallest, then we swap it with the first element and this array becomes [1,5,3,6,8,7,2,4] and then we go from the top without the first element so it’ll become [1,2,3,6,8,7,5,4], [1,2,3,4,8,7,5,6], [1,2,3,4,5,7,8,6],[1,2,3,4,5,6,8,7], [1,2,3,4,5,6,7,8].
Just like bubble sort we’re looping through the array once and once again so we can guess that the time complexity isn’t very fast. Because we have nested for loop so the big O notation is going to be O(n²)
Insertion sort
Insertion sort is also very basic just like those above-mentioned algorithms, however insertion sort can behave very well when the array is nearly sorted. The best case you can get linear time when using it correctly. Let’s dive in and see how it works.
In [6,5,3,1,8,7,2,4], we look at the first item 6 and just leave it there, and see 5 at the second place and because 5 is less than 6 so we switch it over. Then we see 3 and say “Hey, where are you in relation to 5 and 6?”. Obviously 3 is less than 5 and 6 so we shift 5 and 6 over and 3 goes to the front and we keep going until it’s all sorted.
How about that? I think this method is probably how our brain works when we have to move these numbers around
The End
When interviewing, it’s common to be asked to implement these simple sorting algorithms to check that if as interviewees we truly understand how to choose when to use what kind of algorithms and the logic under the hood.
