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: 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. In this example, 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)$.

	<- - - - - - - - - - - - - - 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 ${\mathcal {O}}(\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.

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)

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.

AbstractQuicksorter

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

constructor and instance variables

constructor: public AbstractQuicksorter(Shuffler<T> shuffler)

Hang onto the shuffler in an instance variable for later use.

shuffler

method: public Shuffler<T> shuffler() (sequential implementation only)

Return the shuffler passed to the constructor.

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);

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 use to leverage the Partitioner passed to the constructor to perform the divide step.

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)

Performs the bulk of the work. All forked tasked must be added to the futures queue.

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

Requirement:

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: Quicksort_Parallel_Partitioner

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