Best&Worst Case bei Insertionsort

[Ameise03]

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

 

[mihe7]

Zunächst einmal muss eine Ordnung definiert sein, damit wir überhaupt von einem "kleineren" und einem "gößeren" Element sprechen können. Dann ist die Frage, ob die Elemente auf- oder absteigend sortiert werden sollen und ob die Sortierung vom Anfang oder Ende der Liste her durchgeführt wird. Bevor man diese Faktoren nicht kennt, kann man da gar nix sagen.

Hat man eine Liste, die aufsteigend sortiert werden soll und wird die sortierte Liste vom Anfang der Liste her aufgebaut, dann hast Du recht. Liegen die Elemente in absteigender Reihenfolge vor, dann jedes einzufügende Element kleiner als das kleinste Element der bisher sortierten Liste, so dass immer alle Elemente der sortierten Liste verschoben werden müssten.

Nachtrag: weil hier von "Liste" die Rede ist, muss man natürlich noch berücksichtigen, welche Art von Liste es ist. Die Ausführungen gelten nur für Arrays (bzw. array-artige Listen). Bei verketteten Listen hast Du ggf. gar kein Problem, vorne etwas anzufügen und könntest auch von vorne her vergleichen.

 

[Ameise03]

Zunächst einmal muss eine Ordnung definiert sein, damit wir überhaupt von einem "kleineren" und einem "gößeren" Element sprechen können. Dann ist die Frage, ob die Elemente auf- oder absteigend sortiert werden sollen und ob die Sortierung vom Anfang oder Ende der Liste her durchgeführt wird. Bevor man diese Faktoren nicht kennt, kann man da gar nix sagen.

Hat man eine Liste, die aufsteigend sortiert werden soll und wird die sortierte Liste vom Anfang der Liste her aufgebaut, dann hast Du recht. Liegen die Elemente in absteigender Reihenfolge vor, dann jedes einzufügende Element kleiner als das kleinste Element der bisher sortierten Liste, so dass immer alle Elemente der sortierten Liste verschoben werden müssten.

Nachtrag: weil hier von "Liste" die Rede ist, muss man natürlich noch berücksichtigen, welche Art von Liste es ist. Die Ausführungen gelten nur für Arrays (bzw. array-artige Listen). Bei verketteten Listen hast Du ggf. gar kein Problem, vorne etwas anzufügen und könntest auch von vorne her vergleichen.

Hallo,

ja, das hab ich vergessen ausführlich zu erwähnen. Dann mache ich das eben.

Die Aufgabe bezog sich auf generelle Listen, die Elemente beinhalten (in unserem Falle Zahlen), welche von klein nach groß geordnet werden sollen. Ich glaube sie waren Array artige Listen. Eine Reihe mit mehreren Schachteln, wo zahlen drin waren.

Man betrachtet bei Insertionsort zwei Mengen. Eine sortierte und eine unsortierte Menge. Man nimmt ja immer von vorne die Elemente aus der unsortierten Liste und fügt sie in eine sortierte Liste ein. Also zwei Listen. Eine leer erzeugte, in die dann die sortierten Elemente eingefügt werden aus der unsortierten heraus.

Was wäre denn bei sowas der worst Case? Mein Lehrer meint, wenn sie bereits fertig sortiert ist von klein nach Groß.

 

[mihe7]

Beispiel: 12345678

Die sortierte Liste beginnt z. B. mit der 8 (wir bauen hier einaml von hinten nach vorne auf) und schauen uns jetzt die 7 an. Es ist 7 < 8, also ist die 7 schon an der richtigen Position -> Thema erledigt. Genauso verhält es sich bei der 6, 5, 4, 3, 2 und 1.

Wenn man von vorne her aufbaut, beginnt man mit der 1 und schaut sich die 2 an. Es ist 2 > 1, also ist die 2 schon an der richtigen Position -> Thema erledigt. Genauso verhält es sich bei der 3, 4, 5, 6, 7 und 8.

Drehen wir die Liste einmal um: 87654321 und bauen von vorne nach hinten auf.

7 < 8 also muss 8 mit 7 vertauscht werden. Weitere Elemente gibt es nicht. 1 Element verschoben. Die sortierte Liste ist jetzt 78, die unsortierte 654321.
6 < 8 also muss 8 mit 6 vertauscht werden. Weiter ist 6 < 7, also muss 7 mit 6 vertauscht werden. 2 Elemente verschoben. Die sortierte Liste ist jetzt 678, die unsortierte 54321.
usw.

Genauso wäre es, wenn man von hinten nach vorne aufbaut:

2 > 1, also muss 1 mit 2 veratuscht werden. Weitere Elemente gibt es nicht. Die sortierte Liste jetzt 12, die unsortierte 876543.
3 > 1, also muss 1 mit 3 veratuscht werden. Weiter ist 3 > 2, also muss 2 mit 3 vertauscht werden. Die sortierte Liste ist jetzt 123, die unsortierte 87654.
usw.

 

[Ameise03]

Beispiel: 12345678

Die sortierte Liste beginnt z. B. mit der 8 (wir bauen hier einaml von hinten nach vorne auf) und schauen uns jetzt die 7 an. Es ist 7 < 8, also ist die 7 schon an der richtigen Position -> Thema erledigt. Genauso verhält es sich bei der 6, 5, 4, 3, 2 und 1.

