This is the introduction to a series on sorting algorithms in JavaScript. You might be wondering why should you learn all these algorithms when there’s already a few built-in ways to sort lists. The short answer is: because google and large tech companies want you to know them. The long answer is: depending on the list size, different sorting algorithms will have varying efficiencies that can make a major difference in your application. The time and space complexity of the algorithms you build are very important, and that’s what will get you paid the big bucks. So let’s jump in!
As you might have guessed, a sorting algorithm takes a list of items and sorts them— normally in alphabetical or numerical order.
Learning sorting algorithms is a great way to improve your craft and demand as a software engineer. These are a great way to practice time and space complexity analysis, and come up with clever solutions to simple problems. Working on these skills now will drastically help you when you start interviewing for your next job.
This is especially true if you’re applying for any of the larger tech companies that require you to strongly understand algorithms and data structures.
In addition to the time and space complexity of sorting algorithms, the below properties help define sorting algorithms.
Adaptability: An adaptive sort’s performance improves the more sorted the list is initially
In-place: An in-place sort requires a constant amount of additional space
Parallelism: A parallel sort can split its workload between multiple workers
Stability: A stable sort preserves the order of items in the list that evaluate to the same value
Algorithmic Paradigms
Divide-and-conquer
This is a common algorithmic pattern based on recursion, which is implemented in both merge sort and quick sort. It breaks one main problem into many sub-problems that are similar to the original problem. It then recursively solves the sub-problems, and finally combines the solutions at the end. Remember, divide-and-conquer can have many more than two subproblems which means we’re really utilizing recursion.
There are three parts to a divide and conquer solution:
- Divide the problem into many subproblems that are just smaller instances of the original problem.
- Conquer the subproblems by solving them recursively.
- Combine the solutions to all subproblems into one solution for the original problem.
Brute Force This is a pretty straightforward approach to problem solving, and one I’m sure you’re familiar with. It’s considered one of the easiest to apply to small problems. As you might have guessed, this is not normally the most efficient approach that we want to take with our algorithms.
Some examples of brute force sort algorithms include bubble sort and selection sort.
Sorting algorithms to know: If you’re a beginner to sorting algorithms, I highly suggest you start with bubble sort.
- Bubble Sort
- Insertion Sort
- Merge Sort
- Bucket Sort
- Selection Sort
- Quick Sort
- Heapsort
- Counting Sort
- Comb Sort
- Cocktail Sort