Quicksort
-
Hallo,
in meiner sortiere funktion scheint noch irgendwo ein Fehler drin zu sein. Ich find den grad net
int sortiere(int* arr, int left , int pivot) { int right = pivot; while(left<right) { while(arr[++left] < arr[pivot] && left < right ); while(arr[--right] > arr[pivot] && right > left ); swap(arr[left],arr[right]); } swap(arr[left],arr[pivot]); pivot = left; return pivot; } void quicksort(int* arr, int left , int right) { if(left<right) { int pivot = sortiere(arr,left,right); quicksort(arr,left,pivot-1); quicksort(arr,pivot+1,right); } }
-
So ist er richtig(pseudo Code wikipedia).
int sortiere(int* arr, int left , int right) { int i = left; int j = right-1; int pivot = arr[right]; do { while(arr[i] <= pivot && i < right ) i++; while(arr[j] >= pivot && j > left ) j--; if(i<j) swap(arr[i],arr[j]); } while(i<j); if(arr[i] > pivot) swap(arr[i],arr[right]); return i; } void quicksort(int* arr, int left , int right) { if(left<right) { int pivot = sortiere(arr,left,right); quicksort(arr,left,pivot-1); quicksort(arr,pivot+1,right); } }
-
Nein ist nicht der Code von Wikipedia.
while(arr[j] >= pivot && j > left ) j++;
Die Schleife ist falsch.
=>
while(arr[j] >= pivot && j > left ) j--;
-
jo danke. Habs oben schon korrigiert
-
Es wird ja eine do while schleife benutzt. Ist das nicht unsinnig ? Kann mir einer ein Beispiel nennen wo es einen Unterschied macht.
-
blurry333 schrieb:
Es wird ja eine do while schleife benutzt. Ist das nicht unsinnig ? Kann mir einer ein Beispiel nennen wo es einen Unterschied macht.
google "kopfgesteuert"