3. Quicksort

Quicksort

  • J

    Hallo Leute,

    ich habe den folgenden Quellcode für Quicksort erstellt, aber die Sortierung erfolgt falsch...ich weiß einfach nicht weiter...Hat jemand von euch ein Vorschlag oder Anmerkung was ich falsch mache... freue mich über jede Hilfe.

    Danke im Voraus!!! 🙂 🙂

    #include<iostream>
    #include<fstream>
    #include "quicksort.h"
    #include<time.h>
    #include<ctime>

    using namespace std;

    void quicksort(int a[], int links, int rechts);
    int partition(int a[], int links, int rechts);

    //---------------------------------------------
    void quicksort(int a[], int links, int rechts){
    //int pivot = a[rechts];
    if (links < rechts){
    int s = partition(a, links, rechts);
    quicksort(a, links, s-1);
    quicksort(a, s+1, rechts);

    }
    }

    //---------------------------------------------
    int partition(int a[], int links, int rechts){
    cout<<"in partition\n";
    int pivot = a[rechts];
    int i = links - 1;
    int help;
    // int li, re;
    //li = links;
    // re = rechts;
    //pivot = a[re];
    /* do{
    while(a[l]<pivot) i++;
    }while(li<=re);*/

    for(int j=links; j<=(rechts-1); j++) {

    if( a[j] <= pivot ) {
    cout<<"\nwenn j kleiner pivot ist ...\n";
    i = i+1;
    help = a[i];
    a[i] = a[j];
    a[j] = help;
    cout<<"\nHier kommt: "<< i <<endl;
    cout<<"Hier kommt: "<< j <<endl;
    }

    }
    help = a[i+1];
    cout << i<<endl;
    a[i+1] = a[pivot];
    a[pivot] = help;
    cout <<"\nAusgabe von i: "<< i<<endl;
    cout <<"Ausgabe von pivot: "<< pivot<<endl;

    return i+1;

    }

    //////////////////////////////////////////////////
    ////////// MAIN //////////////////////////////////
    //////////////////////////////////////////////////

    int main(int argc, char *argv[]){

    //int a[]={2,3,1,0};

    int a[]={7,8,2,4};

    int count = sizeof(a)/sizeof(*a);

    quicksort(a, 0, count-1);
    cout<< "\n\nmain Aufrug..quicksort" <<endl;

    for(int i = 0; i<count;i++)
    cout<<a[i]<<endl;

    return 0;
    }

    0
  • Mod

    Nun, da hast du wohl an einer Stelle einen Zugriff außerhalb deines Arrays. Geh doch mal mit einem Debugger Schritt für Schritt durch und guck, wo der falsche Zugriff stattfindet. Sind ja nicht zu viele Schritte, das ist noch machbar.

    Hättest du gleiche einen vector genommen statt einem Array, könntest du nun einfach dessen Debugfunktionen aktivieren und würdest sofort das Problem finden. Aber da du anscheinend Masochist bist und rohe Arrays magst, dürftest du dich über die Debugsitzung sicherlich freuen.

    0
  • N

    Spontan würde ich tippen, der Fehler kommt hierher

    quicksort(a, links, s-1);
quicksort(a, s+1, rechts);

    Denn was ist los mit Element s ?

    0
Anmelden zum Antworten