I mentioned in yesterday's post that a lot of data manipulation involves lists, nested and otherwise. Another common task is sorting elements in a list. Day 6 of 30 Days of Algorithms is a Merge Sort, which is another "divide-and-conquer" algorithm.
Quicksort is one of the most efficient sorting algorithm with O(log n) Big-O notation. It can be 2x - 3x faster than merge sort. It is another divide-and-conquer algorithm. The algorithm divides the list on a pivot, which can be any number in the list. Any item lower than the pivot is added to a 'left' list. Any item larger than the pivot is added to the 'right' list. The process is repeated recursively with any sub-list with more than 2 items.
Given two lists of elements, how do you find which items appear in both lists? The algorithm for Day 4 of 30 Days of Algorithms demonstrates how to find the overlap of two lists (list intersection).
Our algorithm for Day 3 of 30 Days of Algorithms is a Bubble Sort. Bubble Sort is not an efficient sort algorithm (The Big-O notation for the time complexity is 0n2) but it is useful for learning. The basic premise is very simple : Start with the first two items in the list. If the first item (left) is higher than the second item (right), swap them.
The algorithm for Day 2 of 30 Days of Algorithms is a useful formula to find a missing number in an array of numbers from 1 - N. This algorithm only works if there is one-and-only-one missing number, and no duplicate numbers. There are other algorithms for those cases which I will cover on a different day.