Java Sortieren durch Einfügen / InsertionSort

[Vulpecula]

Hallo zusammen!

Ich beschäftige mich gerade mit dem Algorithmus für das Sortieren durch Einfügen. Die Funktionsweise ist mir klar und das umsetzten in Java-Code ist auch kein Problem, nur bin ich jetzt in der Literatur über etwas gestolpert, das ich mir (noch) nicht erklären kann.

Und zwar wird hier von einer "Verbesserung" gesprochen, die dadurch erreicht wird, dass man vor dem eigentlichen Sortiervorgang das kleinste Element an den Anfang der Liste bzw. des Arrays setzt.

Folgende Angaben gab es zu dem unten stehenden Listing:

1. kleinstes Element wandert nach vorne, dient dann als Markierungsschlüssel
2. innere Schleife hat nur noch eine Zuweisung, keine Austauschoperation
3. innere Schleife terminiert, wenn das Element an seiner Position ist

static void insertion(ITEM[] a, int l, int r) {
	int i;
	for (i = r; i > l; i--) compExch(a, i-1, i);
	for (i = l+2; i <= r; i++) {
		int j = i; ITEM v = a[i];
		while (less(v, a[j-1])) {
			a[j] = a[j-1]; j--;
		}
		a[j] = v;
	}
}

Kann mir jemand erklären, WARUM das ganze schneller sein soll? Immerhin wird doch auch beim "normalen" InsertionSort geprüft, ob das Vorgänger-Element kleiner ist oder nicht und die innere Schleife terminiert, sobald dies der Fall ist.



MfG - Vulpecula

P.S.: So habe ich das vor einiger Zeit mal umgesetzt:

Spoiler

	private static int[] InsertionSort(int[] inputArray)
	{
		for (int i = 1; i < arrayGroesse; i++) 
		{
			int k = inputArray[i];
			int j = i - 1;
			
			while ((j > -1) && (inputArray[j] > k))
			{
				inputArray[j+1] = inputArray[j];
				j = j - 1;
			}
			inputArray[j+1] = k;
		}
		sortiertesArrayIS = inputArray.clone();		
		return sortiertesArrayIS;
	}

Ergänzung (28. Dezember 2013)

Ich glaube ich habe den Fehler gefunden. Vorne im Buch dümpelte noch ein Listing herum, in dem InsertionSort wiefolgt gelöst war und auf das sich die "verbesserte Methode" bezieht:

static void sort(double[] a, int l, int r) {
	for (int i = l+1; i <= r; i++)
		for (int j = i; j > l; j--)
			compExch(a, j-1, j);
}

Sie Schreiben zwar, dass es InsertionSort sein soll, aber meiner Meinung nach ist das kein richtiges Sortieren durch Einfügen.

Im Prinzip hatte ich das in meiner Methode schon so umgesetzt. Lediglich das mit dem den Nachvornholen des kleinsten Elements macht mich stutzig...

 

[Groovtama]

Der Trick ist du scanst ja von hinten nach vorne wenn das zu sortierende Element eh kleiner ist als das was bisher kam, kann man es auch gleich nach vorne schieben und spart sich die unnötigen überprüfungen ob v < a[j-1] und hat dadurch nur die überprüfung v < a[l] und das verschieben.

 

[Vulpecula]

Aber soweit ich das sehe, wird hier doch gar nicht überprüft, ob das Element kleiner ist, als alles was bisher da war, oder entgeht mir was? Natürlich prüft er in der while-Schleife auf größer/kleiner und verschiebt ggf, aber es wird ja (je Iteration) AUSSCHLIESSLICH immer nur das nächste Element (j-1) überprüft und nicht alle anderen.

 

[Groovtama]

Keine Ahnung sehe nur eine schleife von vorne nach hinten und eine von hinten nach vorne was dadrin gemacht wird woher soll man das wissen ob da auf das kleinste Element getestet wird^^

Wie gesagt ist nur ne Überprüfung ob das neue element kleiner ist als alles andere davor und dann schiebst es gleich nach vorne und sparst den weg von hinten nach vorne.

 

[Vulpecula]

Naja, die Frage nach dem, was passiert ist gar nicht so das Problem. Deren erste Version ist sowas wie BubbleSort in schnell, da ständig getauscht wird. Die zweite Version unterscheidet sich dadurch, dass nicht am laufenden Band getauscht wird, sondern es wird erst das aktuelle Element (v) in eine temporäre Variable geschoben, dann wird die Position ausgemacht und zuallerletzt (bzw. noch während die Position gesucht wird) wird alles rechts von der neuen Position im Array um einen nach rechts verschoben, damit das Element Platz hat. Man spart im Zweifel also viele überflüssige Tauschoperationen ein, nicht jedoch die Vergleiche.

Trotzdem: Was bleibt ist die Frage, warum zum Teufel hat der Author das kleinste Element des gesamten Arrays nach vorne geholt, bevor die eigentliche Sortierarbeit überhaupt anfängt?
(for (i = r; i > l; i--) compExch(a, i-1, i);)
Immerhin würde sein eigentlicher Algorithmus das kleinste Element doch sowieso nach vorne sortieren...

 

[Groovtama]

