Weird Data Structure & Algorithm Names
How did our beloved data structures and algorithms get their names?
Some of the algorithms that we encounter are named upon their inventors, for example, Dijkstra’s shortest path algorithm is named after the computer scientist Edsger W. Dijkstra who conceived the algorithm in 1956. Similarly, the Knuth-Morris-Pratt (KMP) algorithm for searching a word within another text string is named after James H. Morris, Donald Knuth and Vaughan Pratt.
Most of the data structures and algorithms are based on how they behave or look like. For instance, queues and stacks are named because of their push and pop behaviors. Trees are called trees because they look like inverted trees. Similarly, there are many algorithms, like insertion sort, or merge sort which are very easy to relate to their names.
But, there are some data structures and algorithms which are not very easy to associate with their names. Here I present some of them:
Cuckoo Hashing
Cuckoo Hashing is a hashing algorithm which offers O(1) worst case look up. It works as follows:
We maintain 2 hash tables, and a hash function corresponding to each hash table. So, let us assume that the hash tables are H1 and H2. The hash function for H1 is f1 and the hash function for H2 if f2. Now, let’s say we have to enter value x. We first check if H1[f1(x)] is empty. If it is, we place x at that position in H1.
If it is not empty, we make space for x in H1 by moving the element at that place, let’s sat y, to H2. We move the value y in the second hash table H2 at H2[f2(y)]. This process goes on and on, i.e, if H2[f2(y)] would not have been empty, we would have moved that element, z, back to H1 at the position H1[f1(z)].
How did cuckoo come into the scene? It so happens that certain species of cuckoo chick pushes the other eggs or young out of the nest when it hatches to create space for itself! Hence, cuckoo hashing. Interesting, right?
A red–black tree is a kind of self-balancing binary search tree.
The nodes in the red-black tree, as can be guessed from the name itself, are either colored red or black, and are used to ensure that the tree remains balanced whenever insertions or deletions happen.
I always wondered the significant of these colors. Well, they could have used any other colors, why only black and red ? Turns out that was because black and red were the best-looking colors produced by the color laser printer available to the authors while working at Xerox PARC.
Bubble Sort or Sinking Sort
Okay, I know this is an easy one! Bubble sort is one of the three most basic sorting algorithms.
In bubble sort, we compare the adjacent elements, and swap them in case the left one is greater than the right one.
Each time we go from left to right performing these swaps, the largest element in the unsorted array sinks to the end. And in the process, the small elements bubble up. Hence the name Bubble Sort or Sinking Sort.
Keep tuned in for more ;)
Source:
https://en.wikipedia.org/wiki/
