Sorteerfunctie in c++

[ger@ld]

Goedenavond,

Ik ben bezig met een betrekkelijk eenvoudig programma'tje, namelijk een array met getallen sorteren. Er zitten echter twee fouten in die ik er zo niet uit krijg:

1. De functie sorteer_aflopend() werkt niet correct. Er wordt goed gesorteerd (de ingegeven array), maar het kleinste getal dat wordt ingevoerd wordt steeds vervangen door een ENORM getal. Ik kom er maar niet achter waarom (dacht eigenlijk aan verwijzingen van pointers e.d.)
2. als ik 8 of meer waarden laat sorteren, krijg ik aan het eind van het programma (als het programma normaal "gewoon" afsluit) een "Rapport verzenden" foutmelding (van windows xp). Dit vind ik vaag.

Ik gebruik compiler dev-c++. Daar zou het dus ook nog evt. aan kunnen liggen (gebruik hem nog maar net.)

In de bijlage vind je de broncode.

Ik hoop dat iemand me kan helpen.
Bij voorbaat dank.

 

[c er]

in de functie sorteer_aflopend() staat:

for(i=0; i<n; i++)
{
    if(array[i]<array[i+1])
Dit zou
for(i=0; i<n-1; i++)
{
    if(array[i]<array[i+1])

moeten zijn, dus i van 0 tot n-1

Meer ruimte reserveren voor je tabel in main() is wel zo handig, dus
int getallen[] = {0};
wordt dan bijv.
int getallen[100] = {0};
Je kan dan maximaal 100 getallen inlezen in de tabel, nu heeft je tabel lengte 1 (en beginwaarde 0).

 

[ger@ld]

moeten zijn, dus i van 0 tot n-1

Deze oplossing snap ik niet (heb ik ook niet toegepast), die andere deed het goed genoeg om de vraag op opgelost te zetten (beide problemen opgelost).

Thanx c er...

N.B.: Wel een erg stomme fout trouwens.... Maar goed, dit vergeet ik nooit meer

 

[c er]

Deze oplossing snap ik niet (heb ik ook niet toegepast), die andere deed het goed genoeg om de vraag op opgelost te zetten (beide problemen opgelost).

In deze regel:
if(array<array[i+1])
gebruik je i en i+1 als index voor array. De index mag niet groter zijn dan n-1 (aangezien de tabel lengte n heeft),
dus ( i<n && (i+1)<n ) of eenvoudiger i<n-1.
Ofwel for(i=0; i<n-1; i++) in de sorteer-functie.
Als de tabel bijv. lengte 2 heeft hoeft er maar 1x vergeleken te worden
Als je bijv. een negatief en een positief getal invoert zal jouw oplossing waarschiijnlijk niet goed werken...

 

[ger@ld]

Waarom moet het kleiner zijn dan (n-1)? Het zal nooit even groot zijn als n. Volgens mij is mijn methode ook goed (of kijk ik dan erg scheef)

 

[c er]

Ik heb het hier over de functie sorteer_aflopend.
Je hebt hier een for-lus met daarna een if.

for(i=0; i<n; i++)
{
     if(array[i]<array[i+1])

De if conditie wordt volgens mij dan altijd uitgevoerd, dus i is dan maximaal n-1 (op jouw manier dus).
echter je hebt dit staan: array[i+1] voor i=n-1
wordt dus array[n] dit is volgens mij toch niet de bedoeling. Je vergelijkt dan de laatste waarde in de tabel met de volgende waarde die een onbekende waarde heeft.
Heb je het al uitgeprobeerd met bijv. 2 getallen 1 en -1.

 

[CoD_NL]

Wat c_er eigenlijk probeert te zeggen is:

for(i=0; i<n; i++)
{
     if(array[i]<array[i+1])

In jouw code is 'n' gelijk aan 'aantal'. En overal heb je de volgende conditie staan: 'i < n'. Dit houdt dus in dat de grootte van jouw array gelijk is aan 'n-1'. Als je dan een for-loop hebt die van 'i < n' gaat, dan bereikt die for loop dus de maximale grootte van de array en telt daar dus uiteindelijk nog 1 bij op. En dus val je buiten het bereik van je array.

Je for-loop wordt dan dus:

for(int i = 0; i < n-1; i++){
  if(array[i] < array[i+1])

 

[ger@ld]

Nu begrijp ik het! Ik heb het geprobeerd, en het werkt inderdaad beter. oplopend sorteren ging namelijk niet, en nu wel.

Hartelijk dank, beide!

 

[CoD_NL]

Ik heb nog een paar tips voor je. Globale variabele worden over het algemeen gezien als slecht design. (Sowieso is dit eigenlijk helemaal niet nodig binnen dit programma.)

Als je een for loop hebt en er volgt maar één statement, dan hoef je geen accolades te gebruiken. (het mag wel, maar het hoeft niet. Het kan uiteraard zijn dat je dit al wist. edit: lol, staat zelfs in onderstaand voorbeeld. Sorry.)

void toonreeks(int array[], int n, string prefix="Getallenreeks: ")
{
     cout << prefix;
     for(int i=0; i<n; i++)
     {
             cout << array[i];
             
             if(!((i+1)==n))
             cout << ", ";
             else
             cout << endl;
     }
}

Bovenstaande code zou je, indien je zou willen, ook korter kunnen schrijven. (je gebruikt dan eigenlijk een if else statement, alleen duidt het korter aan)

void toonreeks(const int array[], const int n, const string prefix="Getallenreeks: ")
{
     cout << prefix;
     for(int i = 0; i < n; i++)
       i < n-1 ? cout << array[i] << "," : cout << array[i] << endl;  
   // if(i <n-1) cout << array[i] << ","; else cout << array[i] << endl;
}

In het bovenstaand voorbeeld zal je ook zien dat alle parameters van het type const zijn. Als een waarde niet gewijzigd gaat worden binnen de functie, dan kun je hem als constante declareren. Dit zorgt ervoor dat je hem niet per ongeluk binnen de functie kan wijzigen.

int *sorteer_aflopend(int array[], int n)
{
    int herhaal = 1;
    do
    {
                  herhaal = 0;
                  int i = 0;
                  int tmp = 0;
                  for(i=0; i<n; i++)
                  {
                          if(array[i]<array[i+1])
                          {
                                    //cout << j << " " << k;
                                    //system("pause");
                                    tmp = array[i];
                                    array[i] = array[i+1];
                                    array[i+1] = tmp;
                                    tmp = 0;
                                    herhaal = 1;
                          }
                  }
                  
    
    }while(herhaal>0);
     return array;

    
}

In bovenstaande code stel je telkens de waarde van tmp in op 0, terwijl dit eigenlijk niet nodig is. Verder declareer je binnen een loop telkens een variabele, dit is eigenlijk ook niet nodig. Het maakt de code mijns inziens duidelijker als je ze buiten de loop declareert. (of het verder ook echt wat uitmaakt qua geheugen/snelheid denk ik niet, de compiler zal het heus wel weg optimaliseren) ; Als ze van te voren zijn gedeclareerd dan zou je in jouw voorbeeld ook iets als 'herhaal = tmp = i = 0;' kunnen schrijven.

int *sorteer_aflopend(int array[], const int n)
{
    int herhaal, tmp, i;
    do{
        herhaal = 0;
        for(i = 0; i < n-1; i++)
          if(array[i] < array[i+1])
          {
             tmp = array[i];
             array[i] = array[i+1];
             array[i+1] = tmp;
             herhaal = 1;
          }
        
    }while(herhaal == 1);
    return array;
}

De functie sorteer_aflopend hoeft zelfs geen return waarde te hebben. Test onderstaande maar eens:

#include <cstdlib>
#include <iostream>
using namespace std;

void toonreeks(const int *array, const int n, const string prefix="Getallenreeks: ")
{
     cout << prefix;
     for(int i = 0; i < n; i++)
       i < n-1 ? cout << array[i] << "," : cout << array[i] << endl;
}

void sorteer_aflopend(int *array, const int n)
{
     int herhaal, tmp, i;
     do{
         herhaal = 0;
         for(i = 0; i < n-1; i++)
           if(array[i] < array[i+1])
           {
              tmp = array[i];
              array[i] = array[i+1];
              array[i+1] = tmp;
              herhaal = 1;
           }
     } while(herhaal == 1);
}

int main(int argc, char *argv[])
{
    int n[] = { 1, 5, 3, 6, 4 };
    toonreeks(n, 5);
    sorteer_aflopend(n, 5);
    toonreeks(n, 5);
      
    system("PAUSE");
    return EXIT_SUCCESS;
}

 

[ger@ld]

De meeste punten die je noemt, zijn pas ontstaan toen ik ging debuggen. Ik probeerde op allerlei manieren het resultaat te verbeteren, niet wetende dat het aan de array bereik lag. Alleen de const waarden zaten niet in het oorspronkelijke design.