Du verstehst das falsch das kleinste Element ist nicht das des gesamten Arrays sondern das was vom bisher sortiertem Teil am kleinsten ist. Wenn du etwas kleineres findest als das kleinste Element was bisher sortiert wurde kannst es nach vorne vor dem sortierten teil nehmen und den rest weiter schieben. Das was kleiner als das bisher kleinste ist ist auch kleiner als das was dahinter ist.
Wenn du etwas hast was größer als das kleinste ist suchst den Platz wohin es gehört und schiebst den Rest eins weiter.

Insertsort mit Trick in pseudo Code ohne grenzen siehst so aus

Procedure insertionSort(a:Array[1...n] of Elements)
for i = 1 to n do                 //Durcklauf für das Array
  e = a[i]                            //zu prüfendes Element
  if e < a[1] then                //Überprüfung ob neues Element kleiner als bisher kleinstes Element das am Anfang steht
      for j = i downto 2 do    //Wenn Ja 
        a[j] = a[j -1]               // Alles bis zum Element hin Verschieben
        a[1] = e                      //Element an den Anfang
  else 
      for j = i downto 2         //Wenn Nein Überürfung aller Elemente bis zum Ersten
        while a[j - 1] > e do   //Wiederholt Überprüfung ob Element an vorherigen Position im Array größer ist als das zu prüfende Element
           a[j] = a[j - 1]           //Element im Array nach hinten Verschieben Wenn Ja
           a[j] = e                   //zu prüfendes Element nach vorne schieben

 

[Vulpecula]

Folgende Zeile finden wir in dem fraglichen Programm:
for (i = r; i > l; i--) compExch(a, i-1, i);

Syntaktisch ist das zwar nicht falsch, aber schlecht zu lesen. Leichter wird es, wenn man den ausdruck etwas entzerrt:

for (i = r; i > l; i--)
{
	compExch(a, i-1, i);
}

a ist das Array, r ist der die letzte Feld im Array (ganz rechts) und l demendsprechend das erste Feld (ganz links). compExch macht hier nichts anderes als Compare (Vergleichen) und Exchange (Tauschen), sofern der Vorgänger i-1 größer ist als der aktuelle Index i, also die stinknormale Tauschroutine. Diese for-Schleife spült mir das kleinste Element im Array nach ganz links an die erste Stelle. Kleine Anmerkung für den Fall, dass das nicht klar sein sollte: Der Ausdruck an sich ist abgeschlossen und hat keinen Einfluss mehr auf die nachfolgende Schleife.

Das kuriose daran ist ja, dass es für den eigentlich Algorithmus überhaupt keine Rolle spielt, ob das man das kleinste Element des gesamten Arrays ganz nach vorne holt oder nicht. Lediglich eine kleine Veränderung an der Äußeren schleife wäre nötig. und man hätte sich die Zeile sparen können.

Also: Ich verstehe was Du mir sagen willst, daran liegt es nicht. Aber so wie Dein Algorithmus ist es halt gerade nicht umgesetzt worden.

Ergänzung (29. Dezember 2013)

Ach herrjemine... Eine Seite weiter folgt dann auch die Begründung, warum der Author das so gelöst hat. Mehr oder weniger jedenfalls, denn er schreibt nicht explizit etwas dazu, sondern nur, dass die Überprüfung, ob der Anfang des Arrays erreich wurde, dadurch überflüssig wird. Immerhin ist das kleinste Element ja schon ganz vorne und die innere Schleife terminiert sobald der Vorgänger nicht mehr kleiner ist.

Jetzt stellt sich mir die Frage: Ist der Wegfall dieser Überprüfung wirklich so ein derartiger Performance-Gewinn?

Okay, bei sehr (!) großen Arrays, Listen, etc. kann ich mir durchaus vorstellen, dass eine Überprüfung weniger von Vorteil sein KANN (da die innere Schleife i.d.R. sehr häufig ausgeführt werden wird), aber in der Praxis wird man für große Datenbestände doch eher ein anderes Verfahren anwenden wollen...


Fazit: Didaktisch ist das Buch der letzte Mist - zum Glück hab ich es nur geliehen und nicht gekauft.

 

[misu]

Die Überprüfung, ob der Anfang des Arrays erreicht wurde, ändert zumindest nicht an der Worst-Case-Komplexität, die ist und bleibt O(n^2), was relativ schlecht ist. Bin nicht sicher, ob du das Buch korrekt wiedergibst, das ist schon eine ungewöhnliche Begründung. Im Zweifelsfall zitiere mal die 2 wichtigsten Sätze aus dem Buch.

Basierend auf deinem ersten Post würde ich ja sagen, dass du noch etwas grundlegendes nicht ganz verstanden hast. Das was du im ersten Post als "verbesserte" Methode bezeichnest, ist der klassische Insertionsort-Algorithmus (siehe z.B. wikipedia). Der klassische Insertionsort zieht aber gerade das kleinste Element nicht nach vorne. Also welche Methode ist jetzt deiner Meinung nach die verbesserte Methode, die klassische oder die mit vorziehen?

Vllt hilft die diese Anmerkung: Die linke Seite von deinem aktuellen Element ist immer bereits sortiert! D.h. von den bisher betrachteten Elementen ist das kleinste Element bereits ganz links.

 

[maxwell-cs]

insertionsort ist übrigens in der praxis für kleine inputs extrem performant und wird oft bei schnellen divide & conquer - algorithmen verwendet, um die niedrigsten level zu sortieren, statt die eingabe bis in einelementige mengen aufzuteilen.

daher ist eine constant-factor-optimierung durchaus von nutzen.