Wenn man von vorne her aufbaut, beginnt man mit der 1 und schaut sich die 2 an. Es ist 2 > 1, also ist die 2 schon an der richtigen Position -> Thema erledigt. Genauso verhält es sich bei der 3, 4, 5, 6, 7 und 8.

Drehen wir die Liste einmal um: 87654321 und bauen von vorne nach hinten auf.

7 < 8 also muss 8 mit 7 vertauscht werden. Weitere Elemente gibt es nicht. 1 Element verschoben. Die sortierte Liste ist jetzt 78, die unsortierte 654321.
6 < 8 also muss 8 mit 6 vertauscht werden. Weiter ist 6 < 7, also muss 7 mit 6 vertauscht werden. 2 Elemente verschoben. Die sortierte Liste ist jetzt 678, die unsortierte 54321.
usw.

Genauso wäre es, wenn man von hinten nach vorne aufbaut:

2 > 1, also muss 1 mit 2 veratuscht werden. Weitere Elemente gibt es nicht. Die sortierte Liste jetzt 12, die unsortierte 876543.
3 > 1, also muss 1 mit 3 veratuscht werden. Weiter ist 3 > 2, also muss 2 mit 3 vertauscht werden. Die sortierte Liste ist jetzt 123, die unsortierte 87654.
usw.

Und welcher Fall war das nun? Worst oder best? Wie das Verfahren geht weiß ich ja. Aber die Streitfrage in der schule ist ja, ob eine unsortierte Liste, die von Groß nach klein fertig sortiert ist, aber in eine von klein nach Groß sortierte Liste umsortiert werden soll, dem best oder worst Case Fall entspricht. Ich meine es ist der worst Case.

 

[mihe7]

Und welcher Fall war das nun? Worst oder best? Wie das Verfahren geht weiß ich ja. Aber die Streitfrage in der schule ist ja, ob eine unsortierte Liste, die von Groß nach klein fertig sortiert ist, aber in eine von klein nach Groß sortierte Liste umsortiert werden soll, dem best oder worst Case Fall entspricht. Ich meine es ist der worst Case.

Wenn die Liste bereits in der richtigen Reihenfolge vorliegt, ist das der best case, weil nichts verschoben werden muss.

 

[Ameise03]

Wenn die Liste bereits in der richtigen Reihenfolge vorliegt, ist das der best case, weil nichts verschoben werden muss.

Und wieso sagt mein Informatik Lehrer, dass die Liste in insertionsort für den best Case eine umgedreht sortierte Liste haben muss? Blicke es nicht.

Eine umgedrehte Liste ist doch der qorst Case, wenn man sie in der anderrn Reihenfolge haben will.

 

[KonradN]

Und wieso sagt mein Informatik Lehrer, dass die Liste in insertionsort für den best Case eine umgedreht sortierte Liste haben muss? Blicke es nicht.

Das ist, was @mihe7 mit dem Nachtrag oben etwas ewähnte.

Nachtrag: weil hier von "Liste" die Rede ist, muss man natürlich noch berücksichtigen, welche Art von Liste es ist.

Wir kennen die von euch verwendete Liste nicht. Wenn ihr eine einfache Linked List habt, dann ist die umgedrehte Sortierung der best case, denn Du kannst am Anfang einfügen:

Nehmen wir die elemente 4 3 2 1:

kopf -> null

4 einfügen:
kopf -> 4 -> null

3 einfügen, das erste Element ist direkt größer, also:
kopf -> 3 -> 4 -> null
So geht es weiter bis hin zu
kopf -> 1 -> 2 -> 3 -> 4 -> null

Wenn das also eure List bisher war, dann hat der Lehrer für genau diese List Recht.

 

[Ameise03]

Das ist, was @mihe7 mit dem Nachtrag oben etwas ewähnte.


Wir kennen die von euch verwendete Liste nicht. Wenn ihr eine einfache Linked List habt, dann ist die umgedrehte Sortierung der best case, denn Du kannst am Anfang einfügen:

Nehmen wir die elemente 4 3 2 1:

kopf -> null

4 einfügen:
kopf -> 4 -> null

3 einfügen, das erste Element ist direkt größer, also:
kopf -> 3 -> 4 -> null
So geht es weiter bis hin zu
kopf -> 1 -> 2 -> 3 -> 4 -> null

Wenn das also eure List bisher war, dann hat der Lehrer für genau diese List Recht.

Jap, das ist die Liste. Danke dir für die Ausführung! 🙂

 

[mihe7]

Und wieso sagt mein Informatik Lehrer, dass die Liste in insertionsort für den best Case eine umgedreht sortierte Liste haben muss? Blicke es nicht.

Das musst Du ihn fragen, nicht mich 🙂

 

[osion]

Beim Einordnen eines neuen Elements hängt es davon ab, ob der sortierte Bereich von vorne nach hinten oder von hinten nach vorne abgearbeitet wird. Während unserer Prüfung hat der Dozent manche Algorithmen umdefiniert, indem er sich fragte, "Was wäre, wenn...".

Frage doch am besten deine Mitstudenten, welche auch die Prüfung geschrieben haben.