Time and Space Complexity

Zeitkomplexität:

• Best Case: O(n)
  • Wenn das Array bereits sortiert ist, führt Insertion Sort nur einen Durchlauf aus, um die sortierte Reihenfolge zu bestätigen.
• Average und Worst Case: O(n²)
  • Im Durchschnitt und im schlechtesten Fall benötigt der Algorithmus quadratische Zeit, da für jedes Element Vergleiche und Verschiebungen durch den gesamten sortierten Teil erforderlich sein können.

Platzkomplexität:

• O(1)
  • Insertion Sort ist ein „In-place“-Algorithmus, was bedeutet, dass er keinen zusätzlichen Speicher proportional zur Eingabegröße benötigt.
  • Der für die Sortierung verwendete Speicherplatz bleibt unabhängig von der Eingabegröße konstant.

Zusammenfassung:

• Insertion Sort ist effizient für kleine Datensätze oder nahezu sortierte Arrays.
• Aufgrund seiner quadratischen Zeitkomplexität ist er für große Datensätze weniger geeignet.
• Die Platzkomplexität ist konstant, was ihn für jede Eingabegröße speichereffizient macht.