JS: Sorting Algorithms, Pt. 1

Woohoo!

I made it! I graduated from Flatiron School’s Immersive Software Engineering Program last month. Hooray! Now that time has passed, it’s time to focus on the job search. With the job search, comes the interviews, which are both technical and non-technical. Because of this, I’ve decided to dedicate some of my next few blogs on data structures and algorithms. While we were briefly exposed to this at Flatiron, we didn’t practice it too much. So I’ve decided to write blogs about them.

First up, sorting algorithms (in Javascript)!

What is a Sorting Algorithm? Why is it Important?

Hogwarts’ Sorting Hat

A sorting algorithm is a set of instructions that take a list of items and arrange them in a particular order. Since sorting can often reduce the complexity of a problem, it’s important to learn. While there are so many different types of sorting algorithms, the length of time sort usually depends on the amount of items in the list. That’s where the concept of Big O Notation comes in, where faster is better, of course.

Common Sorting Algorithms

These are some of the more common sorting algorithms:

1. Selection Sort
2. Bubble Sort
3. Insertion Sort
4. Heap Sort
5. Quick Sort
6. Merge Sort

While there are many more types of sorting algorithms, these are the ones I’ll be going into more detail with this and the next blog. Below is a chart that displays the time complexities of these algorithms:

screenshot from https://www.geeksforgeeks.org/

Based on this chart, selection, bubble, and insertion would take a longer in a most scenarios, where as something like a merge sort would not be. To see this visually, review this YouTube video:

Visualization & Comparison of Sorting Algorithms

Selection Sort

This method sorts an array in ascending order by repeatedly selecting the minimum element and placing it at the beginning. There are different ways to implement this method, but one way would be to work with two subarrays within the original array, one part that is the sorted section and the remaining would be the unsorted section. The advantage of this is that it doesn’t use too much memory as it only makes one swap at a time. However, the disadvantage is that it uses a nested loops, which causes it to have a O(n²) time complexity. Review the code below:

Selection sort function

Bubble Sort

This method is the simplest sorting method as it was repeatedly swap adjacent elements if they are in the wrong order. This method will iterate through the array multiple times and continuously swap elements that are in the wrong order, bubbling the larger value as it goes through the array. This will continue until in runs through the array without have to swap elements (thus completely sorting the array). This method also deals with a nested loop, having a disadvantage with time complexity. However, concept wise, it’s easy to learn and understand as a first sorting algorithm. Review the code below:

Bubble sort function

Insertion Sort

This method can be compared to sorted a deck of cards in your hand. This sort also deals with two subarrays within the original array, a sorted subarray and an unsorted array. Upon each iteration, values from the unsorted array are moved into the sorted array and inserted in the correct position of the sorted array. This method also uses a nested loop, making it a disadvantage with time complexity. However, this sorting method is typically used when the number of elements are small or when only a few elements are misplaced in a large array. Note: V8 Engine of Chrome uses this type of sorting for their .sort(). Review the code below:

Insertion sort function

In the next blog, I’ll review some of the quicker sorting methods, such as merge sort! Happy sorting!

Resources:

1. “Sorting Algorithms Explained,” FreeCodeCamp, accessed October 15, 2020, https://www.freecodecamp.org/news/sorting-algorithms-explained/
2. “JS: Sorting Algorithms”, accessed October 15, 2020, https://khan4019.github.io/front-end-Interview-Questions/sort.html
3. “Time Complexities of all Sorting Algorithms,” GeeksForGeeks, accessed October 15, 2020, https://www.geeksforgeeks.org/time-complexities-of-all-sorting-algorithms/
4. “Selection Sort,” GeekForGeeks, accessed October 16, 2020, https://www.geeksforgeeks.org/selection-sort/
5. “Bubble Sort,” GeekForGeeks, accessed October 16, 2020, https://www.geeksforgeeks.org/bubble-sort/
6. “Insertion Sort,” GeekForGeeks, accessed October 16, 2020, https://www.geeksforgeeks.org/insertion-sort/