Quicksort Assignment

Motivation

Sorting is a problem that is well solved by divide and conquer algorithms. Quicksort is an oldie but a goodie. Developed in 1959 by Tony Hoare, it is still the fastest sort after all these years. As a bonus, the conquer portion can be easily parallelized. The divide portion can also be parallelized, although not trivially (which left as an optional fun challenge for those so inclined).

Background

In computer science, quicksort is a sorting algorithm which selects a pivot value, partitions all the values less than the pivot value on one side and the values greater on the other. By recursively performing this operation on the ever decreasing range lengths on the left and right, the array is sorted when the range length reaches a size of 1.

For more information on how this process works, visit the wikipedia page on quicksort.

Video: Parallel Quicksort

Visualization

If you are unclear on how merge sort works, take a look at the visualgo explanation and visualization of quicksort.

Work and Span

Partition does the work of quicksort. The top-level partition must do N work. The next level does two ~N/2 partitions. The level below that performs four ~N/4 partitions. And so on. The table is $N$ wide and $\log N$ high. Thus the work of quicksort is $O(N\log N)$.

For N=16:

	<- - - - - - - - - - - - - - N - - - - - - - - - - - - - ->
^	partition [0, 16)
|	partition [0, 8)								partition [8, 16)
lg N	partition [0, 4)				partition [4, 8)				partition [8, 12)				partition [12, 16)
|	partition [0, 2)		partition [2, 4)		partition [4, 6)		partition [6, 8)		partition [8, 10)		partition [10, 12)		partition [12, 14)		partition [14, 16)
v	base	base	base	base	base	base	base	base	base	base	base	base	base	base	base	base

The span for the classic sequential partition is one partition of each of the levels (highlighted in blue). This works out to be the geometric series:

$N+{\frac {N}{2}}+{\frac {N}{4}}+{\frac {N}{8}}+{\frac {N}{16}}+\cdots +1$

which is:

$2N$

As a challenge problem, we parallelize the partition step, resulting in a span for quicksort of an outstanding $\lg ^{k}{}n$.

Mistakes To Avoid

Warning: Be sure to invoke the Partitioner provided to the Sorter's constructor's partitionRange method. Do not implement SequentialPartioner and then re-implement it in the Sorters.

Warning: When checking the base case, remember to account for [minInclusive, maxExclusive). It is all too easy to get an off by 1 error and stack overflow.

Warning: When transitioning to sequential, make sure to NOT sort the entire array when you are only responsible for a range [min,max).

WarmUp

The JoinAll WarmUp prepares you for getting around with ConcurrentLinkedQueue's weakly consistent iterators. It is highly recommended.

Client

class:	QuicksortClient.java	CLIENT
package:	sort
source folder:	student/src/sort.quick.client/java

Note: Quicksort is not stable. You can see that after sorting by name, this is not preserved when sorting by length. For example, the 3 of length 4 come out Hera, Ares, Zeus.

QuicksortClient

// https://en.wikipedia.org/wiki/Twelve_Olympians String[] olympians = { "Zeus", "Hera", "Athena", "Apollo", "Poseidon", "Ares", "Artemis", "Demeter", "Aphrodite", "Dionysus", "Hermes", "Hephaestus", }; Shuffler<String> shuffler = new LinearShuffler<>(new Random(System.currentTimeMillis())); Partitioner<String> partitioner = new SequentialPartitioner<>(); IntPredicate isParallelDesired = (rangeLength) -> rangeLength > 3; Sorter<String> sequentialQuicksorter = new SequentialQuicksorter<>(shuffler, partitioner); Sorter<String> parallelQuicksorter = new ParallelQuicksorter<>(shuffler, partitioner, isParallelDesired, sequentialQuicksorter); System.out.println(" original: " + Arrays.toString(olympians)); parallelQuicksorter.sort(olympians, Comparator.naturalOrder()); System.out.println(" sorted by name: " + Arrays.toString(olympians)); Comparator<String> lengthComparator = (a, b) -> b.length() - a.length(); parallelQuicksorter.sort(olympians, lengthComparator); System.out.println("sorted by length: " + Arrays.toString(olympians));

QuicksortClient Output
original: [Zeus, Hera, Athena, Apollo, Poseidon, Ares, Artemis, Demeter, Aphrodite, Dionysus, Hermes, Hephaestus] sorted by name: [Aphrodite, Apollo, Ares, Artemis, Athena, Demeter, Dionysus, Hephaestus, Hera, Hermes, Poseidon, Zeus] sorted by length: [Hephaestus, Aphrodite, Dionysus, Poseidon, Artemis, Demeter, Athena, Hermes, Apollo, Hera, Ares, Zeus]

Code to Implement

Both the sequential and parallel quicksorts will be passed a Partitioner. Partitioning occurs during the divide phase of divide-and-conquer of the general recursive case.

You will need to implement quicksort sequentially and in parallel. Both implementations will naturally be recursive. The kernel method should call itself using recursion, but each public quicksort method should only call its kernel once to do the work.

AbstractPartitioner

class:	AbstractPartitioner.java
methods:	constructor initialIndexSelector
package:	sort.quick.exercise
source folder:	student/src/main/java

SequentialPartitioner

class:	SequentialPartitioner.java
methods:	partitionRange
package:	sort.quick.exercise
source folder:	student/src/main/java

partitionRange

method: public PivotLocation partitionRange(T[] data, Comparator<T> comparator, int min, int maxExclusive) (sequential implementation only)

There are many approaches to partition with different performance characteristics.

Requirements:

All values left of the returned PivotLocation must be less than or equal to the value at the PivotLocation

All values right of the returned PivotLocation must be greater than or equal to the value at the PivotLocation.

