Sort-Versuch bis Mitternacht^^

[Goldenflash]

Hallo,
Ich wollte mal eben in devC++ einen Sortieralgorithmus schreiben, das ist nun schon ein paar Stunden her.
Erstmal zum Code:

#include <iostream.h>
using namespace std;

int i;
int middle (int b[]) //sucht den Mittelwert eines Feldes
{
int big=0;
int small=b[0];
int average=0;
for (i=0;i<sizeof(b);i++)
{
if (b[i]<small) small=b[i];
if (b[i]>big) big=b[i];
}
average=(big+small)/2;

return(average);
}



int mysort(int feld[])
{
int m;
int n=0;
int o;
int p;

if (sizeof(feld)>1)
{

//Mittelwert abholen und schauen wieviele Elemente kleiner als der
//Mittelwert sind (Anzahl=p)
m=middle(feld);
for (i=0;i<sizeof(feld);i++)
{
if (feld[i]<m) n++;
}
p=n;


o=sizeof(feld)-p; //Anzahl der Elemente die groesser als der
//Mittelwert sind

//ein Array für die kleinen und eins für die grossen
int small[p];
int big[o];

//die kleinen ins entsprechende Array kopieren
n=0;
for (i=0;i<sizeof(feld);i++)
{
if (feld[i]<m)
{
small[n]=feld[i];
n++;
}
}


//das gleiche für die grossen...
n=0;
for (i=0;i<sizeof(feld);i++)
{
if (feld[i]>=m)
{
big[n]=feld[i];
n++;
}
}
// ein Array für die kleinen sortierten Werte und eins für die
//grossen
int klein[p];
int gross[o];
klein=mysort(small);
gross=mysort(big);

//feld aus den beiden sortierten Array zusammensetzen
for (i=0;i<p;i++)
{
feld[i]=klein[i];
}
n=0;
for (i=(n+1);i<(sizeof(feld));i++)
{
feld[i]=gross[n];
n++;
}

}
return(feld);
}


int main() {
int a[9]={5,2,8,1,4,5,7,3,0};
int b[9];
b=mysort(a);

system("PAUSE");
return 0;
}



Abgesehen von dem wirklich grausamen Stil und der umständlichen Herandgehensweise (will gar nicht wissen wieviele Flops das kostet :P ) kompiliert das ganze Monster auch gar nicht erst :( .



main.cpp: In function `int mysort(int*)':
main.cpp:48: error: incompatible types in assignment of `int' to `int[((unsigned int)((int)p))]'

main.cpp:59: error: incompatible types in assignment of `int' to `int[((unsigned int)((int)o))]'
main.cpp:72: error: invalid conversion from `int*' to `int'
main.cpp: In function `int main()':
main.cpp:80: error: incompatible types in assignment of `int' to `int[9]'



Wäre über Hilfe sehr dankbar :)
Gruß Goldenflash

[fumir]

oooh jeee *bedächtigkopfschüttel* :-)

erst mal gibt sizeof(feldvariable) nicht die anzahl der feldelemente sondern die größe des zeigers der auf das feld zeigt (vermutlich also etwa 4)
vergiss dass es diesen befehl gibt, bis du etwas von C verstehst :-)

dann kannst du kein feld mit variabler größe anlegen. der compiler muss die feldgröße kennen, bevor das programm startet. etwas wie
int small[p];
geht daher nicht
bei c++ gehts wenn p als const deklariert ist (const int p=99), in C muss die feldgröße ein literal (z.b. 99) oder eine symbolische konstante (#define feldgröße 99) sein.
in jedem fall muss die feldgröße also de fakto konstant sein.

am besten legst du mal ne konstante wie
const int feldmax=99;
an (wobei 99 größer sein soll als alle benötigten felder)
und legst alle felder so an:
int feld(feldmax);

mach die felder immer etwas größer als benötigt.
z.b. du willst 13 werte speichern.
dann mach
int feld[15];
feld[0]=-999;
feld[14]=-999;
verwende die indizes von 1 bis 13 also feld[1] bis feld[13] um die werte zu speichern.
verwende zum sortieren nur positive zahlen.
prüfe am ende des programms, ob in feld[0] und feld[14] immer noch -999 steht.
falls nicht, stimmt etwas nicht im programm.
(das sind natürlich nur tips für anfänger)

bring das erst mal alles in ordnung, dann sehen wir weiter :-)

[fumir]

soll das etwa quicksort werden ? :-)

[Goldenflash]

Also ertsmal danke für die Antwort.
Da hab ich ja mal einiges verbockt. :P


soll das etwa quicksort werden ? :-)
Naja immerhin hast du es erkannt. :D
Ich hab nun seit über 2 Jahren nichts mehr programmiert und wollte wieder reinkommen, aber da hab ich noch paar Probleme. :-k

[Goldenflash]

Alles soweit so gut.
Mein einziges Problem ist, dass sowas

klein=mysort(small); obwohl alle die gleiche Länge haben, nicht geht.
Da bekomme ich immer
incompatible types in assignment of `int' to `int[256]' ](*,)

[McJenso]

Hallo,

übleg was für einen Typen mysort() zurück gibt und was für ein Type klein ist. Klein ist ja zumindest ein Zeiger.
Ich verstehe auch nicht warum du das machen willst, es sei denn du hast den Code grundlegend geändert. Du deklarierst klein innerhalb von mysort() und weist klein dann das Ergebnis zu?

Gruß

Jens

[Goldenflash]

#include <iostream.h>
using namespace std;


int middle (int b[]) //sucht den Mittelwert eines Feldes
{
int big=0;
int small=b[0];
int average=0;
for (int i=0;i<sizeof(b);i++)
{
if (b[i]<small) small=b[i];
if (b[i]>big) big=b[i];
}
average=(big+small)/2;

return(average);
}



