✔ QuickSort sortiert nicht richtig

[manerr]

Hallo

Ich habe mir eine Quicksort-Funktion programmiert, doch leider sortiert die nicht ganz korrekt. Ab und zu ist mal eine Zahl an der falschen Stelle:

8712024
8712011
8712012
8712013
8712014
8712015
8712016
8712021
8712022
8712023
8712025
8712026
8712031
8712032
8712034
8712035
8712036
8712041
8712042
8712043
8712044
8712045
8712046
8712051
8712052
8712053
8712054
8712055
8712056
8712061
8712062
8712063
8712064
8712065
8712066
8712071
8712072
8712073
8712074
8712075
8712075
8712076
8712081
8712082
8712242
8712083
8712084
8712085
8712086
8712091
8712092
8712093

Die erste Zahl sollte da nicht stehen und am Ende ist auch noch eine falsche drin. Die zahlen stellen ein Datum dar 8712045 ist z.b. 04.12.1987, die 5 ist eine Messnummer. Insgesamt hat mein Array 543 Einträge welche noch bis in den Februar 88 reichen.

So und nun mein Quellcode:
<neuerer Code weiter unten>
die Variablen li und re sind zu beginn jeweils auf 0 und auf 542.

Würde mich freuen, wenn mir einer ein Tipp hat, wo hier der Fehler liegt.

Vielen Dank
Manuel

 

[zeja]

Ich würde empfehlen das nach folgenden Pseudocode zu programmieren: http://de.wikipedia.org/wiki/Quicksort

Da siehst du schon, dass bei dir ire falsch initialisiert ist. Es sollte ire = re - 1 heißen.

Das Pivotelement in einer Variablen abzulegen ist vor allem sinnvoll, da es die Arrayzugriffe beträchtlich reduziert und der Algorithmus somit schneller läuft.

 

[manerr]

Danke zeja

Habe mir auch den Pseudocode bei Wikipedia angeschaut aber dieses kleine, aber feine Detail voll übersehen.

Das mit dem pivot ist auch ne gute Idee, werde ich gleich so abändern, den daran hab ich noch gar nicht gedacht.

manuel

 

[manerr]

Ich habe es so abgeändert, aber irgendwie funktioniert es noch nicht ganz.

So sollte das ganze nachher aussehen: http://altherr.it/liste_soll.txt (hier war nur der Bubblesort am Werk, der Rest ist alles gleich)
So sieht es aber aus: http://altherr.it/liste_ist.txt

vielen dank

 

[zeja]

Dann poste doch nochmal deinen Code.

Wie gesagt, wenn man den Pseudocode genauso in Java übersetzt dann funktioniert es auch korrekt.

 

[manerr]

Bei Wikipedia wird auch auf Beispielcodes verlinkt, die funktionieren aber auch nicht.

public static void dm004quick(int li, int re) {
		int m = (li + re) / 2;
		int ili = li;
		int ire = re - 1;
		int pivot = tempListe.get(m).getDatum();
		while (ili < ire) {
			while(tempListe.get(ili).getDatum() < pivot) {
				ili++;
			}
			while(tempListe.get(ire).getDatum() > pivot) {
				ire--;
			}
			
			Temperatur temp = tempListe.get(ili);
			tempListe.set(ili, tempListe.get(ire));
			tempListe.set(ire, temp);
			
			if (m == ili) {
				m = ire;
			} else if (m == ire) {
				m = ili;
			}
			ili++;
			ire--;
		}
		if (li < m-1) {
			dm004quick(li, m-1);
		}
		if (re > m+1) {
			dm004quick(m+1, re);
		}
	}

 

[manerr]

Jetzt funktioniert es, hier der Code:

	public static void dm004quickTest(int li, int re) {
		int m = (li + re) / 2;
		int ili = li;
		int ire = re;
		int pivot = tempListe.get(m).getDatum();
		do {
			while(tempListe.get(ili).getDatum() < pivot) {
				ili++;
			}
			while(tempListe.get(ire).getDatum() > pivot) {
				ire--;
			}
			
			if (ili < ire) {
				Temperatur temp = tempListe.get(ili);
				tempListe.set(ili, tempListe.get(ire));
				tempListe.set(ire, temp);
				ili++;
				ire--;			
			} else if (ili == ire) {
				ili++;
				ire--;
			}
		} while (ili <= ire);
		
		if (li < ire) {
			dm004quickTest(li, ire);
		}
		if (ili < re) {
			dm004quickTest(ili, re);
		}
	}