THINK FIRST·CODE LATER

← All labs

Quick sort: does the choice of pivot matter?

Problem

Write PivotChoice, which sorts the same data twice with quick sort (Lomuto-style partition around the element at low) and counts the comparisons of elements and the depth of the recursion:

  1. the pivot is the first element of the range;
  2. the pivot is the median of three — of the first, middle and last elements — which is first moved to position low.

Read n, then n integers. Print the first 12 sorted values, then the two counts and depths. For the input

10
5 2 9 4 7 6 1 3 8 10

the program prints

Sorted: 1 2 3 4 5 6 7 8 9 10
First element as pivot: 21 comparisons, recursion depth 4
Median of three as pivot: 34 comparisons, recursion depth 3
Both sorted correctly: true

Try an already sorted input of 500 values. Explain the two depths.

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d9-8-data-1.txt

10
5 2 9 4 7 6 1 3 8 10
What your program must print for d9-8-data-1.txt
Sorted: 1 2 3 4 5 6 7 8 9 10
First element as pivot: 21 comparisons, recursion depth 4
Median of three as pivot: 34 comparisons, recursion depth 3
Both sorted correctly: true

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d9-8-data-1.txt

Windows PowerShell does not understand <:

Get-Content d9-8-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.