Laufzeit

Question 1

Insertion Sort

Answer 1

###

• Out of Place: nein, nicht viel mehr Speicher
• Laufzeit:
  
  • Best Case: (O(n))
  • Average Case: (O(n^2))
  • Worst Case: (O(n^2))
• Stabilität: Insertion Sort ist stabil, da Elemente der Ausgangssequenz im neuen Array in der korrekten relativen Reihenfolge stehen.

Question 2

Merge Sort

Answer 2

• Out of Place: Ja, Merge Sort benötigt zusätzlichen Speicher für temporäre Arrays.
• Laufzeit:
  
  • Best Case: (O(n log n))
  • Average Case: (O(n log n))
  • Worst Case: (O(n log n))
• Stabilität: Merge Sort ist stabil, da Elemente mit gleichem Wert während des Mergings in ihrer relativen Reihenfolge beibehalten werden.

Question 3

Bucket Sort

Answer 3

• Out of Place: Ja, es werden mehrere temporäre Buckets (Listen) verwendet.
• Laufzeit:
  
  • Best Case: (O(n))
  • Average Case: (O(n))
  • Worst Case: (O(n^2)), wenn alle Elemente in einen einzigen Bucket fallen.
• Stabilität: Bucket Sort kann stabil sein, wenn die inneren Sortiervorgänge (wie Insertion Sort) stabil sind.

Question 4

Radix Sort

Answer 4

• Out of Place: Ja, Radix Sort verwendet temporäre Arrays oder Buckets für jede Stelle (Digit).
• Laufzeit:
  
  • 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)))
• Stabilität: Radix Sort ist stabil, wenn der verwendete stabile Sortieralgorithmus (wie Counting Sort) für jede Stelle stabil ist.

Question 5

Heapsort

Answer 5

• Out of Place: Nein, Heapsort ist ein in-place Sortieralgorithmus.
• Laufzeit:
  
  • Best Case: (O(n log n))
  • Average Case: (O(n log n))
  • Worst Case: (O(n log n))
• Stabilität: Heapsort ist nicht stabil, da die Heapshiftdown-Operationen die relative Reihenfolge der Elemente mit gleichem Wert ändern können.

Question 6

Quicksort

Answer 6

• Out of Place: Nein, Quicksort ist ein in-place Sortieralgorithmus, kann aber zusätzlichen Speicher für Rekursion benötigen.
• Laufzeit:
  
  • Best Case: (O(n log n))
  • Average Case: (O(n log n))
  • Worst Case: (O(n^2)) (wenn das Pivotelement ungünstig gewählt wird)
• Stabilität: Quicksort ist nicht stabil, da das Vertauschen von Elementen die relative Reihenfolge ändern kann.

Question 7

Counting Sort

Answer 7

• Out of Place: Ja, Counting Sort verwendet ein zusätzliches Array zur Zählung und Speicherung der sortierten Elemente.
• Laufzeit:
  
  • Best Case: (O(n + k)), wobei (k) der Bereich der Eingabewerte ist.
  • Average Case: (O(n + k))
  • Worst Case: (O(n + k))
• Stabilität: Counting Sort ist stabil, da Elemente mit gleichem Wert in ihrer relativen Reihenfolge gezählt und sortiert werden.