-         

Seite 1 von 2 12 LetzteLetzte
Ergebnis 1 bis 10 von 12

Thema: Sort-Versuch bis Mitternacht^^

  1. #1
    Erfahrener Benutzer Fleißiges Mitglied
    Registriert seit
    17.08.2004
    Beiträge
    169

    Sort-Versuch bis Mitternacht^^

    Anzeige

    Hallo,
    Ich wollte mal eben in devC++ einen Sortieralgorithmus schreiben, das ist nun schon ein paar Stunden her.
    Erstmal zum Code:
    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
    ---

  2. #2
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    25.10.2007
    Ort
    41462 Neuss
    Alter
    49
    Beiträge
    375
    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

  3. #3
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    25.10.2007
    Ort
    41462 Neuss
    Alter
    49
    Beiträge
    375
    soll das etwa quicksort werden ?

  4. #4
    Erfahrener Benutzer Fleißiges Mitglied
    Registriert seit
    17.08.2004
    Beiträge
    169
    Also ertsmal danke für die Antwort.
    Da hab ich ja mal einiges verbockt. :P

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

  5. #5
    Erfahrener Benutzer Fleißiges Mitglied
    Registriert seit
    17.08.2004
    Beiträge
    169
    Alles soweit so gut.
    Mein einziges Problem ist, dass sowas
    Code:
    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]'
    ---

  6. #6
    Erfahrener Benutzer Roboter Experte
    Registriert seit
    20.05.2006
    Ort
    Lippe
    Alter
    48
    Beiträge
    524
    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

  7. #7
    Erfahrener Benutzer Fleißiges Mitglied
    Registriert seit
    17.08.2004
    Beiträge
    169
    Code:
    #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.
    ---

  8. #8
    Erfahrener Benutzer Roboter Experte
    Registriert seit
    20.05.2006
    Ort
    Lippe
    Alter
    48
    Beiträge
    524
    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

  9. #9
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    25.10.2007
    Ort
    41462 Neuss
    Alter
    49
    Beiträge
    375
    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.

  10. #10
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    25.10.2007
    Ort
    41462 Neuss
    Alter
    49
    Beiträge
    375
    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!

Seite 1 von 2 12 LetzteLetzte

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •