Introprog 6. Tutorium

Was ist die Worst-Case Laufzeitkomplexität von Insertionsort?

• O(n)
• O(log n)
• O(n^2)
• O(1)

Welcher Sortieralgorithmus vergleicht wiederholt benachbarte Elemente und vertauscht diese, wenn sie in der falschen Reihenfolge sind?

• Insertionsort

• Selectionsort

• Bubblesort

• Countsort

Welche Schlüsseloperation wird in der äußeren Schleife von Insertionsort durchgeführt?

• Ein Element an seine richtige Position einfügen

• Das kleinste oder größte Element auswählen

• Die Elemente aufsummieren

In welchem Fall ist Selectionsort am effizientesten?
Wenn die Eingabe...

• schon richtig sortiert ist

• falschherum sortiert ist

• gar nicht sortiert ist

• alle Fälle sind gleich effizient

In welchem Fall ist Insertionsort am effizientesten?
Wenn die Eingabe...

• schon richtig sortiert ist

• falschherum sortiert ist

• gar nicht sortiert ist

• alle Fälle sind gleich effizient

Wie kann Bubblesort so optimiert werden, dass der Algorithmus in einigen Fällen vorzeitig beendet wird?

• Durch Erhöhen der Anzahl der Iterationen

• Durch Rekursion

• Indem der Algorithmus abbricht, wenn in einem Durchgang keine Elemente getauscht werden

• Indem die Anzahl der Durchläufe auf die Quadratwurzel der Arraygröße reduziert wird

Wieso ist Stabilität von Sortierverfahren wichtig?

• Dadurch kann in O(n) sortiert werden

• Dadurch wird der Speicherplatzverbrauch von Algorithmen reduziert

• Es ist wichtig für Anwendungen, bei denen die Reihenfolge von Daten mit gleichem Schlüssel relevant ist

• Es ist für keinen praktische Anwendung relevant

Was ist die Speicherplatzkomplexität von Insertionsort?
(wie viel Speicherplatz braucht Insertionsort zusätzlich)

• O(1)

• O(log n)

• O(n)

• O(n²)

Welche asymptotische Laufzeitkomplexität ist effizienter?

• O(1.000 n)

• O(n²)

• beide sind gleich effizient

Welche asymptotische Laufzeitkomplexität ist effizienter?

• O(n log n)

• O(n²)

• beide sind gleich effizient