Sequential Quicksort17 4 22 11 63 65 14 Recursively
apply quicksort
to high list
Parallel Programming in C with MPI and OpenMP Michael J. Quinn
Chapter 14 Sorting
Outline
Sorting problem
Sequential quicksort
Parallel quicksort
Hyperquicksort
Parallel sorting by regular sampling
Sorting Problem
Permute: unordered sequence ordered sequence
Typically key (value being sorted) is part of record with additional values (satellite data)
Most parallel sorts designed for theoretical parallel models: not practical
Our focus: internal sorts based on comparison of keys
Sequential Quicksort
17 14 65 4 22 63 11 Unordered list of values
Sequential Quicksort
17 14 65 4 22 63 11 Choose pivot value
Sequential Quicksort
17 14 65 4 22 63 11 Low list
( 17) High list
(> 17)
Sequential Quicksort
17 4 65 11 22 63 14 Recursively
apply quicksort
to low list
Sequential Quicksort
17 4 22 11 63 65 14 Recursively
apply quicksort
to high list
Sequential Quicksort
17 4 22 11 63 65 14 Sorted list of values
Attributes of Sequential Quicksort
Average-case time complexity: (n log n)
Worst-case time complexity: (n2)
Occurs when low, high lists maximally unbalanced at every partitioning step
Can make worst-case less probable by using sampling to choose pivot value
Example: “Median of 3” technique
Quicksort Good Starting Point for Parallel Algorithm
Speed
Generally recognized as fastest sort in average case
Preferable to base parallel algorithm on fastest sequential algorithm
Natural concurrency
Recursive sorts of low, high lists can be done in parallel
Definitions of “Sorted”
Definition 1: Sorted list held in memory of a single processor
Definition 2:
Portion of list in every processor’s memory is sorted
Value of last element on Pi’s list is less than or equal to value of first element on Pi+1’s list
We adopt Definition 2: Allows problem size to scale with number of processors
Comments