[C++] sorteren op laatste getal

[GaveGozer]

Weet iemand hoe ik een reeks waardes kan laten sorteren op het laatste getal.
dus dat bijvoorbeeld
23454 voor 12456 komt
en 244433 weer voor alle 2 komt


het moet gedaan worden in C++ heeft iemand enig idee of er een funcitie voor is???

ik ben al aan het stoeien geweest met % 10(modulo dus)
dan neemt ie de rest waarde van een deling door 10, dus zeg maar het laatst cijfer.
maar als de lengte van de getallen verschilt dan gaat dat niet goed.

iemand een idee??

[gpex]

Moeilijk he die huiswerkopdrachten?

[Verwijderd]

Eerst een functie schrijven die het laatste karakter van een string (dus omzetten van number -> string lijkt me) eruit pikt en dan loslaten op je reeks?

[Klippy]

ff stringetje of getal omdraaien en sorteren, 't is niet zo moelijk

[GaMeOvEr]

Mja, dit moet in P&W maar ik ben bang dat je daar snel op een slotje getrakteerd gaat worden als ik dit topic zo bekijk...

Move SA -> P&W

[justmental]

Al je eerst het getal omzet naar een character type, dan kun je met string functies het laatste teken eraf knippen en die dan gebruiken voor de sortering.
_{Dit is meer iets voor [PW]}

edit:
ik typ traag

[Fvdlaar]

En hoe denk je dat je een getal omzet naar een string? Met div en mod misschien?

[RickN]

Ik zou denk ik eerst een bitmap van die getallen maken en dan een stukje beeldherkennings software schrijven die bitmap interpreteerd en dan met een neuraal netwerkje wat AI d'r inbouwen die dan verteld hoe je die getallen op volgorde van het laatste cijfer sorteert.

Ofzoiets.....

[Fvdlaar]

Da's een goede RickN, daar had ik nog niet aan gedacht

Maar ff serieus, de mod zou goed moeten gaan hoor. Misschien doe je wat anders fout?

[D2k]

ff een vriendelijk verzoek om ontopic te blijven
danku

_{titel gefixt}

[Verwijderd]

1. je zet je array van getalletjes om naar een array van strings
2. je keert die strings om met deze functie:

code:

char * _strrev (char *);

3. je vergelijkt het eerste karakter van elke string met de volgende eerste karakters van de strings eronder. Indien nodig, wissel je de 2 strings van plaats, en zo ga je verder tot het einde.

Zo zou ik het doen?

[Klippy]

Op dinsdag 19 februari 2002 15:38 schreef DiEana het volgende:
1. je zet je array van getalletjes om naar een array van strings
2. je keert die strings om met deze functie:

code:

char * _strrev (char *);

3. je vergelijkt het eerste karakter van elke string uit je nieuwe array met de strcmp functie

Zo zou ik het doen?

Ik ook denk ik

[Verwijderd]

Op dinsdag 19 februari 2002 15:39 schreef LiquidSilver het volgende:

[..]

Ik ook denk ik

Had wel eerst de strcmp functie gezegd (zie mijn edit), maar dat is beetje zinloos, omdat je toch met karakters zit (1ste karakter van de string namelijk) en daar kan je evengoed bijv. bla[i] < bla[j] op toepassen, ipv. de strcmp

[RickN]

Waar hebben we het nou over, sorteren van het eerste of van het laatste getal, I'm confused...

[EXX]

Een suggestie:

1. integers omzetten naar strings
2. strings inverteren (achterstevoren zetten, dus '12345' wordt '54321')
3. strings sorteren.
4. strings weer terug inverteren
5. strings weer terug omzetten naar integers.

edit:

DiEana was me voor

[Verwijderd]

Op dinsdag 19 februari 2002 15:41 schreef RickN het volgende:
Waar hebben we het nou over, sorteren van het eerste of van het laatste getal, I'm confused...

laatste getalletje, daarom dat we het ook gaan omkeren.

[Fvdlaar]

Da's wel leuk, maar als je een getal omzet naar een string, gebruik je ook mod, dus dan weet je gelijk het laatste cijfer.

