Limited access

Upgrade to access all content for this subject

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.

Select an assignment template