Best&Worst Case bei Insertionsort

Ameise03

Mitglied
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

Top Contributor
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

Mitglied
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

Top Contributor
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

Mitglied
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

Top Contributor
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

Mitglied
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

Super-Moderator
Mitarbeiter
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

Mitglied
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! :)
 

osion

Bekanntes Mitglied
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
T Best Practice überprüfen von Übergabeparametern Allgemeine Java-Themen 17
S Best Practices CopyConstrutor mit ArrayList Allgemeine Java-Themen 1
S best practice: Einordnung Enitity und Datenklasse Allgemeine Java-Themen 11
temi best practice: Parameter überprüfen, wo? Allgemeine Java-Themen 9
Airwolf89 JUnit: Vorschläge/ Best Practice Allgemeine Java-Themen 7
F Error Logging - best practices? Allgemeine Java-Themen 3
M Best Practice: Daten aufnehmen-speichern-bereitstellen Allgemeine Java-Themen 8
H Best Practice zu vielen konstanten Objekten? Allgemeine Java-Themen 10
M Best Practices für Undo/Redo Allgemeine Java-Themen 16
G Best Practices Software-Engineering‏ Allgemeine Java-Themen 3
G Best Practices Allgemeine Java-Themen 10
F best practice Allgemeine Java-Themen 5
J Input/Output Dateien bearbeiten - "Best Practice" Allgemeine Java-Themen 3
M Best Practices Exception Handling für eigene library Allgemeine Java-Themen 8
R Statische Klasse: Best practice mit flags (2) Allgemeine Java-Themen 3
musiKk Best Practice für kleine Variationen in gegebenen Modellklassen Allgemeine Java-Themen 11
S best practise Allgemeine Java-Themen 6
J Best Practice für implementierung von equals(...) Allgemeine Java-Themen 7
Daniel_L Best Practice zum Löschen von Log-Files? Allgemeine Java-Themen 8
S Array: Anzahl Elemente mit best. Wert zählen Allgemeine Java-Themen 4
M Best Match / Best Fit auf Strings Allgemeine Java-Themen 9
T regex case insensitive trimmed Allgemeine Java-Themen 6
ReinerCoder Case statt if else Abfragen?! Allgemeine Java-Themen 8
C Regex (Case insensitive und Umlaute) Allgemeine Java-Themen 4
B RowFilter Case Insensitive Problem Allgemeine Java-Themen 3
L String -> Case insensitiv replacement Allgemeine Java-Themen 5
1 String mit contains vergleichen (ignore case) Allgemeine Java-Themen 2
DStrohma [Erledigt] Regex CASE INSENSITIVE Allgemeine Java-Themen 7
K Sortierung, Collator und Case Allgemeine Java-Themen 5
V Case-sensitiv nur in Jar? Allgemeine Java-Themen 8
MQue Use case Allgemeine Java-Themen 8
E CASE Tools Allgemeine Java-Themen 15
F case Allgemeine Java-Themen 3
0 case orphaned Fehlermeldung! Allgemeine Java-Themen 2
G switch case VS. if.else if Allgemeine Java-Themen 2
M Switch von case zu case weiterleiten Allgemeine Java-Themen 6

Ähnliche Java Themen

Neue Themen


Oben