Sorting Algorithms and Hash Tables: Explained and Compared

Sorting Algorithms and Their Bounds

Results like the Ω(nlgn) lower bound on all sorting via binary comparisons are difficult to establish. On the other hand, results like the O(n2) upper bound on INSERTION-SORT are easier to achieve. Explain adequately the difference in the “ease” of arriving at these results.

One result applies to all sorting algorithms that are based on binary comparisons (and so is harder to establish) while the other result is simply for one specific sorting algorithm in the same category. A more complete answer would involve an argument that rightly recognizes that the lower bound result is one that also applies to algorithms that exist and also those yet to be devised (yes, even those that may be written a hundred years from now). The result is therefore necessarily a mathematical, formal proof that is more abstract than concrete. On the other hand, the upper bound result is obtained by analyzing a concrete algorithm, one that can be done based on the structure of the algorithm, by looking at, say, the pseudo-code that implements it and applying existing techniques of analysis (as presented in class). This can almost be mechanized by a program that is not unlike that part of a compiler that does semantic analysis. The lower bound result was thus obtained using a model (decision tree) that represents all binary comparison sorting algorithms. The number of leaves in the decision tree (which was a full binary tree), had to at least match all the n! possible ways the input values can be arranged. Such a binary tree can have at the least a height that is Ω(nlgn). The height of such a tree represents the worst-case complexity of the sorting algorithm, thus the lower bound result. The upper bound result was obtained by pointing out that INSERTION-SORT involved a looping structure that is performed O(n) times, each iteration also involving O(n) time to perform, resulting in the O(n2) bound.

HEAP-SORT: An In-Place Sorting Algorithm

Explain what is meant by HEAP-SORT being an “in-place” sorting algorithm?

It simply means that HEAP-SORT does not require more than O(1) auxiliary space for doing its sorting task. And, indeed, looking at its pseudo-code, all that is needed would be a variable or two to be able to do swaps and a three-way comparison. This is unlike MERGE-SORT which involves an auxiliary array that matches the size of the array to be sorted, that is, O(n) additional space.

Collision Resolution in Hash Tables

Explain what a “collision” is in the context of hash tables and how they are resolved.

A collision occurs when two keys are mapped by the hash function to the same value. This is a natural result of the fact that the hash function’s domain is much larger than its range, that is, the hash function is a many-to-one type of function. One method for resolving collisions looks into the hash table and tries to find another open slot to hold the item that caused the collision. A simple way to do this is to start at the original hash value position and then move in a sequential manner through the slots until we encounter the first slot that is empty. Few Collision Resolution ideas: Separate chaining, Some Open addressing techniques (Linear Probing, Quadratic Probing)