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.

Mistakes To Avoid

Warning: Be sure to invoke the provided Partitioner's partitionRange method.

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

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.

SequentialPartitioner

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.

Sorter

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

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 partitioner sortRange
package:	sort.quick.exercise
source folder:	student/src/main/java

SequentialQuicksorter

Warning:Do NOT implement your own partition in either the sequential or parallel quicksorters. Use the partitioner specified to your constructor.

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

Implement the classic divide and conquer sequential algorithm here.

Warning:Be use to leverage the provided private final Partitioner<T> partitioner; field to perform the divide step.

ParallelQuicksorter

class:	ParallelMergeSorter.java
methods:	kernel sortRange
package:	sort.merge.studio
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.

kernel

private void kernel(Queue<Future<?>> futures, T[] data, Comparator<T> comparator, int min, int maxExclusive)

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

Warning:Be use to leverage the provided private final Partitioner<T> partitioner; field to perform the divide step.

Warning:Do not join the tasks here. Joining is the responsibility of the sortRange method.

sortRange

This method is partially provided. Invokes kernel on the complete range with a ConcurrentLinkedQueue.

When kernel 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 group warmup.

	@Override
	public void sortRange(T[] data, Comparator<T> comparator, int min, int maxExclusive)
			throws InterruptedException, ExecutionException {
		Queue<Future<?>> futures = new ConcurrentLinkedQueue<>();
		kernel(futures, data, comparator, min, maxExclusive);

		throw new NotYetImplementedException();

	}

Warning:do not call sortRange recursively. kernel 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