23454 % 10 = 4
12456 % 10 = 6
244433 % 10 = 3

Dus volgens mij doet hij iets fout.

[GaveGozer]

Op dinsdag 19 februari 2002 15:25 schreef LiquidSilver het volgende:


ff stringetje of getal omdraaien en sorteren, 't is niet zo moelijk

dat mocht dus niet!! jammer he

[Verwijderd]

<edit>Weggehaald, het is intussen duidelijk</edit>

[GaveGozer]

Op dinsdag 19 februari 2002 15:38 schreef DiEana het volgende:
1. je zet je array van getalletjes om naar een array van strings
2. je keert die strings om met deze functie:

code:

char * _strrev (char *);

3. je vergelijkt het eerste karakter van elke string met de volgende eerste karakters van de strings eronder. Indien nodig, wissel je de 2 strings van plaats, en zo ga je verder tot het einde.

Zo zou ik het doen?

THANX!!

[GaveGozer]

Bedankt allemaal er zat idd iets verkeerd met de % 10

hij sorteerde alleen de laatste maar hij moest dan ook de een na laatste en die daarvoor enzo

ik heb er een loop van gemaakt die elke keer een getal eerder neemt en zo de juiste getallen sorteerd!

Thanx

[Orphix]

Ik vind een wrapper-class met een ge-overloade == en < operator toch mooier. Maargoed het werkt zo ook

[Verwijderd]

Op dinsdag 19 februari 2002 15:47 schreef GaveGozer het volgende:

[..]

THANX!!

yw

Vergeet niet bij het uitprinten (of als je het terug in je eerste array wilt stoppen), dat je de integers terug omkeert en dan weer naar een string zet, voor de duidelijkheid Maar als je zo ver geraakt bent, is dat een kleine moeite -> je kan de "keerOm" functie opnieuw gebruiken!

[GaveGozer]

hoe bedoel je een wrapper class ??!?!??

[Orphix]

Je stopt de integer waarde in een object. Deze objecten zet je bv in een vector. De standaard algoritme std::sort() kan dan (mits je de == en < operator overload hebt) deze objecten sorteren.
_{maar iets zegt me dat je hiermee niet bij je prof aan kan komen}

[GaveGozer]

ik zal het ook op die manier eens proberen

allemaal bedankt voor de info!

ik red me nu wel weer :-)

[Verwijderd]

Op dinsdag 19 februari 2002 15:52 schreef GaveGozer het volgende:
hoe bedoel je een wrapper class ??!?!??

Hij bedoelt het stukje STL code dat ik ondertussen al heb weggehaald. Overigens zijn function-objects (zoals die comparator uit mijn code) een fundament van "moderne" STL-based C++, je komt er maar met veel moeite en onelegant gestoei omheen. (Operators overloaden zodat < true geeft terwijl de programmeur false verwacht is sowieso verwarrend).

Het ging om deze code:

code:

#include <iostream>
#include <algorithm>
#include <iterator>

class IntReverseComparator {
public:
  bool operator () (int a, int b) const { return b < a; }
};

int tabel[] = { 3, 7, 2, 6, 8, 1, 4, 9, 5, 0 };

int main() {
  // sorteren
  std::sort(tabel, tabel + sizeof(tabel) / sizeof(tabel[0]),
        IntReverseComparator());

  // printen
  std::copy(tabel, tabel + sizeof(tabel) / sizeof(tabel[0]),
        std::ostream_iterator<int>(std::cout, "\n"));

  return 0;
}

[MSalters]

Op dinsdag 19 februari 2002 16:00 schreef mietje het volgende:

[..]

Hij bedoelt het stukje STL code dat ik ondertussen al heb weggehaald. Overigens zijn function-objects (zoals die comparator uit mijn code) een fundament van "moderne" STL-based C++, je komt er maar met veel moeite en onelegant gestoei omheen. (Operators overloaden zodat < true geeft terwijl de programmeur false verwacht is sowieso verwarrend).

