Quicksort - Abfrage in zwei Unterwhileschleifen, ob links < linksAlt nötig? Beweis?

[Eisflamme]

Hi,

Wir machen gerade Sortis in Java, daher schreib ich den Source kurz Mal so.
Gegeben sei dieser Quicksort:

public void Sort(Type[] array, int left, int right)
	{
		if(left == right)
			return;

		int oldLeft = left, oldRight = right;

		Type	pivot		= array[(left + right) / 2];

		while(left <= right)
		{
			while(left < oldRight && array[left].compareTo(pivot) < 0)
				++left;

			while(right > oldLeft && array[right].compareTo(pivot) > 0)
				--right;

			if(left <= right)
			{
				swap(array, left, right);
				++left;
				--right;
			}
		}

		DoSort(array, oldLeft, left - 1);
		DoSort(array, left, oldRight);
	}

Also ich meine den jeweils ersten Vergleich in den beide inneren Whileschleifen. Braucht man diesen?

Das Problem ist ja grundsätzlich: Wenn nur noch kleinere Elemente als das Pivot-Element gelesen werden können, wird das zu einer Endlosschleife.

Bis zum Pivot-Element gibt es aber keine Probleme, denn hier wird immer gestoppt. Das Problem kann also nur entstehen, wenn wir aber über das Pivot-Element hinausgelaufen sind, gleichzeitig auf der rechten Seite aber nur noch kleinere Elemente sind.
Es können aber rechts nicht nur noch kleinere Elemente sein, wenn wir über das Pivot-Element hinausgelaufen sind, weil wir ja (wegen des Pivot-Elements) schon mindestens einen Tausch gemacht haben, der dazu geführt hat, dass auf der rechten Seite von Pivot ein Element steht.
Folglich würden wir zumindest noch einmal rechts abstoppen. Und der rechte Zeiger müsste damit auch bereits links vom rechten Element stehen, zumindest aber auf der gleichen Position, sodass nach dem Tausch mit sich selbst die Schleife danach zu Ende wär.

Ist das schon Beweis genug oder kann das jemand vielleicht prägnanter formulieren. Oder ist das gar falsch, weil es Fälle gibt, in denen die Abfrage nötig ist? Wiki nutzt diesen Vergleich, zahlreiche andere Codes nicht.

Lg

[Tobiking2]

Eisflamme schrieb:

Bis zum Pivot-Element gibt es aber keine Probleme, denn hier wird immer gestoppt.

Der Code of Wikipedia prüft im Gegensatz zu dir, ob der Arrayinhalt unter left/right kleiner- oder größer-gleich dem pivot ist statt echt kleiner oder größer.

Wenn man dann ein Beispiel wie 213 sortiert, ist die Schleife für left nicht erfüllt, und somit bleibt left=0. Aber die Schleife für right ist erfüllt und geht ohne die Bedingung auch bis right=0. Das würde heißen die Zahlenfolge ist sortiert, was nicht stimmt. Mit der Bedingung bleibt right bei 1 stehen, man tauscht position 0 mit 1 und es passt.