All values at the Pivot Location must be equal.

The pivot location must divide the problem into smaller sub-problems.

Alert:The HackerRank approach from the prep does not maintain the pivot value at the PivotLocation. Thus the range between the pivot location's maxExclusiveOfLesserSide and minOfGreaterSide will be 0 in length. As a result, care must be taken to ensure that partition produces a pivot such that there are always smaller sub-problems.

Alert:The HackerRank approach from the prep chooses the value at the midpoint as its pivot value. Critically, it calculates the midpoint based on the *inclusive* maximum. Believe it or not, the entire algorithm death spirals if you choose the midpoint based on the exclusive max.

Although an interesting challenge, you are not required handle the Dutch national flag problem.

interface Sorter

class:	Sorter.java
methods:	sort
package:	sort.core
source folder:	student/src/main/java

sort

method: default void sort(T[] data, Comparator<T> comparator) (sequential implementation only)

This should be already complete from the Merge Sort Exercise.

class SequentialQuicksorter

class:	SequentialQuicksorter.java
methods:	sortRange
package:	sort.quick.exercise
source folder:	student/src/main/java

public class SequentialQuicksorter<T> extends AbstractQuicksorter<T>

constructor and instance variable

public SequentialQuicksorter(Shuffler<T> shuffler, Partitioner<T> partitioner) {
	super(shuffler);
	throw new NotYetImplementedException();
}

partitioner

method: public Partitioner<T> partitioner() (sequential implementation only)

sortShuffledRange

method: @Override protected void sortShuffledRange(T[] data, Comparator<T> comparator, int min, int maxExclusive) (sequential implementation only)

Implement the classic divide and conquer sequential algorithm here.

Alert:Be sure to leverage the Partitioner passed to the constructor to perform the divide step.

sortRange

method: public void sortRange(T[] data, Comparator<T> comparator, int min, int maxExclusive) (sequential implementation only)

Quicksort's performance depends on shuffling the input array. Use the provided shuffler to shuffle the array and then invoke the abstract method sortShuffledRange, which each subclass will implement.

protected abstract void sortShuffledRange(T[] data, Comparator<T> comparator, int min, int maxExclusive);

=class ParallelQuicksorter

class:	ParallelQuicksorter.java
methods:	partitioner isParallelDesired sequentialSorter sortShuffledRangeHelper sortShuffledRange
package:	sort.quick.exercise
source folder:	student/src/main/java

Adapt your sequential algorithm to take advantage of what can be parallelized.

What can be in parallel?

What is dependent on the parallel tasks completing?

Warning:Leverage the provided private final IntPredicate isParallelDesired; field to test whether or not parallelism is warranted for the current range length.

Warning:Fall back to the provided private final Sorter<T> sequentialSorter; field when the isParallelDesired predicate indicates that parallelism is not longer warranted.

constructor and instance variables

public ParallelQuicksorter(Shuffler<T> shuffler, Partitioner<T> partitioner, IntPredicate isParallelDesired, Sorter<T> sequentialSorter) {
	super(shuffler);
	throw new NotYetImplementedException();
}

partitioner

method: public Partitioner<T> partitioner() (sequential implementation only)

isParallelDesired

method: public IntPredicate isParallelDesired() (sequential implementation only)

sequentialSorter

method: public Sorter<T> sequentialSorter() (sequential implementation only)

sortShuffledRangeHelper

method: private void sortShuffledRangeHelper(Queue<Future<Void>> futures, T[] data, Comparator<T> comparator, int min, int maxExclusive) (parallel implementation required)

This method implements the essence of quicksort.

Test this isParallelDesired predicate on the range length first. If it passes, invoke the partitioner to perform the majority of the work followed by appropriately parallel recursive tasks. If the predicate does not pass the test, simply invoke the sequentialSorter.

Requirement:

Do not invoke the partitioner if the predicate fails the test. Let the sequential sorter handle it from here.

Requirements:

All forked tasks must be added to the futures queue.

Do not join the tasks in this method. Joining is the responsibility of the sortShuffledRange method.

sortShuffledRange

This method is partially provided. Invokes sortShuffledRangeHelper on the complete range, and passes an additional ConcurrentLinkedQueue to capture the Futures associated with any and all forked tasks.

@Override
protected void sortShuffledRange(T[] data, Comparator<T> comparator, int min, int maxExclusive) throws InterruptedException, ExecutionException {
	Queue<Future<Void>> futures = new ConcurrentLinkedQueue<>();
	sortShuffledRangeHelper(futures, data, comparator, min, maxExclusive);

	throw new NotYetImplementedException();

}

When sortShuffledRangeHelper is complete, each task in the queue must be joined. Since ConcurrentLinkedQueue's iterators are weakly consistent, and all of the tasks may not yet be in the queue, we must join all the tasks as in the Join All warmup.

Alert:do not call sortShuffledRange recursively. sortShuffledRangeHelper should do the recursive work.

Challenge

You can divide and conquer the divide step in quicksort. The pan can be improved from ${\mathcal {O}}(n)$ down to ${\mathcal {O}}(\lg ^{k}{}n)$.

For details on how to complete this challenge, check out: Parallel Partition

Testing Your Solution

class:	__QuicksorterTestSuite.java
package:	sort.quick.exercise
source folder:	testing/src/test/java

Note: In an effort to aid debugging, most testing will use a NoOpShuffler that does not do anything to the data when asked to shuffle.

public final class NoOpShuffler<T> implements Shuffler<T> {
    @Override
    public void shuffle(T[] data, int min, int maxExclusive) {
        // do nothing
    }
}

Pledge, Acknowledgments, Citations

file:

quicksort-pledge-acknowledgments-citations.txt

More info about the Honor Pledge