En om die verwarring te voorkomen heb je dus de standaard comparision function-objects std::more<int> en std::less<int>. Zelf iets schrijven dat dat doet is idd verwarrend.

Overigens is het IIRC triviaal om een string om te keren:
[code]std::string keerom ( std::string const& str )
{
return std::string( str.rbegin(), str.rend() );
}

en als je die strings sort ( std::more<std::string> )
en vervolgens weer omdraait dan ben je er.

code:

  // uit m'n hoofd, niet gecompileerd
  std::vector<std::string> tabel;
  std::transform( tabel.begin(), tabel.end(),
            tabel.begin(),
            &keerom ) ;

[Olaf van der Spek]

Maar dan doe je veel meer werk dan nodig volgens mij. Een custom compare functie is efficienter.

[MSalters]

Op woensdag 20 februari 2002 14:07 schreef OlafvdSpek het volgende:
Maar dan doe je veel meer werk dan nodig volgens mij. Een custom compare functie is efficienter.

?
Het is huiswerk; dan meet je efficientie door te kijken hoeveel library code je kunt gebruiken ipv custom code.

[Korben]

Zucht. Het is misschien makkelijk om met bitwise AND te werken.

Omdat:
• String-conversie/vergelijking == traaaaaag
• Modulo == ook traag, maar al iets minder
• AND == fokking snel

Dus:

code:

getal & 0xa // 0xa == 10

Wat moeilijk zeg. Om daar nou meer dan vijf posts aan te besteden...

[.oisyn]

Op donderdag 21 februari 2002 13:36 schreef Xenophage het volgende:
Zucht. Het is misschien makkelijk om met bitwise AND te werken.

Omdat:
• String-conversie/vergelijking == traaaaaag
• Modulo == ook traag, maar al iets minder
• AND == fokking snel

Dus:

code:

getal & 0xa // 0xa == 10

Wat moeilijk zeg. Om daar nou meer dan vijf posts aan te besteden...

dat gaat dus niet werken
werken met de AND operator als modulo werkt alleen bij machten van 2 (logisch ook, aangezien je met AND kijkt naar de achterste bits. Je kunt niet kijken naar de achterste decimalen, omdat de computer de getallen niet opslaat in het decimale stelsel, maar in het binaire stelsel)

als voorbeeldje een aantal willekeurige getallen die je AND met 10:

code:

 5 & 10 =  0
13 & 10 =  8
18 & 10 =  2
24 & 10 =  8
26 & 10 = 10
33 & 10 =  0

okee, dan kun je natuurlijk zeggen: "ow wat stom, ik bedoelde natuurlijk met 9" (want bij machten van 2 and je ook met een_macht_van_2 - 1)

zelfde verhaal

code:

 5 & 9 = 1
13 & 9 = 9
18 & 9 = 0
24 & 9 = 8
26 & 9 = 8
33 & 9 = 1

[Korben]

Op donderdag 21 februari 2002 13:43 schreef OiSyN het volgende:

[..]

dat gaat dus niet werken
werken met de AND operator als modulo werkt alleen bij machten van 2 (logisch ook, aangezien je met AND kijkt naar de achterste bits. Je kunt niet kijken naar de achterste decimalen, omdat de computer de getallen niet opslaat in het decimale stelsel, maar in het binaire stelsel)

als voorbeeldje een aantal willekeurige getallen die je AND met 10:

code:

 5 & 10 =  0
13 & 10 =  8
18 & 10 =  2
24 & 10 =  8
26 & 10 = 10
33 & 10 =  0

okee, dan kun je natuurlijk zeggen: "ow wat stom, ik bedoelde natuurlijk met 9" (want bij machten van 2 and je ook met een_macht_van_2 - 1)

zelfde verhaal

code:

 5 & 9 = 1
13 & 9 = 9
18 & 9 = 0
24 & 9 = 8
26 & 9 = 8
33 & 9 = 1

Crap. Hoe erg ik het vind, xal toch moeten toegeven dat je gelijk hebt . Je kunt wel anden met F, dan is 8 & 0xf wél 8, maar 13 & 0xf óók. Niet de bedoeling. Dus modulo 10 is de enige redelijke optie.

