Algorithms are a list of steps you follow to solve a problem. They are the processes and formulas that turn our questions into answers. One easy problem-solving technique is divide and conquer, tackling smaller sub-problems rather than the entire problem at once. Divide and conquer is especially useful in sorting (or ordering) algorithms super efficiently.
Computers sort information all the time. If everything is in order, whether descending or ascending, then it is easier to find something. Think of your email application sorting messages by date or a search engine sorting websites to give you the best results. Computer scientists have devised many algorithms, from simple to complex, for sorting an array (or list) of values.
Three common sorting algorithms include:
- Bubble Sort - Compares two adjacent items and swaps them if they are out of order. Smaller or larger elements then "bubble" to the top of the list, giving the algorithm its name. Although it’s simple, bubble sort is too slow and impractical for most problems.
- Insertion Sort - Create a subarray from the items already analyzed. Then, loop through the subarray with each new item and insert it in the right order. On average, Insertion Sort requires only half as many comparisons as Bubble Sort.
- Quicksort - A more advanced sort that uses the divide-and-conquer method (or recursion).
The relative efficiency of each sorting method becomes more obvious when a larger number of items are being sorted. Think of efficiency as how many steps or how much time it will require to solve the problem. In practice, strategies that focus on solving subproblems efficiently using the divide-and-conquer method are the fastest and most commonly used, like Quicksort.
This Ted-Ed video offers a fun way to see each of these sorting algorithms in action. In the video, you are asked to imagine yourself as a university librarian. A shipment of 1,280 books has just arrived, and it’s your job to sort them in the most efficient amount of time.