V
'#' - the real schrieb:
@volkard
Ignorier diesen Deppen da der direkt unter dir gepostet hat.
hab ihn gelöscht.
Warum? Ich hab gehört das es eine Rekursionstiefe gibt welche bei zu hoher Rekursionsausführung abbricht.
das ist der fall. dein stack hat vermutlich nur 1M. wenn quicksort pech hat und in den worst case geht, würde das rumms machen, wenn das feld ein wenig größer ist. aber wenn quicksort glück hat und die feldgröße bei jedem weiteren rekursionslevel halbiert wird, kannste mit 30 levels gleich 2^30 datensätze sortieren.
Auch das die daten direkt im cach landen und wenn dieser zu klein ist das es dann rummms macht.
wenn der chache zu klein ist, wirds langsamer. aber das ist eher nicht so relevant.
alles, was wir brauchen, ist glück, daß wir mit jedem teiferen level die arraygröße halbieren. da gibts sogar einen trick, daß die arraygröße sich mindestens halbiert.
dein code:
void Quicksort(DWORD dwLow, DWORD dwHigh) {
:anfang
//ganz viel weggelassen
//Und die Funktion für die Teile rechts und links des Partition Elements aufgerufen
QuickSort(dwLow, iTop - 1, Compare);
QuickSort(iTop + 1, dwHigh, Compare);
}
}
}
mein code:
void Quicksort(DWORD dwLow, DWORD dwHigh) {
:anfang
//ganz viel weggelassen
//Und die Funktion für die Teile rechts und links des Partition Elements aufgerufen
QuickSort(dwLow, iTop - 1, Compare);
dwLow=iTop+1;
dwHigh=dwHigh;
goto anfang;
}
}
}
also ein unteraufruf wird rekursiv gemacht und einer wird zu nem schleifensprung umgemodelt.
schleifen kann der computer ja ohne schmerzen viele ausführen.
außerdem hat keiner gesagt, welchen der beiden unteraufrufe du zuerst abarbeiten mußt. mach es so: arbeite zuerst rekursiv das kleinere unterfeld ab und dann per schleife das größere. das garantiert, daß du bei jeder neuen rekursionstiefe die feldgröße mindestens halbiert hat. hast also bei 1 milliarde datensätzen eine rekursionstiefe von höchstens 30. bist auf der sicheren seite damit.