[.oisyn]

Op donderdag 21 februari 2002 14:01 schreef Xenophage het volgende:

[..]

Crap. Hoe erg ik het vind, xal toch moeten toegeven dat je gelijk hebt . Je kunt wel anden met F, dan is 8 & 0xf wél 8, maar 13 & 0xf óók. Niet de bedoeling. Dus modulo 10 is de enige redelijke optie.

juist, maar als je AND met 0xf (15), dan bereken je modulo 16, en 16 is een macht van 2
Het werkt trouwens wel bij BCD strings (binary coded decimals), aangezien je dan per 4 bits een decimaal definieert, waardoor ANDen met 15 hetzelfde is als naar de achterste decimaal kijken, want 0xb t/m 0xf worden niet gebruikt

^{erg off-topic trouwens}

[Korben]

Op donderdag 21 februari 2002 14:05 schreef OiSyN het volgende:
^{erg off-topic trouwens}

Nogal. Niet dat deze post niet off-topic is...

[Verwijderd]

Ok, ik zat me te vervelen, dus hier een volledige oplossing:

code:

#include <strstream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <string>

template <class Type> std::string to_string(const Type& val)
  { std::ostrstream trans;
    trans << val;
    return std::string(trans.str());
  }

inline std::string revert_string(const std::string& orig)
#if 0
  { std::string ret;
    ret.resize(orig.size());
    std::reverse_copy(orig.begin(), orig.end(), ret.begin());
    return ret;
  }
#else
  { return std::string(orig.rbegin(), orig.rend()); }
#endif

const int invoer[]= { 13, 27, 42, 66, 78, 10, 84, 109, 75, 11 };

int main() {
  std::vector<std::string> tabel(sizeof(invoer) / sizeof(invoer[0]));

  // vul de vector met stringrepresentaties van de input tabel.
  std::transform(invoer, invoer + sizeof(invoer) / sizeof(invoer[0]),
             tabel.begin(), &to_string<int>);

  // keer de strings in de vector om.
  std::transform(tabel.begin(), tabel.end(), tabel.begin(), &revert_string);
  
  // sorteren.
  std::sort(tabel.begin(), tabel.end());

  // keer de strings in de vector opnieuw om.
  std::transform(tabel.begin(), tabel.end(), tabel.begin(), &revert_string);

  // printen.
  std::copy(tabel.begin(), tabel.end(),
        std::ostream_iterator<std::string>(std::cout, "\n"));

  return 0;
}

<edit>MSalters revert_string() is eleganter ;)</edit>

[_.Luke._]

Woehahaha...

Kom je niet uit de opdracht van DataStructuren op de HTS in Arnhem???

Daar hebben we nl dezelfde opdracht....;)

Luc

[Verwijderd]

Op dinsdag 19 februari 2002 15:25 schreef GaMeOvEr het volgende:
Mja, dit moet in P&W maar ik ben bang dat je daar snel op een slotje getrakteerd gaat worden als ik dit topic zo bekijk...

Move SA -> P&W

Hoezo dat dan?

[MSalters]

Op donderdag 21 februari 2002 15:21 schreef mietje het volgende:
Ok, ik zat me te vervelen, dus hier een volledige oplossing:

code:

{SNIP}

KLAP KLAP KLAP KLAP.

Da's een 9+

1/2 puntje aftrek voor ostrstream ipv ostringstream,
1/4 puntje aftrek voor string::resize & reverse_copy
ipv string::string( orig.rbegin(), orig.rend() )

[Verwijderd]

Op donderdag 21 februari 2002 17:18 schreef MSalters het volgende:
KLAP KLAP KLAP KLAP.

/me buigt

1/2 puntje aftrek voor ostrstream ipv ostringstream,

Tja, de meeste compilers zijn nog niet van de modernste STL met stringstream classes voorzien.

1/4 puntje aftrek voor string::resize & reverse_copy
ipv string::string( orig.rbegin(), orig.rend() )

Damn, you're right