[C/C++] Quicksort (irgendwo muss ein minifehler sein)*gefunden*

Dieses Thema im Forum "Programmierung & Entwicklung" wurde erstellt von Xen0n, 16. Januar 2009 .

Schlagworte:
Status des Themas:
Es sind keine weiteren Antworten möglich.
  1. 16. Januar 2009
    Quicksort (irgendwo muss ein minifehler sein)*gefunden*

    Hi Leute,

    ich möchte einen Quicksort programmieren, mit dem ich ein array von array[1] (ohne 0) bis array[ANZAHL] mit Zufallszahlen fülle.

    Problem: Wenn ANZAHL kleiner als ~150 ist, geht alles prima und schnell. Sobald ANZAHL ~ 200 oder größer ist, verfängt sich das Programm in einer Endlosschleife und ich weiß nicht warum.

    Hier der Code:

    main()
    Code:
    #include <stdio.h>
    #include <stdlib.h> 
    #include "analyse.h" // contains the stopp_uhr(_); function
    
    #define ANZAHL 10 // amount of array fields
    #define INIT 4711 // init value for same values each time 4711
    #define AUSGABE 1 // print flag: 1->print / 0->print not
    
    
    int partition(int* array, int begin, int end);
    void quicksort(int* array, int begin, int end);
    
    int main()
    {
     
     int array[ANZAHL+1]={0}; 
    
     int x=0; // counter for filling the array
     int min; // selection sort flag
     int i, j, // loop variables
     puffer; // buffer for changing
    
     srand(INIT); 
    
     // fill the array with random numbers loop and print them
     for(x=1; x<=ANZAHL; x++) 
     {
     array[x]=rand();
     if (AUSGABE) printf("%d ",array[x]);
     }
     printf("\n");
     
    
     quicksort(array, 0, ANZAHL);
     
     //output sorted array
     for(x=1; x<=ANZAHL; x++) 
     {
     if (AUSGABE) printf("%d ",array[x]);
     }
    }
    
    quicksort()
    Code:
    void quicksort(int* array, int begin, int end){
     int iCompare;
     if(begin < end){
     iCompare = partition(array, begin, end); //devide the array
     quicksort(array, begin, iCompare-1); 
     quicksort(array, iCompare, end); 
     } 
    }
    
    partition()
    Code:
    int partition(int* array, int begin, int end){
     int iPivot = array[end]; //last random number of the (part)list gets the pivotelement
     int i = begin;
     int j = end;
     int puffer; 
     while(i<j)
     {
     while(array[i]<iPivot && i < j){i++;}
     while(array[j]>iPivot && i < j){j--;}
     if(i==j){ return i; }
     puffer=array[i];
     array[i]=array[j];
     array[j]=puffer; 
     } 
     return i;
    }
    
    Ich suche jetzt schon ewig danach und sehe mittlerweile nichts mehr. Ich hoffe hier findet jmd. was, ich würde mich echt riesig freuen

    Bw is klaro.
     
  2. 16. Januar 2009
    AW: Quicksort (irgendwo muss ein minifehler sein)

    ich denke du bekommst keine endlosschleife sondern das programm rechnet einfach bei so großen arrays relativ lange. laufzeit hängt ja stark vom pivotelement ab, im schlimmsten fall hast da ne laufzeit von O(n*n) ... lass das programm dann einfach mal 1-2 stunden laufen, dann wirst schon zu deinem ergebnis kommen
     
  3. 16. Januar 2009
    AW: Quicksort (irgendwo muss ein minifehler sein)

    In deiner partition()-Funktion sind einige Ungereimtheiten drinnen.
    Soweit ich im Pseudocode von Wikipedia (Quicksort – Wikipedia) die "teile"-Funktion durchgelesen habe, so sind da schonmal Unterschiede beim letzten Element.

    Schau dir einfach mal den Pseudocode dort an, und vergleiche das.
     
  4. 16. Januar 2009
    AW: Quicksort (irgendwo muss ein minifehler sein)

    Ein quicksort sollte für ein array mit 200 elementen nicht über 1 sekunde brauchen. Nichtmal ein bubblesort würde länger als ne Minute brauchen.. also 1-2 stunden sind da echt unrealistisch, trotzdem thx^^

    Danke durch die Seite hatte ich mir auch den quicksort auch beigebracht, allerdings wollte ich halt nirgends "kopieren" sondern selber schreiben.

    Das ding is ja dass mein code wunderbar funktioniert, nur ab einer bestimmten array-größe versagt und ich will einfach wissen woran es liegt.

    Ich hoffe einfach, dass sich jmd. die Zeit nimmt um den Code nachzuvollziehen und den Fehler findet^^

    //edit: und übrigens meine ich dass der pseudocode auf wiki garnicht korret ist
     
  5. 16. Januar 2009
    AW: Quicksort (irgendwo muss ein minifehler sein)*ungefunden*

    Der Fehler liegt darran:

    Code:
     while(array[i]<iPivot && i < j){i++;}
     while(array[j]>iPivot && i < j){j--;}
    
    Wenn array == array[j] == iPivot ist entsteht eine Endlosschleife.....

    Das ändern der Zeile
    while(array<iPivot && i < j){i++;}
    in
    while(array <=iPivot && i < j){i++;}

    sollte das Problem beheben.

    Edit: Hab grad bei Wiki den Artikel gelesen und wenn man das überträgt müsste man auch die andere Zeile mit einem >= ausstaten.

    Mfg Rushh0ur
     
  6. 16. Januar 2009
    AW: Quicksort (irgendwo muss ein minifehler sein)*ungefunden*



    Moa endlich es geht.. ich danke dir vielmals!

    Und ich stutze bei dem wiki artikel da i bis nach ganz rechts und j bis nach ganz links läuft reicht doch wenn sie stoppen sobald sie sich treffen (spätestens)
     
  7. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.