?

Algorithms & Data Structures

Free Version

Upgrade subject to access all content

Difficult

Bubble Sort Variants for Parallelization

ALGOR-6UFOAZ

Due to the sequential nature of the bubble sort algorithm, it is difficult to parallelize. For instance, the comparison of the last two elements $n-1$ and $n-2$ depends on the comparison of elements $n-2$ and $n-3$, which in turn depends on the comparison of elements $n-3$ and $n-4$, etc.

Which of the following parallelizable bubble sort variants will correctly sort an unsorted list?

Select ALL that apply.

A

Examine only non-overlapping adjacent pairs of indices, i.e. instead of $(0,1)$, $(1,2)$, $(2,3)$, etc., compare $(0,1)$, $(2,3)$, $(4,5)$, etc.

B

Examine only non-overlapping adjacent pairs of indices, starting at index 1, i.e. $(1,2)$, $(3,4)$, $(4,5)$.

C

Examine non-overlapping adjacent pairs of indices starting at 0 on odd iterations and starting at 1 otherwise.

D

At each iteration, randomly select a partition of the unsorted list into $\lfloor \frac{n}{2} \rfloor$ non-overlapping pairs of elements for comparison.