3. Problem mit Pointern beim Quicksort-Algorhytmus

Problem mit Pointern beim Quicksort-Algorhytmus

  • ?

    Hallo, ich schreibe grade eine Funktion die eine Start und Endadresse auf dem Arbeitsspeicher nimmt, und die integer größen darin sortiert.
    aber irgendwie scheint er irgendwas mit den Zeigern zu verkacken... er kompiliert eins a, und gibt mir dann eine Gleitkomma ausnahme zurück...

    #include<iostream>
using namespace std;
void QS(int* start,int* end)
{
int laenge=0;
for(int i=0;&start[i]!=end;i++)laenge++;
laenge/=4;
int pivo=rand()%laenge;
pivo=*(start+pivo);
string klein,gross;
int pivo_counter=0;

for(int i=0;i<laenge;i++)
	{
	if( *(start+i) < pivo ) klein += *(start+i);
	if( *(start+i) > pivo ) gross += *(start+i);
	else pivo_counter++;
	}

int laenge_klein=klein.size();
int laenge_gross=gross.size();

for(int i=0;i<laenge_klein;i++)
*(start+i)=(int)klein[i]-48;

for(int i=0;i<pivo_counter;i++)
*(start+laenge_klein+i)=pivo;

for(int i=0;i<laenge_gross;i++)
*(start+laenge_klein+pivo_counter+i)=(int)gross[i]-48;

int* start_klein=start;
int* end_klein=start+laenge_klein;
int* start_gross=start+laenge_klein+pivo_counter+1;
int* end_gross=start+laenge_klein+pivo_counter+laenge_gross;
QS(start_klein,end_klein);
QS(start_gross,end_gross);
}

int main()
{
int test[5]={ 1, 3, 2 , 4, 1};
int* start=&test[0];
int* end=&test[4];
QS(start,end);
for(int i=0;i<5;i++)cout<<test[i];
cin.get();
return 1;

}

    Vielen dank im Vorraus...

    0
  • *

    Habs nur schnell getestet. Du dividierst in folgender Zeile:

    [cpp]
    int pivo=rand()%laenge;
    [code]

    Durch 0. D.h. Laenge ist 0. Muss irgendetwas mit deiner Rekursion zu tun haben.

    0
  • ?

    Habe das Programm bearbeitet, war wirklich ein sehr dummer fehler^^ Hat auch sonst nich mit dem algorhytmus harmoniert, so wie er laufen soll..

    hier die neue: das Problem besteht aber weiterhin..

    #include<iostream>
    using namespace std;
    void QS(int* start,int* end)
    {
    int laenge=0;
    for(int i=0;&start[i-1]!=end;i++)laenge++;
    cout<<"länge: "<<laenge<<endl;
    int pivo=rand()%laenge;
    pivo=start[pivo];
    string klein,gross;
    int pivo_counter=0;
    cout<<"pivo: "<<pivo<<endl;

    for(int i=0;i<laenge;i++)
    {
    if( start[i] < pivo ) {klein += (char)start[i];} //
    if( start[i] > pivo ) gross += (char)start[i];
    else pivo_counter++;
    }
    int laenge_klein=klein.size();
    int laenge_gross=gross.size();

    for(int i=0;i<laenge_klein;i++)
    *(start+i)=(int)klein[i]-48;

    for(int i=0;i<pivo_counter;i++)
    *(start+laenge_klein+i)=pivo;

    for(int i=0;i<laenge_gross;i++)
    (start+laenge_klein+pivo_counter+i)=(int)gross[i]-48;
    int     start_klein=start;
    int* end_klein=&start[laenge_klein];
    int* start_gross=&start[laenge_klein+pivo_counter+1];
    int* end_gross=&start[laenge_klein+pivo_counter+laenge_gross];
    if(laenge_klein>=2)
    QS(start_klein,end_klein);
    if(laenge_gross>=2)
    QS(start_gross,end_gross);
    }

    int main()

    {
    int test[7];
    test[0]=2;
    test[2]=3;
    test[3]=5;
    test[4]=4;
    test[1]=8;
    test[5]=13;
    test[6]=-2;
    int* start=&test[0];
    int* end=&test[6];
    QS(start,end);
    for(int i=0;i<5;i++)cout<<start[i];
    cin.get();
    return 1;

    }
    [cpp]

    0
  • *

    Ich schau es mir gerade noch einmal an. Zu erst einmal solltest du in der
    main Funktion 0 zurückgeben, sonst ist es ein Fehler-Rückgabewert. Und
    zweitens solltest du als erstes einen Prototyp deiner Funktion anlegen, und
    dann erst die Funktion definieren!

    0
  • *

    So, ich hab es mir jetzt mal weiter angeschaut: was soll denn bitte folgende
    Zeilen bedeuten?

    if( start[i] < pivo ) {klein += (char)start[i];}
