"Searching, Sorting & Hashing" — Practice

Question 1

Which sorting algorithm always performs the same number of comparisons regardless of the input?

Accepted Answer

B

Question 2

A hash table with separate chaining has 200 slots and 500 elements. What is the load factor?

Accepted Answer

B

Question 3

Radix sort requires its inner sort to be

Accepted Answer

C

Question 4

What is the minimum number of comparisons needed in the worst case to sort 5 distinct elements, and how is the bound obtained?

Accepted Answer

Model any comparison sort as a decision tree. Each internal node is one comparison with two outcomes, and each leaf is one of the possible output orderings.

For correctness, every one of the 5 factorial = 120 input permutations must reach a distinct leaf, since each requires a different rearrangement.

A binary tree of height h has at most 2 to the h leaves, so 2 to the h must be at least 120.

Since 2 to the 6 = 64 is too few and 2 to the 7 = 128 suffices, the height must be at least 7.

The information-theoretic lower bound is therefore 7 comparisons in the worst case.

This is a lower bound, and whether it is achievable is a separate question. For n = 5 it happens to be achievable: merge insertion sort attains exactly 7 comparisons. For n = 12 the bound gives 29 but the true minimum is 30, so the bound is not always tight for small n.

The general form of the argument is the ceiling of log base 2 of n factorial, which by Stirling grows as n log n and gives the asymptotic Omega(n log n) result.

Question 5

Quicksort is run on an array of 8 elements already in ascending order, using the last element as pivot. How many comparisons does the partition step of the top-level call make, and what is the total?

Accepted Answer

The top-level partition compares the pivot against every other element, so with 8 elements it makes 7 comparisons.

Since the array is ascending and the pivot is the last element, every other element is smaller. The partition therefore places all 7 elements on the left and the pivot at the far right, giving a split of 7 and 0.

The recursion then runs on a subarray of 7 elements, which is again sorted and again splits 6 and 0.

The comparison counts across levels are 7, 6, 5, 4, 3, 2, 1, summing to 28.

That is exactly n(n-1)/2 for n = 8, which is the quadratic worst case.

The recursion depth is also 7 rather than log 8 = 3, so the stack usage becomes linear and can overflow on large inputs.

The irony worth noting is that this input — already sorted — is one of the most common in practice, which makes it the worst possible worst case for an algorithm to have. Choosing the median of the first, middle and last elements would pick the true median here and give a perfectly balanced split, reducing the total to about 8 log 8 = 24 comparisons with depth 3.

Question 6

A hash table of size 7 uses h(k) = k mod 7 with quadratic probing where the i-th probe checks (h(k) + i squared) mod 7. Insert 15, 22, 8, 29 and give the final table.

Accepted Answer

Compute each initial slot and probe with increasing squares on collision.

15 mod 7 = 1. Slot 1 is free. Placed at 1.

22 mod 7 = 1. Slot 1 is occupied. Probe i = 1: (1 plus 1) mod 7 = 2. Free. Placed at 2.

8 mod 7 = 1. Slot 1 occupied. Probe i = 1: slot 2, occupied. Probe i = 2: (1 plus 4) mod 7 = 5. Free. Placed at 5.

29 mod 7 = 1. Slot 1 occupied. Probe i = 1: slot 2, occupied. Probe i = 2: slot 5, occupied. Probe i = 3: (1 plus 9) mod 7 = 10 mod 7 = 3. Free. Placed at 3.

The final table holds 15 at slot 1, 22 at slot 2, 29 at slot 3, and 8 at slot 5, with slots 0, 4 and 6 empty.

Two observations. All four keys hashed to slot 1, so they followed identical probe sequences — this is secondary clustering, which quadratic probing does not eliminate. And quadratic probing does not necessarily visit every slot: with a table size of 7 and this step function, the reachable offsets are the quadratic residues, so some slots may be unreachable from a given start. Guaranteeing full coverage requires the table size to be prime and the load factor kept below one half, or a specifically chosen probe function.

Question 7

An embedded system with 4 KB of RAM must sort 500 sensor readings, each a 16-bit integer in the range 0 to 1023, with a hard real-time deadline. Which sort should be used and why?

Accepted Answer

Work through the constraints in order.

