Quicksort/Bubblesort < C/C++ < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Aufgabe | Implementieren Sie Algorithmen BubbleSort und Quicksort als C-Funktionen und schreiben Sie ein
Hauptprogramm zum Testen dieser Sortierverfahren anhand von Folgen zufälliger Gleitkommazahlen,
deren Länge der Benutzer festlegen kann (Sie müssen also dynamisch Speicherplatz reservieren).
Zählen Sie außerdem bei beiden Verfahren in jedem Sortiervorgang die Anzahl der Vergleiche und die
Anzahl der Vertauschungen (mit Hilfe globaler Variablen). |
Hallo zusammen,
kann mir vielleicht jemand sagen warum mein Programm bei Quicksort immer eine 0 an die 2 Stelle des Array speichert??
Was mach ich falsch bzw. muss umgeändert werden, dass mein Quicksort Algorithmus richtig funktioniert??
Hab ich meine Variablen richig gesetzt, die die Anzahl der Vergleiche und Vertauschungen erfasst??
Hier mein Code:
| 1: |
| | 2: |
| | 3: | #include<stdio.h>
| | 4: | #include<stdlib.h>
| | 5: |
| | 6: |
| | 7: | int VertB=0, VertQ=0, VergB=0, VergQ=0;
| | 8: |
| | 9: | void bubblesort(double *array, double length){
| | 10: | int i, j;
| | 11: | for (i = 0; i < length; ++i) {
| | 12: | for (j = 0; j < length - i - 1; ++j) {
| | 13: | if (array[j] > array[j + 1]) {
| | 14: | double tmp = array[j];
| | 15: | array[j] = array[j + 1];
| | 16: | array[j + 1] = tmp;
| | 17: | VertB++;
| | 18: | }
| | 19: | }
| | 20: | VergB++;
| | 21: | }
| | 22: | }
| | 23: |
| | 24: | void quicksort(double a[], int li, int re){
| | 25: | if(re>li){
| | 26: | int i=li-1, j=re;
| | 27: | double tmp;
| | 28: | while(1){
| | 29: | while(a[++i]<a[re]){VergQ++;}
| | 30: | while(a[--j]>a[re]){VergQ++;}
| | 31: | if(i>=j) break;
| | 32: | tmp=a[i]; a[i]=a[j]; a[j]=tmp;VertQ++;
| | 33: | }
| | 34: | tmp=a[i]; a[i]=a[re]; a[re]=tmp;VertQ++;
| | 35: |
| | 36: | quicksort(a, li, i-1);
| | 37: | quicksort(a, i+1, re);
| | 38: | }
| | 39: | }
| | 40: |
| | 41: | int main(){
| | 42: | int n;
| | 43: | printf("Bitte geben sie die Länge ihrer Sortierreihe ein: ");
| | 44: | scanf("%i", &n);
| | 45: | double*p,*q;
| | 46: | p=(double*)malloc((n+1)*sizeof(double));
| | 47: | q=(double*)malloc((n+1)*sizeof(double));
| | 48: | int i=0;
| | 49: | printf("Zahlenfolge:\n");
| | 50: | for(i=0; i<n; i++){
| | 51: | p[i]=(double)rand()/12345;
| | 52: | q[i]=p[i];
| | 53: | printf("%.2lf\t",p[i]);
| | 54: | }
| | 55: | printf("\nSortieren mit BubbleSort:\n\n");
| | 56: | bubblesort(p, n);
| | 57: | for(i=0; i<n; i++){
| | 58: | printf("%.2lf\t",p[i]);
| | 59: | }
| | 60: | printf("\nVertauschungen: %i", VertB);
| | 61: | printf("\nVergleiche: %i\n", VergB);
| | 62: | printf("\nSortieren mit Quicksort:\n\n");
| | 63: | quicksort(q, 1, n);
| | 64: | for(i=0; i<n; i++){
| | 65: | printf("%.2lf\t",q[i]);
| | 66: | }
| | 67: | printf("\nVertauschungen: %i", VertQ);
| | 68: | printf("\nVergleiche: %i\n", VergQ);
| | 69: | }
| | 70: |
|
Bitte um eure Hilfe.
Schon mal danke.
Gruß Tobias
|
|
| |
|
Hallo zusammen,
wollt nur noch mal auf mein Problem aufmerksam machen.
Ist es zu trivial oder einfach nicht lösbar?
Bitte um Feedback.
Gruß Tobias
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:18 Mo 26.01.2009 | | Autor: | bazzzty |
> Hallo zusammen,
>
> wollt nur noch mal auf mein Problem aufmerksam machen.
> Ist es zu trivial oder einfach nicht lösbar?
Ich nehme an: Zu mühsam. Du hast Dir selbst anscheinend noch nicht die Mühe gemacht, "unnötige" Teile aus Quicksort zu entfernen bzw. Quicksort auf eine Form zu bringen, in der in einer Zeile auch nur ein Statement steht. Das ist einfach schwerer zu debuggen. Der klassische Weg wäre: Du nimmst Dir eine Eingabe und lässt Dir Schritt für Schritt ausgeben, was Deine Implementierung macht, und vergleichst das damit, was sie machen sollte. Das kannst Du so gut wie jeder andere auch.
Ein paar Fehler(?) und Anmerkungen zum Code habe ich aber trotzdem:
| 1: |
| | 2: | 24: void quicksort(double a[], int li, int re){
| | 3: |
| | 4: | // (24) für ein Array a[0]...a[n-1] ist li=1 und re=n. Einfacher
| | 5: | // wäre sicherlich, direkt Indizes zu verwenden, aber gut.
| | 6: | // WIr merken uns: beide Zähler enthalten 1-basierte Werte.
| | 7: |
| | 8: |
| | 9: | 25: if(re>li){
| | 10: | 26: int i=li-1, j=re;
| | 11: |
| | 12: | // (26) hier wird i auf den ersten Index zurückgesetzt
| | 13: | // erster Aufruf: i=0, j=n. Jetzt zeigt i auf das erste Element,
| | 14: | // j direkt hinter das letzte. Wichtig: a[re] ist a[n] ist nicht
| | 15: | // Teil des Arrays.
| | 16: |
| | 17: |
| | 18: | 27: double tmp;
| | 19: | 28: while(1){
| | 20: |
| | 21: |
| | 22: | 29: while(a[++i]<a[re]){VergQ++;}
| | 23: | // (29) hier wird i zuerst inkrementiert, und dann ausgewertet.
| | 24: | // a[0] wird also nie angeschaut Dafür wird mit a[re] verglichen, // das ist aber a[n], also gar nicht Teil des Arrays.
| | 25: | // Was da vielleicht stehen sollte:
| | 26: | // while(a[i]<a[re-1]){i++} oder for (;a[i]<a[re-1];i++){...}
| | 27: | // Es gibt einen Grund warum man in fast allen Code Conventions
| | 28: | // das Auswerten von Bedingungen mit Nebeneffekten verbietet.
| | 29: | // Ansonsten: Hier zeigt sich genau, welches Problem Du Dir mit den
| | 30: | // natürlichen Indizes li und re eingehandelt hast.
| | 31: |
| | 32: |
| | 33: | 30: while(a[--j]>a[re]){VergQ++;}
| | 34: | // Bei j ist es anders: Das fängt bei n an, und darf deshalb zuerst
| | 35: | // dekrementiert werden. Ändert aber nichts daran, dass "re" hinter
| | 36: | // das Array zeigt. Was den Stil angeht, gilt dasselbe wie
| | 37: | // oben.
| | 38: |
| | 39: |
|
Ich gehe jetzt nicht bis zum Schluss durch. Vielleicht ist das Problem mit den Indizes das einzige, vielleicht auch nicht. Damit solltest Du Dich nochmal auseinandersetzen.
Meine Tipps:
* Mach Dir klar, was Deine Parameter bedeuten. Am einfachsten ist es, wenn Du immer nur mit Arrayindizes rechnest, also quicks(0,n-1) aufrufst, und dann konsistent dabeibleibst.
* Keine Bedingungen der Form "while(a[++i]<a[re])", wenn Du nicht wirklich sicher bist, dass das tut, was Du willst. Ganz besonders: Keine while-Schleifen ohne vernünftigen Body (in diesem Fall das hochzählen der Vergleiche). So wenige Zeilen wie möglich schreiben zu wollen ist ein Anfängerfehler. Code muss gut lesbar und nachvollziehbar sein. Quicksort-Code sollte man mit einem Zettel und einem Stift "emulieren" können. Preinkremente und solche Spielereien versperren da nur die Sicht.
* Lass erstmal alles weg, wo es nur um das Zählen der Vergleiche geht. Schreibe wenigen Code, und den sauber. Der Code auf Wikipedia entspricht Deinem Quicksort, wenn Du nur mit Array-Indizes arbeitest.
|
|
|
| |
|
Hallo bazzty,
danke für die Hilfe.
Hab jetzt meinen Fehler entdeckt.
Man muss in Zeile 63 nicht "n" sondern "n-1" an die Methode übergeben.
Lg Tobias
|
|
|
|
