Parallel Partition

From CSE231 Wiki
Revision as of 09:31, 1 April 2023 by Cosgroved (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Partition does almost all of the work of quicksort. Further, the classic sequential partition, although wonderful, dominates the span of the quicksort algorithm. If we can parallelize partition, the span can be improved from down to .

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

(Optional) Parallel Partition Challenge

The partitioning step can also be done in parallel with Scan remarkably similar to how Pack worked.

class: ParallelPartitioner.java Java.png
methods: partitionRange
package: sort.quick.challenge
source folder: student/src/main/java

method: PivotLocation partitionRange(int[] data, int min, int maxExclusive) Parallel.svg (parallel implementation required)

Testing Your Solution

Correctness

class: _ParallelPartitionerTestSuite.java Junit.png
package: sort.quick.challenge
source folder: testing/src/test/java