8 - Algorithms 1 (Sorting)

Question 1

What is sorting?

Answer 1

Operation that takes input values and places them in a specific order

Question 2

Why may you need sorting?

Answer 2

• You need to sort (for easier readability)

- Optimise other algorithms (makes efficient search of merge), median-based statistics

Question 3

What is a comparison based algorithm?

Answer 3

Compare two elements, if not in order then exchange

Question 4

What is the best work complexity of compare and exchange?

Answer 4

O(nlogn)

Question 5

What does the performance of comparison based algorithms depend on?

Answer 5

The data

Question 6

What is a serial bubble sort?

Answer 6

Repeatedly compare and exchange the adjacent neighbours if they are in the wrong order

Question 7

What is the work complexity of a serial bubble sort?

Answer 7

O(n2) - not recommended in practical aogirithms

Question 8

How can a serial bubble sort be modified?

Answer 8

To detect early exit

Question 9

What is a parallel odd even sort?

Answer 9

Parallel “bubble sort” - compare and exchange all independent neighbouring pairs in two phases (odd and even)

Question 10

What is the step complexity of the odd even sort?

Answer 10

O(n)

Question 11

What is the work complexity of the odd even sort?

Answer 11

O(n2)

Question 12

What are good applications of the odd even sort?

Answer 12

Good for very small sequences (tens of elements)

Question 13

What does a sorting network consist of?

Answer 13

Comparators and wires

Wires carry values

Each comparator connects two wires and swaps the values if the top wire’s value is greater

Arranged in columns each representing a single step

Output is sorted top to bottom

Question 14

What is the speed of a sorting network proportional to?

Answer 14

Its depth (number of steps)

Question 15

What is the goal of sorting networks?

Answer 15

To design a network such its depth and number of comparators is as low as possible

Question 16

What do optimal sorting networks do?

Answer 16

Sort N elements in smaller than O(nlogn) operations

Question 17

What is a bitonic sequence?

Answer 17

A sequence with two tones, increasing and decreasing.

Any cyclic rotation of such sequences is also considered bitonic

Question 18

What is the special property of bitonic split?

Answer 18

If you split one bitonic sequence into two parts and perform compare and exchange operation on each element of both parts, you get bitonic sequences.

All elements in part one are smaller than those in part two

Question 19

How do you sort a bitonic sequence?

Answer 19

Recursively perform bitonic split operations on it

Question 20

What do a sequence of bitonic splits form?

Answer 20

A bitonic merge

Question 21

How do you obtain a bitonic sequence from an unordered input sequence?

Answer 21

Merge two pairs of two elements to form a bitonic sequence of length 4

Sort first two elements using a comparator

Sort the next two using a reverse comparator

Repeat but with 8 instead of 4 and so on

Question 22

What is the two step procedure to a Bitonic sort?

Answer 22

Convert an unordered sequence into a bitonic sequence (apply a set of bitonic merges)

Sort the bitonic sequence into an ordered sequence (final bitonic merge)

Question 23

What is the step complexity of bitonic sort?

Answer 23

O(log2n)

Question 24

What is the work complexity of bitonic sort?

Answer 24

O(nlog2n)