Algoritmika 2026/27 sügis

HW2. Dual-Pivot Quicksort, Binary Search, and Divide-and-Conquer

Deadline: Monday, 14.09.2026, 23:59

Purpose

This homework studies how algorithm design, pivot selection, input structure, and recursion shape affect sorting and searching. You will implement an instrumented dual-pivot Quicksort, investigate how randomisation changes its behaviour, measure the logarithmic growth of binary search, and use binary search itself to find an input size with a specified search cost.

General requirements

• Reuse the reporting and reproducibility practices from HW1.
• Test correctness before measuring performance.
• Use identical input instances when comparing methods.
• Report random seeds and use several seeds for randomised experiments.
• Count every comparison between input values, including comparisons used to order pivots. Do not count index or loop-condition checks as element comparisons.
• Exclude input generation and copying from measured algorithm time. If these costs matter, report them separately.
• Stop an individual run if it exceeds 30 seconds or reaches a recursion or resource limit. Record the failure as evidence instead of hiding it.
• Keep interpretations concise and support them with a table, plot, trace, or counterexample.

Base tasks

T1. Implement and validate dual-pivot Quicksort (1p)

Implement an in-place dual-pivot Quicksort without calling a library sorting function inside the implementation.

For each recursive call, choose two pivot elements p <= q and partition the input into three regions:

• values smaller than p;
• values between p and q;
• values greater than q.

For this task, use a deterministic baseline rule: take the first and last elements of the current region as pivots. State precise partition invariants and explain which regions are processed recursively.

Handle equal values carefully. In particular, explain and test what happens when p == q. The algorithm must terminate correctly on all-equal and duplicate-heavy inputs, without repeatedly sorting a region already known to contain only pivot-equal values.

Test empty, one-element, two-element, sorted, reverse-sorted, random, all-equal, and duplicate-heavy inputs. Compare every result with a trusted library sort.

Deliverable: implementation, correctness tests, and a concise explanation of the partition invariants, recursive ranges, and duplicate handling.

T2. How does random pivot selection help? (1p)

Extend T1 with two pivot-selection strategies:

1. first and last elements;
2. two positions chosen uniformly at random without replacement.

Keep the partition implementation and all other algorithm details unchanged. Use fixed and reported random seeds.

Compare the strategies on random permutations, sorted input, reverse-sorted input, almost-sorted input, and duplicate-heavy input. Use at least four increasing input sizes and at least five seeds for the randomised strategy.

Measure:

• element comparisons;
• running time;
• maximum recursion depth.

If a deterministic run reaches the time limit, recursion limit, or another resource limit, report where it fails. Do not omit that input.

Explain why two uniformly random pivots have expected relative ranks near 1/3 and 2/3. Discuss how this affects partition balance and expected recursion depth, and why randomisation improves expected behaviour without removing the theoretical worst case.

Deliverable: a comparison-count plot, a recursion-depth plot or table, a compact timing table, and at most 200 words connecting pivot ranks, input order, partition balance, and performance.

T3. Binary search at scale (1p)

Implement lower-bound search and instrument it to count element comparisons. Test the implementation before measuring it.

Create a compact sorted numeric array with at least n0 = 10_000_000 elements, or a larger size if the environment allows it comfortably. Report the array representation, numeric type, and memory used.

Perform uniformly distributed membership queries for exactly 10 seconds. Generate the queries before timing and use a fixed seed. Report:

• searches completed in 10 seconds;
• average comparisons per search;
• time per search.

Then find the largest n < n0 for which at least twice as many searches can be completed in the same 10 seconds.

Do not run a full 10-second experiment for every candidate size. You may use at most three full 10-second runs in total, including the baseline and final verification. Short pilot measurements used to locate the candidate may consume at most 10 additional seconds in total.

Use theory, comparison counts, and the limited pilot measurements to guide an outer search on n. State how the measurement budget was allocated.

Compare the measured size with the theoretical prediction obtained from log2(n). Explain why memory hierarchy, array representation, and implementation overhead may make the measured result different.

Deliverable: code and correctness tests, the baseline and final throughput measurements, the outer-search trace, the resulting size and reduction factor, the measurement-budget allocation, and at most 180 words of interpretation.

T4. When is sorting before searching worthwhile? (1p)

For one randomly ordered array of n = 100_000 distinct values, compare two strategies for answering a sequence of membership queries:

1. answer every query by linear search on the unordered array;
2. sort once using the randomised dual-pivot Quicksort from T2, then answer every query using lower-bound search from T3.

Generate one fixed query sequence containing both present and absent values. Use identical data and queries for both strategies. Include the one-time sorting cost in both the comparison count and total running time of the second strategy.

Use your measured comparison counts to estimate the smallest number of queries q for which sorting once becomes worthwhile. Test several values immediately below and above this estimate. Repeat the experiment with three data/query seeds.

Compare the measured crossover with a theoretical estimate based on

q * n

and


n * log2(n) + q * log2(n).

Explain why the timing crossover need not equal the comparison-count crossover.

Deliverable: one compact crossover table or plot and at most 180 words connecting the theoretical estimate, measured comparisons, and running time.

T5. Recurrences behind the experiments (1p)

Consider the following idealised recurrences:

L(n) = L(n/2) + 1

Q(n) = 3Q(n/3) + n

W(n) = W(n - 2) + n

Assume constant-size base cases.

For each recurrence:

1. identify the algorithmic situation from T1-T4 that it models;
2. derive its asymptotic growth;
3. state whether the Master Theorem applies and justify the answer.

The recurrence Q(n) represents an ideal balanced dual-pivot partition, not every random partition. The recurrence W(n) represents a case where two pivots are removed but almost all remaining values stay in one recursive region.

Finally, use evidence from T2 to explain which recurrence better describes deterministic endpoint pivots on ordered inputs and why random pivot selection usually moves the observed behaviour closer to the balanced model.

Deliverable: three concise derivations and an evidence-based interpretation of the recurrences, at most 300 words in total.

Bonus task

B1. Run-aware sorting challenge (bonus 1p)

Design a sorting method that identifies ascending and descending runs and uses them to beat your randomised dual-pivot Quicksort from T2. You may merge useful runs and fall back to dual-pivot Quicksort when the input contains too many short runs.

Test random, sorted, reverse-sorted, almost-sorted, and randomly ordered sorted-block inputs. Use large enough inputs for the timing difference to be meaningful. Include run detection, method selection, and any copying or temporary storage in the measured cost.

To complete the challenge, the run-aware method must be faster on at least two run-structured input families. Report its overhead on a random permutation as well.

Deliverable: implementation, detected run counts and lengths, one compact comparison table or plot, and at most 150 words explaining when the hybrid wins or loses.

Submission checklist

• Each algorithm has correctness tests.
• Compared methods use identical input instances and query sequences.
• Random seeds and stopping conditions are reported.
• Raw measurements and comparison counts are included with the code or data.
• The report distinguishes measured evidence from theoretical expectations.
• The report remains concise and includes only plots, tables, and traces that support an argument.
• Report and code/source files are uploaded separately.