Sortieren durch einfügen

[witch doctor]

Kann mir jemand den Algorithmus zu Sortieren durch Einfügen erklären?

Ich wollte es als JAVA Programm schreiben.

Ich habe auch eine fremde Lösung gefunden, aber noch nicht so wirklich verstanden, warum da was gemacht wird:

public static void insertionSort(int feld[])

	{

		for(int i=0;i<feld.length;i++) //Das Feld wird durchlaufen

		{

			int marker=i; 

			int temp=feld[i];


			while(marker>0 && feld[marker-1]>temp)

			{

				feld[marker]=feld[marker-1];

				marker--;

			}	

			feld[marker]=temp; //feld[marker] wird sich gemerkt;

		}

Könnt ihr mir das erklären?

[carfax]

Was sortiert der überhaupt ?...wenn ich den laufen lass, kommt hinten nur Brötchen raus !

BEISPIEL

input:

int[] a = new int[3];

a[0] = 3;

a[1] = 2;

a[2] = 1;

nach Sortierung:

a[0] = 0;

a[1] = 0;

a[2] = 1;

Oder soll das die Sortierung sein ?

MfG

carfax

[witch doctor]

Also bei mir läuft es.

Ich verstehe den Code nur nicht komplett.

Der komplette Code wäre zB so:

import java.io.*;

/**

 * Die nachfolgende Methode führt den InsertionSort 

 * (auch Sortieren durch Einfügen genannt) 

 * aus. 

 * Das Grundprinzip dieser Sortierung besteht darin, den ersten Wert einer Liste 

 * auszuwählen und jeden weiteren an die richtige Stelle (gemäß der Sortierungsanforderung)

 * einzufügen. 

 */


		public class insertionsort

		{



			public static void insertionSort(int feld[])


			{


				for(int i=0;i<feld.length;i++) //Das Feld wird durchlaufen


				{


					int marker=i; // Der Index wird hier zwischengespeichert 

					//System.out.println("marker "+marker);


					int temp=feld[i]; //speichert die Eingaben zwischen

					//System.out.println("temp "+temp);			


					while(marker>0 && feld[marker-1]>temp)

					{

							feld[marker]=feld[marker-1]; //hier wird getauscht

							marker--;

							System.out.println("marker "+marker);		


					}


				feld[marker]=temp; //feld[marker] wird sich gemerkt;


				}

			}


	public static void main(String args[])

	throws IOException

	{

		int n;

		int feld[];



		BufferedReader din = new BufferedReader(new InputStreamReader(System.in));


		System.out.println("Bitte geben Sie die Feldgröße ein:");

		n=Integer.parseInt(din.readLine());

		feld=new int[n];


		for(int i=0;i<n;i++)

		{

			System.out.println("Bitte geben Sie einen Wert ein");

			feld[i]=Integer.parseInt(din.readLine());	

		}


		insertionSort(feld);


		for(int i=0;i<n;i++)

		{

			System.out.println(feld[i]);

		}



	}

}

Er sortiert aufsteigend. Und das macht er auch ganz wunderbar.

Nur zum Beispiel verstehe ich das marker-- in der for-Schleife nicht.

[Klotzkopp]

for(int i=0;i<feld.length;i++)

Die äußere Schleife läuft von vorn nach hinten, d.h. das Feld wird auch von vorn nach hinten sortiert. Insertion Sort bedeutet, dass man das erste Element aus dem unsortierten Bereich an der passenden Stelle im sortierten Bereich einfügt. Das hat zur Folge, dass alle Elemente, die im sortierten Bereich dahinter liegen, um eine Position nach hinten verschoben werden müssen, um dem neu einsortierten Element Platz zu machen:

int marker=i;

Marker ist die "Einfügemarke", die nach der richtigen Einfügeposition sucht. i ist die Position des ersten Elements im unsortierten Bereich. Hier startet der Marker.

int temp=feld;

Das ist der einzusortierende Wert.

while(marker>0 && feld[marker-1]>temp)

Solange der Marker noch nicht am Anfang angekommen ist, und das Element vor dem Marker größer ist als unser einzusortierendes Element... (übrigens, beim ersten Durchlauf der äußeren Schleife wird die innere gar nicht ausgeführt, weil marker == 0)

feld[marker]=feld[marker-1];

... wird das Element vor dem Marker nach hinten verschoben...

marker--;

... und der Marker nach vorn gesetzt. Man könnte diese beiden Schritte auch trennen, d.h. man sucht zuerst nach der richtigen Position und verschiebt dann die größeren Elemente eine Position nach hinten.

feld[marker]=temp;

Nach dem Ende der inneren Schleife sind wir entweder am Anfang des Bereichs angekommen, oder der Marker zeigt auf das Element, das gerade eben noch größer ist als das Einzufügende. Da wir ersteres aber eben noch nach hinten verschoben haben, können wir einfach unseren gespeicherten Wert an der Stelle des Markers einsetzen.

[witch doctor]

Aha, wird schon klarer.

Man könnte diese beiden Schritte auch trennen, d.h. man sucht zuerst nach der richtigen Position und verschiebt dann die größeren Elemente eine Position nach hinten.

Dies wäre sicherlich mit einer binären Suche möglich.

Nur wie mache ich das. Den Algorithmus zur binären Suche habe ich verstanden.

Nur wie baue ich den in Sortieren durch einfügen ein?