Algorithms 101: Searching & Sorting

When I was watching my favorite show, Jane the Virgin, I was excited when Xiomara had a back-and-forth with Rogelio. He claimed that he was compatible with someone based on a matchmaking algorithm. She accused him of not even knowing what an algorithm is. Hah!

Well, Rogelio, an algorithm is a set of instructions for accomplishing a task. There are algorithms that are well-known patterns or are fast or solve interesting problems. For instance, weren’t you really fascinated when I wrote (and talked about) the algorithm for an unbeatable AI in tic-tac-toe?

I’ve started reading Aditya Y. Bhargava’s book, “Grokking Algorithms,” whose book includes many diagrams (visual learner FTW), memorable examples and analogies, and easy-to-read language. I was delighted by the prerequisite to reading the book: basic algebra. I love algebra so much I took the class twice (once during the summer, where I constantly competed with my older sister, and again during the school year). Geometry is another story.

Anyway, without further ado, here is an overview of what I’ve learned so far. I’ll try to recap a handful of main concepts at one time. (Also, these examples are from the book!):

Big O notation

• Definition: A special notation that tells you how fast an algorithm is, given that running times will grow at different rates and provides a worst-case scenario.
• Example: Let’s say it takes one second to check one element. With simple search, if there are 100 elements, it will take 100 seconds. With binary search, it will take 7 seconds to run since log2 (or log base 2) 100 is equal to about 7 (in other words, it takes 2 multiplied 7 times to roughly equal 100). If we were looking at 1 billion elements, simple search results in 1 billion seconds whereas binary search results in about 30 seconds. At 100 seconds, 33 Simple search and binary search do not grow at the same rate.

Simple search

• Definition: Looking at each element of a collection in order.
• Example: You have a dictionary and you’re looking for “peacock.” You start from the beginning, checking each word until you find the word “peacock.”
• Big O run time: O(n), also known as linear time.

Binary search

• Definition: Select the middle number and eliminate half of the remaining numbers every time. Binary search runs in logarithmic time (e.g. if there is a list of 100 items, it will take at most 7 guesses to get the answer).
• Example: Person A chooses a number between 1 to 100 (24). Person B has to guess A’s number and does by starting at the middle (50). A says 50 is too high so B halves that number and guesses 25, and so forth and so forth.
• Big O run time: O(log n), also known as log time.

Quicksort

• Definition: A sorting algorithm that uses “divide and conquer.”
• Example: If sorting numbers in an array, choose a pivot (an element to compare with the rest of the elements). Find all of the elements that are lower and all of the elements that are higher and partition them into sub-arrays. Sort those subarrays in the same way (e.g. choosing a pivot and arranging elements based on whether they’re lower or higher than the pivot) until every element is sorted.
• Big O run time: O(n * log n)

Selection sort

• Definition: A comparison-based algorithm in which there is a list is divided into two parts: the sorted part and the unsorted part. Initially, the sorted part is empty and the unsorted part is the entire list.
• Example: Based on a list of artists and numbers representing how many times you have played their songs, you decide to rank them based on their play count. You go through the list the first time and find the most-played artist and add it to a new list while removing it from the original list. You go through the list a second time and find the second most-played artist, and so forth until you have no more artists in the original list. You now have a new list that is sorted based on play count!