The hard deadline rules out quicksort. Its average case is excellent but its worst case is quadratic, and a real-time system must be designed against the worst case rather than the average. No pivot strategy makes the worst case impossible, only unlikely.

The memory constraint rules out merge sort. It needs Theta(n) auxiliary space, which for 500 sixteen-bit values is 1 KB on top of the 1 KB the data already occupies, consuming half the available RAM.

That leaves heapsort among the comparison sorts. It guarantees n log n in every case and sorts in place with O(1) extra space, so it satisfies both constraints. For 500 elements that is roughly 500 times 9 = 4500 comparisons.

But the key range opens a better option. The values lie in 0 to 1023, so k = 1024, which is comparable to n = 500. Counting sort costs Theta(n plus k) = 500 plus 1024, about 1500 operations — three times fewer than heapsort, with a completely deterministic running time.

The cost is the counter array: 1024 counters. At 16 bits each that is 2 KB, which fits in the remaining budget but is tight. Using 8-bit counters would suffice only if no value repeats more than 255 times, which for 500 readings is guaranteed.

The recommendation is counting sort with 8-bit counters, using 1 KB for counters and giving deterministic linear time. If the memory proved too tight, heapsort is the correct fallback, since it is the only comparison sort meeting both the worst-case and the space constraint.

Question 8

Explain why linear probing degrades faster than chaining as the load factor rises, using the probe-count formulas, and state the practical resizing thresholds each implies.

Accepted Answer

For separate chaining, an unsuccessful search hashes to a slot and walks the whole chain there. The expected chain length is exactly the load factor alpha, so the expected cost is 1 plus alpha — linear in alpha with slope 1.

At alpha = 0.5 that is 1.5 probes. At alpha = 1 it is 2. At alpha = 2 it is 3. The growth is gentle and unbounded, so the table never fails, it merely slows.

For linear probing, the expected unsuccessful probe count is approximately one half times (1 plus 1 over (1 minus alpha) squared).

At alpha = 0.5 that gives one half times (1 plus 4) = 2.5. At alpha = 0.75 it gives one half times (1 plus 16) = 8.5. At alpha = 0.9 it gives one half times (1 plus 100) = 50.5.

The difference is the squared term in the denominator. As alpha approaches 1, the quantity 1 minus alpha approaches zero and its square approaches zero faster, so the reciprocal explodes.

The underlying cause is primary clustering. When a run of occupied slots forms, any key hashing anywhere within that run must probe past all of it, and the run then grows by one at its end — making it even more likely to absorb the next insertion. Runs merge, and merged runs grow faster still, so the cost is superlinear rather than linear.

The practical consequences follow directly. Chained tables are commonly resized at alpha around 1 to 2, since the cost is still small there. Open-addressed tables are resized at alpha around 0.7, well before the formula turns sharply, and never allowed near 0.9.

Question 9

Define stability, explain why it matters, and determine which of merge sort, quicksort, heapsort and counting sort are stable, with the reason in each case.

Accepted Answer

A sort is stable if elements comparing equal retain their relative input order in the output.

It matters whenever records are sorted on more than one field. Sorting employees by department and then by salary produces a correct within-department salary order only if the second sort is stable, since an unstable one would scramble the department grouping. Stability is what makes multi-key sorting composable, and it is exactly why radix sort works at all.

Merge sort is stable, provided the merge takes from the left half when two elements compare equal. That single tie-breaking rule is the whole of it; taking from the right instead yields a correct but unstable sort.

Quicksort is not stable. The partition swaps elements across long distances, and an element can be swapped past an equal element that originally preceded it. Stable variants exist but require auxiliary space, which forfeits quicksort's main advantage.

Heapsort is not stable. Sifting moves values along root-to-leaf paths and the swap that places an element can jump it past an equal one arbitrarily. There is no simple tie-breaking fix, because the heap's partial order does not track insertion sequence.

Counting sort is stable if the output array is filled by scanning the input from right to left while decrementing the running counts. Scanning left to right instead reverses equal elements and makes it unstable, which would then break any radix sort built on it.

Selection sort is worth adding as a contrast among the quadratic sorts: it is the only one of bubble, insertion and selection that is unstable, because swapping the minimum into place jumps it past equal elements.

Practice — "Searching, Sorting & Hashing"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities