8 - Algorithms 1 (Sorting) Flashcards
What is sorting?
Operation that takes input values and places them in a specific order
Why may you need sorting?
- You need to sort (for easier readability)
- Optimise other algorithms (makes efficient search of merge), median-based statistics
What is a comparison based algorithm?
Compare two elements, if not in order then exchange
What is the best work complexity of compare and exchange?
O(nlogn)
What does the performance of comparison based algorithms depend on?
The data
What is a serial bubble sort?
Repeatedly compare and exchange the adjacent neighbours if they are in the wrong order
What is the work complexity of a serial bubble sort?
O(n2) - not recommended in practical aogirithms
How can a serial bubble sort be modified?
To detect early exit
What is a parallel odd even sort?
Parallel “bubble sort” - compare and exchange all independent neighbouring pairs in two phases (odd and even)
What is the step complexity of the odd even sort?
O(n)
What is the work complexity of the odd even sort?
O(n2)
What are good applications of the odd even sort?
Good for very small sequences (tens of elements)
What does a sorting network consist of?
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
What is the speed of a sorting network proportional to?
Its depth (number of steps)
What is the goal of sorting networks?
To design a network such its depth and number of comparators is as low as possible
What do optimal sorting networks do?
Sort N elements in smaller than O(nlogn) operations
What is a bitonic sequence?
A sequence with two tones, increasing and decreasing.
Any cyclic rotation of such sequences is also considered bitonic
What is the special property of bitonic split?
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
How do you sort a bitonic sequence?
Recursively perform bitonic split operations on it
What do a sequence of bitonic splits form?
A bitonic merge
How do you obtain a bitonic sequence from an unordered input sequence?
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
What is the two step procedure to a Bitonic sort?
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)
What is the step complexity of bitonic sort?
O(log2n)
What is the work complexity of bitonic sort?
O(nlog2n)
