Laufzeit

Question 1

Insertion Sort

Answer 1

• In Place
• Best Case: (O(n))
• Average Case: (O(n^2))
• Worst Case: (O(n^2))
• Stabil

Question 2

Merge Sort

Answer 2

• Out of Place
• Best Case: (O(n log n))
• Average Case: (O(n log n))
• Worst Case: (O(n log n))
• Stabil

Question 3

Bucket Sort

Answer 3

• Out of Place
• Best Case: (O(n))
• Average Case: (O(n))
• Worst Case: (O(n^2)), wenn alle Elemente in einen einzigen Bucket fallen.
• Bucket Sort kann stabil sein, wenn die inneren Sortiervorgänge (wie Insertion Sort) stabil sind.

Question 4

Radix Sort

Answer 4

• Out of Place
  • Best Case: (O(d(n+k))), wobei (k) die Anzahl der Stellen in den Zahlen ist.
  • Average Case: (O(d(n+k)))
  • Worst Case: (O(d(n+k)))
• Radix Sort ist stabil, wenn der verwendete stabile Sortieralgorithmus (wie Counting Sort) für jede Stelle stabil ist.

Question 5

Heapsort

Answer 5

• In Place
• Best Case: (O(n log n))
• Average Case: (O(n log n))
• Worst Case: (O(n log n))
• nicht stabil

Question 6

Quicksort

Answer 6

• Out of Place
• Best Case: (O(n log n))
• Average Case: (O(n log n))
• Worst Case: (O(n^2))
• Nicht Stabil

Question 7

Counting Sort

Answer 7

• Out of Place
• Best Case: (O(n + k)), wobei (k) der Bereich der Eingabewerte ist.
• Average Case: (O(n + k))
• Worst Case: (O(n + k))
• Stabil