[C++] Getallen sorteren lukt niet

[Tha Man]

Hoi, mijn eerste post op GoT!

Val me even niet aan over het Mickey Mouse niveau van deze code Het is een opdracht voor school, en ik heb weinig zin om alles te gaan herschrijven naar coolere naamgeving etc.

De opdracht is feitelijk heel simpel: sorteer rij[] zodat de het laagste getal vooraan komt, en het hoogste getal achteraan, en alles ertussen oplopend. Het kan wellicht allemaal wat simpeler, maar het gaat mij erom dat deze code min of meer zo kan blijven en dan gewoon werken. Ik hoef uiteraard geen kant en klare antwoorden, maar wellicht een paar goede tips in de juiste richting.

Tot dusver had ik zelf inmiddels door dat er een probleem met de loop van bepaalKleinsteEnGrootste is, aangezien ik daar de eerste keer iets probeer te krijgen dat kleiner is dan 0, en dat kan uiteraard niet. Wellicht heeft iemand daar een idee over, hoe dat getackeld kan worden?

Alvast enorm bedankt!

C++:

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

const int MAX_LEN = 7 ;

void verwissel (int rij [], int i, int j){
    int t = rij[i] ;
    rij[i] = rij[j] ;
    rij[j] = t; 
}

void bepaalKleinsteEnGrootste(int rij[],int van,int tot,int &kl,int &gr){
    kl = van; 
    gr = tot; 
    for (int i = van; i < tot; i++) {           
        if (rij[i] < kl)
        kl = i;
        if (rij[i] > gr)
        gr = i ;
    }
}

void selectionSort (int rij [], int lengte, int &kl, int &gr){
    for (int x = 0; x < lengte; x++)
        cout << x << "=>" <<rij[x] << "; "; cout << "\n";

 // lengte/2+1 zodat de verwissel functies elkaar niet op gaan heffen..
    for (int i = 0; i < lengte/2+1; i++){ 
        bepaalKleinsteEnGrootste (rij,i,MAX_LEN-i,kl,gr) ;
        verwissel (rij, i, kl);
        verwissel (rij, MAX_LEN-i, gr);

// hier wil ik de gesorteerde rij laten zien..
        cout << "gesorteerd " << rij[i] << endl ;
    }
}

void  main(){
    int rij[MAX_LEN] = {3,4,2,7,1,6,5} ;
    int kl, gr;
    selectionSort (rij, MAX_LEN, kl, gr) ;
}

[De Cowboy]

Wil je bij

code:

if (rij[i] < kl)
       kl = i;
if (rij[i] > gr)
       gr = i ;

rij[i] niet met rij[kl] en rij[gr] vergelijken ?

[Tha Man]

Kerel, je hebt helemaal gelijk!!



Ik ben hier echt al uren mee bezig, en dan zie je dat soort stommiteiten niet (ik zeg niet dat ik het anders wel gezien had hoor )

Volgens mij moet ie het zo doen, zal 'm meteen even uitproberen..

alvast bedankt

[ATS]

Je hebt voor sorteren de grootste en de kleinste waarde helemaal niet nodig. Ik neem aan dat je alles zelf moet schrijven (anders gebruik je gewoon de sorteeralgoritmes uit de standaardlibrary). Een mogelijke manier is om de array gewoon net zo vaak langs te lopen tot je niet meer hoeft te verwisselen (bubblesort). Er zijn efficientere algoritmes, die kan je zo opzoeken met Google.

Wat je verder punten op zou kunnen leveren is als je het onafhankelijk kan maken van het type wat je erin stopt. Dat kan door templates te gebruiken. Je kan zo alles sorteren wat de < operator kent, en omdat het C++ is, kan je in principe elk object dat laten doen

Tenslotte: even je resultaat uitvoeren komt de geloofwaardigheid dat e.e.a. ook werkt natuurlijk wel ten goede

[Tha Man]

Hej, over je stukje:

De Cowboy schreef op woensdag 22 februari 2006 @ 23:21:
Wil je bij

code:

if (rij[i] < kl)
       kl = i;
if (rij[i] > gr)
       gr = i ;

rij[i] niet met rij[kl] en rij[gr] vergelijken ?

Helaas, volgens mij werkt het niet!

Ik krijg bij rij[i] < rij[kl] de volgende vergelijkingen:
3<3, daarna 4<3, daarna 2<3...die werkt dus, zo lijkt het.

de andere vergelijking, rij[i] > rij[gr], geeft echter:
3>1245120, 4>1245120, 2>1245120, 7>1245120, 1>1245120, 6>1245120, 5>1245120,
en dan ineens 4>5...wat er dus precies gebeurt snap ik zeker niet, maar het lijkt niet te kloppen.

[.oisyn]

Ik denk dat het handig is als je gewoon eens met de debugger kijkt of de waardes kloppen. Zo zal in de eerste iteratie van de 2e for-loop in je selectionSort functie de functie bepaalKleinsteEnGrootste aangeroepen worden met 'tot' = MAX_LEN. rij[MAX_LEN] bestaat natuurlijk niet, hij is maar MAX_LEN groot.

[Ivo]

Dat maakt volgens mij niks uit want

code:

for (int i = van; i < tot; i++)

er wordt maar tot en zonder 'tot' geloopt.

Edit: Oeps! In de loop staat 'gr = tot', dus rij[gr] valt buiten de grenzen.

[ Voor 29% gewijzigd door Ivo op 23-02-2006 09:32 ]

[farlane]

C++:

void bepaalKleinsteEnGrootste(int rij[],int van,int tot,int &kl,int &gr){

    kl = gr = van;

    for (int i = van; i < tot; i++)    {            
        if (rij[i] < rij[ kl ])
            kl = i;
        if (rij[i] > rij[ gr ])
            gr = i;
    }
}

[edit]
Oeps, die kl en gr moeten indices zijn , maar volgens mij is dit niet wat je probeert te bereiken

[ Voor 33% gewijzigd door farlane op 23-02-2006 11:34 ]

[Grijze Vos]

Waarom hou je het niet gewoon simpel?

Als je telkens alleen de kleinste zoekt, en die voorop in het nog-te-sorteren deel van het array zet, dan is je array gesorteerd als je te-sorteren deel lengte 0 heeft.

[.oisyn]

Waarom is wat hij nu doet dan zoveel moeilijker? Het enige wat anders is is dat hij dat ook met de grootste doet.

[farlane]

C++:

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

const int       MAX_LEN = 7;

void verwissel( int rij[], int i, int j )
{
    int t = rij[i];
    rij[i] = rij[j];
    rij[j] = t;
}

void bepaalKleinsteEnGrootste( int rij[], int van, int tot, int& kl, int& gr )
{
    kl = gr = van;
    for( int i = van; i < tot; ++i )
    {
        if( rij[i] < rij[ kl ] )
            kl = i;
        if( rij[i] > rij[ gr ] )
            gr = i;
    }
}

void selectionSort( int rij[], int lengte )
{
    int kl = 0, gr = 0;

    // lengte/2+1 zodat de verwissel functies elkaar niet op gaan heffen..
    for( int i = 0; i < lengte / 2 + 1; ++i )
    {
        bepaalKleinsteEnGrootste( rij, i, MAX_LEN - i, kl, gr );

        verwissel( rij, i, kl );
        verwissel( rij, MAX_LEN - i - 1, gr ); // !!
    }
}

void main( void )
{
    int rij[MAX_LEN] = { 3, 4, 2, 7, 1, 6, 5 };
    
    for( int x = 0; x < MAX_LEN; ++x )
        cout << x << "=>" << rij[x] << "; ";
    cout << "\n";

    selectionSort( rij, MAX_LEN );

    for( int x = 0; x < MAX_LEN; ++x )
        cout << x << "=>" << rij[x] << "; ";
    cout << "\n";

}

of

C++:

#include <iostream>
#include <algorithm>
void main( void )
{
    int rij[MAX_LEN] = { 3, 4, 2, 7, 1, 6, 5 };
    
    for( int x = 0; x < MAX_LEN; ++x )
        cout << x << "=>" << rij[x] << "; ";
    cout << "\n";

    std::sort( rij, rij + MAX_LEN );

    for( int x = 0; x < MAX_LEN; ++x )
        cout << x << "=>" << rij[x] << "; ";
    cout << "\n";

    std::cin.get();
}

[ Voor 87% gewijzigd door farlane op 23-02-2006 12:15 ]

[.oisyn]

Je main returnt geen int en je haalt cout niet uit std

[Tha Man]

Hoi, enorm bedankt iig voor alle reacties tot dusver. Het helpt echt een hoop met te begrijpen wat er allemaal met zo'n programma aan de hand kan zijn!

Volgens mij heeft de meeste impact de volgende aanpassing: kl = gr = van; (zie hieronder).
Nu wordt elke keer netjes hetzelfde getal voor beide vergelijkingen gebruikt, waarmee er geen vreemde getallen meer voorkomen zoals ik hierboven ergens beschreven had...

Ook kom ik nu netjes uit bij het middelste getal, wat ik zo graag wilde, zijnde 4, op rij[3].

[quote]farlane schreef op donderdag 23 februari 2006 @ 12:02:

C++:

void bepaalKleinsteEnGrootste( int rij[], int van, int tot, int& kl, int& gr ){
    kl = gr = van;
    for( int i = van; i < tot; ++i )    {
        if( rij[i] < rij[ kl ] )
            kl = i;
        if( rij[i] > rij[ gr ] )
            gr = i;
    }
}

void selectionSort( int rij[], int lengte ){
    int kl = 0, gr = 0;

    // lengte/2+1 zodat de verwissel functies elkaar niet op gaan heffen..
    for( int i = 0; i < lengte / 2 + 1; ++i )   {
        bepaalKleinsteEnGrootste( rij, i, MAX_LEN - i, kl, gr );

        verwissel( rij, i, kl );
        verwissel( rij, MAX_LEN - i - 1, gr ); // !!
    }
}

Echter, ik kom er ff niet achter wat de verandering

C++:

verwissel( rij, MAX_LEN - i - 1, gr ); // !!

nu precies doet

[ Voor 6% gewijzigd door Tha Man op 23-02-2006 13:40 ]

[.oisyn]

Dat heb ik in mijn eerste post in deze draad al uitgelegd. Als i == 0, dan is MAX_LEN-i dus gewoon MAX_LEN, maar rij[MAX_LEN] is geen geldige waarde. Het laatste element van de rij array is rij[MAX_LEN - 1]

[Tha Man]

Oh ja, natuurlijk. Met die -1 zorg je er dus voor dat er geen waarden worden opgevraagd die buiten de rij vallen..slim slim

Dank je wel, zal voortaan beter lezen