int mysort(int feld[256])
{
int m;
int n=0;
int o;
int p;
int small[256];
int big[256];
int klein[256];
int gross[256];
for (int i=0;i<256;i++)
{
klein[i]=999;
gross[i]=999;
big[i]=999;
small[i]=999;
}

if (feld[0]!=999)
{

//Mittelwert abholen und schauen wieviele Elemente kleiner als der
//Mittelwert sind (Anzahl=p)
m=middle(feld);
for (int i=0;i<256;i++)
{
if (feld[i]<m) n++;
}
p=n;


o=256-p; //Anzahl der Elemente die groesser als der
//Mittelwert sind

//ein Array für die kleinen und eins für die grossen


//die kleinen ins entsprechende Array kopieren
n=0;
for (int i=0;i<256;i++)
{
if (feld[i]<m)
{
small[n]=feld[i];
n++;
}
}


//das gleiche für die grossen...
n=0;
for (int i=0;i<256;i++)
{
if (feld[i]>=m)
{
big[n]=feld[i];
n++;
}
}
// ein Array für die kleinen sortierten Werte und eins für die
//grossen

klein=mysort(small);
gross=mysort(big);

//feld aus den beiden sortierten Array zusammensetzen
for (int i=0;i<p;i++)
{
feld[i]=klein[i];
}
n=0;
for (int i=(n+1);i<256;i++)
{
feld[i]=gross[n];
n++;
}

}
return(feld);
}


int main() {
int a[9]={5,2,8,1,4,5,7,3,0};
int b[256];
int i;
for (i=0;i<9;i++)
{
b[i]=a[i];
}
for (int n=i;n<256;n++)
{
b[n]=999;
}
b=mysort(b);

system("PAUSE");
return 0;
}




Du deklarierst klein innerhalb von mysort() und weist klein dann das Ergebnis zu?
Stichwort "Rekursion" ich schnappe mir die Liste mit den kleineren werten und ordne diese zuerst...

Was ich so seltsam finde ist dass er klein nicht als array zu akzeptieren scheint.

[McJenso]

Okay, jetzt weiß ich was du möchtest.

int feld [256]; bedeutet:
feld[0] ist ein integer, feld [1] ...feld[255] alles integer
feld ohne jeden index ist ein Zeiger auf einen Integer. Genauer gesagt ist es der Zeiger auf feld[0], okay?

int mysort(int feld[256])
mysort gibt per Deklaration einen Integer zurück.
return feld;
feld ist aber ein Zeiger. Das geht so nicht.


Was du wirklich vor hast, wird hier klar.
b=mysort(b);
Du möchtest das b innerhalb der Funktion manipuliert wird, sonst nix. Warum übergibst du erst b und schreibst es dann zurück. Besser ist es, der Funktion mitzuteilen wo sie auf b zugreifen kann. Das machst du mittels eines Zeigers.

void mysort (int*);
Bei dieser Deklaration gibt es keinen Rückgabewert. Dh. du schließt sie nur mit return; ab und sie erwartet einen Zeiger als der auf einen Integer verwist als Argument.
void mysort (int* pFeld){
pFeld[0] = 1;
pFeld[1] = 2;
}
So greifst du dann auf die Felder zu.

Gruß

Jens

[fumir]

bei quicksort solltest du das element mit dem verglichen wird (bei dir der mittelwert) in konstanter zeit berechnen (bei dir lineare zeit).

üblicherweise nimmt man einfach den ersten wert und vergleicht die übrigen mit diesem.
oder besser:
man nimmt den ersten, den letzten und einen wert aus der mitte. berechnet von diesen drei werten den mittleren, und verwendet diesen zum vergleichen. oder
oder auch gut:
man nimmt nicht den ersten sondern einen zufälligen wert aus dem feld

dann sollte man im wesentlichen ohne zusätzlichen speicherbedarf auskommen und nicht ne menge hilfsfelder anlegen. das geht alles im ursprünglichen feld!

du hast also noch einiges zu tun, um quicksort zu bekommen.

[fumir]

ich sehe, einer meiner tips wurde mißverstanden: du sollst nicht überall mit 256 feldelementen rumgurken, wenn du nur 9 werte sortieren willst! du solltest die felder nur so groß anlegen, dass du dir keine sorgen machen musst wenn du versehentlich (durch programmfehler) mal einen etwas zu großen index verwendest!

[fumir]

noch ein fehler:
int middle (int b[]) //sucht den Mittelwert eines Feldes
{
int big=0;
int small=b[0];

das ist falsch.
du must small auf den größtmöglichen integerwert (oder zumindest auf den größten feldwert) setzen.
warum sollte dieser größte wert ausgerechnet in b[0] stehen?

auserdem hast du ja immer noch sizeof drinstehen (ein paar zeilen drunter) !???

[fumir]

vielleicht noch ein letzter tip:

nimm dir 9 zettel und schreib deine feldwerte drauf.
leg die zettel vor dich hin und mach mal quicksort per hand.
mach das ein paar mal und überleg dir, wie man es machen sollte, damit die zettel möglichst wenig bewegt werden.

nimm dir 9 neue zettel und schreib mal ungewöhnliche werte drauf (z.b. schon sortiert, falsch sortiert, alle gleich, alle bis auf einen gleich, etc.etc.)
spiel weiter quicksort.

spiele so lange mit den zetteln, bis du quicksort und dessen schwierigkeiten wirklich verstanden hast.

schieb dein programfile in den papierkorb und fang noch mal neu an - diesmal langsam und richtig :-)

wenn du genug mit den zetteln gespielt hast (und quicksort verstanden hast) kannst du das programmieren eigentlich auch lassen: ist eh schon tausendmal hingeschrieben worden :-)

trotzdem viel spass noch :-)