ALGORITHMS
A repeatable series of steps taken to solve a problem, produce some output, or achieve a goal.
(YouTube)
But First, Recursion
A function that calls itself to break down a larger problem into smaller bits.
Ex: The Fibonacci sequence. (YouTube)
Comparison Sort Algorithms
Compare and order 2 items at a time.
Ex: Comparing a group of lego pieces based on their size. (YouTube)
BUBBLE SORT
Compare and sort 2 items and then move to the next pair. All the necessary elements will eventually “bubble” up.
Ex: It's usually used to introduce the idea of an algorithm, or it's used within more efficient sorting algorithms. (YouTube) (It's not great)
INSERTION SORT
Go down the line, select each item, and “insert” it into its proper place if needed.
Ex: When you're playing cards and you manually sort your cards in order. (YouTube)
Divide-and-Conquer Sort Algorithms
Solve problems using comparison sort and recursion.
Ex: Keep splitting a group of legos in half until you get to 1 lego, and then you put them all back together, now all sorted. (YouTube)
MERGE SORT
Split the items in half over and over until they're all sorted (divide, via the Merge Sort algorithm), and then merge the sorted pieces back together on their way back up (conquer, via the Merge algorithm).
Ex: Sorting a Linked List. (YouTube)
QUICK SORT
Divide all your items into 3 parts (the left partition, the pivot, and the right partition), then do recursion on the partitions around the sorted pivot (single value). The pivot is usually the first or last value, but it can be any random value.
Ex: Unlike Merge Sort, the hard work is done during the dividing, not the merging. (YouTube)
Distribution Sort Algorithms
Instead of comparing 2 items, you compare and group all your items by properties.
Ex: Group all your lego pieces by color. (YouTube)
BUCKET SORT
Sort items into buckets based on certain properties, and then sort within those buckets.
Ex: When sorting a large set of floating point numbers (between 0.0 and 1.0), you can create sorting "buckets" 0 through 9 and sort from there. (YouTube)
RADIX SORT
Same as Bucket Sort, but only for integers; you group each integer by certain digits.
Ex: Given a range of large numbers, sort all the numbers first by the first digit (1-9), then the next digit range (10-90) and so on. (YouTube)
Search Algorithms
Find, and sometimes retrieve, an item with a specific value in a sorted sequence.
Ex: Searching a dictionary. (YouTube)
BRUTE FORCE SEARCH
Try every possibility available.
Ex: The Traveling Salesman Problem. If a salesman needs to visit 10 cities, calculate the total distance for each possible route and then select the shortest one. (YouTube) (But avoid it when you can)
BINARY SEARCH
Find an item by repeatedly halving your search. When an array is sorted, go to the middle (left of center) and then search its left or right and go to its new middle, and so on.
Ex: Literally searching a dictionary. (YouTube)