Quicksort < Softwaretechnik+Pro < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Bauen sie den gegebenen Quicksort-Algorithmus zu einem randomisierten Quicksort-Alogrithmus der auf gleichverteilten randomisierten Pivotelement basiert. |
Hi Leute!
Ich hab hier einem Quicksort-Algorithmus, den ich nun zum gefragten randomisierten Quicksort-Alogrithmus umbauen muss. Hier der Code:
| 1: |
| | 2: | void swap(int &a, int &b)
| | 3: | {
| | 4: | int h = b;
| | 5: | b = a;
| | 6: | a = h;
| | 7: | }
| | 8: |
| | 9: |
| | 10: |
| | 11: | void PreparePartition(int a[], int f, int l, int &p)
| | 12: | {
| | 13: | //Pivot-Element
| | 14: | //f = f + rand() % (l-f+1);
| | 15: | //int f = rand() % 9;
| | 16: | int pivot = a[f];
| | 17: | //int pivot = a[f];
| | 18: | p = f-1;
| | 19: |
| | 20: | for(int i = f; i <= l; i++)
| | 21: | {
| | 22: | if(a[i] <= pivot)
| | 23: | {
| | 24: | p++;
| | 25: | swap(a[i], a[p]);
| | 26: | }
| | 27: | }
| | 28: |
| | 29: | //Pivot an die richtige Stelle
| | 30: | swap(a[f], a[p]);
| | 31: | }
| | 32: |
| | 33: |
| | 34: |
| | 35: | void Quicksort(int a[], int f, int l)
| | 36: | {
| | 37: | int part;
| | 38: |
| | 39: | if(f < l)
| | 40: | {
| | 41: | PreparePartition(a,f,l,part);
| | 42: | Quicksort(a,f,part-1);
| | 43: | Quicksort(a,part+1,l);
| | 44: | }
| | 45: | }
|
In der Funktion PreparePartition seht ihr ganz am Anfang zwei auskommentierte Codefragmente, die ich ausprobiert habe. Leider funktioniert der Sortier-Algo dann nur noch sporadisch. Ist es also noch nicht ganz richtig.
Des Weiteren hab ich versucht, die Funktion Quicksort aus der main schon an der Stelle f mit randomisierten Zufallszahlen aufzurufen; leider auch ohne Erfolg...
Ich hoffe, jemand von euch kann mir helfen! Das wäre sehr nett!
Danke!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:20 Sa 20.04.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