if( start[i] > pivo ) gross += (char)start[i];
    0
  • ?

    Ich speichere die jeweils kleineren beziehungsweise größeren vergleichszahlen in jeweiligen strings ab.
    Mein Shema sollte eigentlich so laufen:
    Nimm anfangs und endadresse
    nimm eine stichprobe
    vergleiche alle damit und merke was kleiner oder größer war
    schreibe nun den speicher neu in der Form #kleinere#stichprobe#größere
    fahre fort mit dem speicherbereich in dem kleinere gespeichert ist
    dann mit dem wo größere drin gespeichert ist..

    ich danke für deine hilfe^^

    0
  • ?

    HAbe das ganze noch einmal generalüberholt. jetz müssten meiner ansicht nach uch alle adressen soweit stimmen ;,-)

    #include<iostream>
using namespace std;
void QS(int* start,int* end)
{
int laenge=0;
for(int i=0;&start[i-1]!=end;i++)laenge++;
cout<<"länge: "<<laenge<<endl;
int pivo=rand()%laenge;
pivo=start[pivo];
string klein="",gross="";
int pivocounter=0;
cout<<"pivo: "<<pivo<<endl;

for(int i=0;i<laenge;i++)
	{
	if( start[i] < pivo ) {klein += (char)start[i];}                //
	if( start[i] > pivo ) gross += (char)start[i];
	else pivocounter++;
	}
int laenge_klein=klein.size();
int laenge_gross=gross.size();

for(int i=0;i<laenge_klein;i++)
start[i]=(int)klein[i];

for(int i=0;i<pivocounter-1;i++)
start[laenge_klein+i]=pivo;

for(int i=0;i<laenge_gross;i++)
start[laenge_klein+pivocounter+i]=(int)gross[i];

int* start_klein=start;
int* end_klein=&start[laenge_klein-1];
int* start_gross=&start[laenge_klein+pivocounter];
int* end_gross=&start[laenge_klein+pivocounter+laenge_gross-1];
klein="";gross="";

for(int i=0;i<laenge;i++)cout<<start[i]<<" ";
cout<<endl;
if(laenge_klein>1)
QS(start_klein,end_klein);
if(laenge_gross>1)
QS(start_gross,end_gross);
}

int main()

{
int test[7];
test[0]=6;
test[1]=71;
test[2]=3;
test[3]=5;
test[4]=2;
test[5]=13;
test[6]=7;
int* start=&test[0];
int* end=&test[6];
QS(start,end);
for(int i=0;i<5;i++)cout<<start[i];
cin.get();
return 0;

}
    0
  • ?

    Es ist fertig, war etwas ganz triviales. else vor dem 2. if vergessen^^

    Wer es sich nochmal ansehen mag:

    #include<iostream>
using namespace std;

void QS(int* start,int* end)
{
int laenge=0;
for(int i=0;&start[i-1]!=end;i++)laenge++;
int pivo=rand()%laenge;
pivo=start[pivo];
string klein="",gross="";
int pivocounter=0;

for(int i=0;i<laenge;i++)
	{
	if( start[i] < pivo ) {klein += (char)start[i];}
	else                //
	if( start[i] > pivo ) {gross += (char)start[i];}
	else {pivocounter++;}
	}
int laenge_klein=klein.size();
int laenge_gross=gross.size();

for(int i=0;i<laenge_klein;i++)
start[i]=(int)klein[i];

for(int i=0;i<pivocounter;i++)
start[laenge_klein+i]=pivo;

for(int i=0;i<laenge_gross;i++)
start[laenge_klein+pivocounter+i]=(int)gross[i];

int* start_klein=start;
int* end_klein=&start[laenge_klein-1];
int* start_gross=&start[laenge_klein+pivocounter];
int* end_gross=&start[laenge_klein+pivocounter+laenge_gross-1];
klein="";gross="";
if(laenge_klein>1)
QS(start_klein,end_klein);
if(laenge_gross>1)
QS(start_gross,end_gross);
}

int main()

{
string test;
getline(cin,test);
int array[1000];
for(int i=0;i<test.size();i++)array[i]=(int)test[i];
int* start=&array[0];
int* end=&array[test.size()-1];
QS(start,end);
start=&array[0];
for(int i=0;i<test.size();i++)cout<<(char)start[i]<<" ";
cin.get();
return 0;

}

    weiß jemand wie ich integer variablen dynamisch speichern kann? also um das int array[1000] zu vermeiden^^

    0
Anmelden zum Antworten