Sorting and Selection

Sorting and Selection

1. Bucket-Sort

   • Not based on comparisons algorithm, but on using keys as indices into a bucket array B that has cells indexed from 0 to N-1
     • Runs in O(n+N) time
     • Uses O(n+N) space
     • Efficient when the range N is smaller than the sequence n

2. Radix-Sort

   • Sorts a sequence S of entries with keys that are in pairs
   • It applies a stable bucket-sort on the sequence twice

3. Comparing Sorting Algorithms

   • Consider Running Time among other factores

4. Selection

   • Selecting the smallest element from an unsorted collection of n comparable elements
   • Prune-and-search: we solve a given problem that is defined on a collection of n objects by pruning away a fraction of the n objects and recursively solving the smaller problem
     • When the problem is reduced to one defined on a constant sized collection of objects, we solve the problem using a brute-force method
   • Randomized Quick-Select
     • Runs in O(n) expected time, O(n^2) worst case time

Bilder und Dateien der Mindmap