Hallo,
ich habe gestern eine Klassenarbeit in Informatik geschrieben in der folgende Aufgabe drankam:
„Beschreiben Sie, bei welcher vorliegenden Liste mit Elementen der Worst und der Best case bei dem Verfahren Insertionsort vorliegt.“
Insertionsort besitzt im Best Case ja O(n) und im worst Case O(n²). Jetzt dachte ich, dass der worst Case Eintritt, wenn wir eine fertig sortierte Liste haben, die aber in der umgekehrten Reihenfolge geordnet ist, und man sie eigentlich andersherum (von klein nach gross) haben will. Zumindest steht das in sämtlichen Forums bei Personen, die davon Ahnung haben.
Mir wurde heute jedoch gesagt von Klassenkameraden und meinem Lehrer, dass das nicht stimmt. Der worst Case ist wenn die Elemente in der korrekten Reihenfolge schon sortiert ist, da jedes Element einmal komplett die sortierte Liste durchläuft.
Was ist nun richtig?
LG
ich habe gestern eine Klassenarbeit in Informatik geschrieben in der folgende Aufgabe drankam:
„Beschreiben Sie, bei welcher vorliegenden Liste mit Elementen der Worst und der Best case bei dem Verfahren Insertionsort vorliegt.“
Insertionsort besitzt im Best Case ja O(n) und im worst Case O(n²). Jetzt dachte ich, dass der worst Case Eintritt, wenn wir eine fertig sortierte Liste haben, die aber in der umgekehrten Reihenfolge geordnet ist, und man sie eigentlich andersherum (von klein nach gross) haben will. Zumindest steht das in sämtlichen Forums bei Personen, die davon Ahnung haben.
Mir wurde heute jedoch gesagt von Klassenkameraden und meinem Lehrer, dass das nicht stimmt. Der worst Case ist wenn die Elemente in der korrekten Reihenfolge schon sortiert ist, da jedes Element einmal komplett die sortierte Liste durchläuft.
Was ist nun richtig?
LG