sciencetalk

Voor school moeten een radix sort implementeren voor unsigned ints. Het komt er op neer bij radix sort dat je de getallen gaat opdelen in groepen volgens een bepaalde radix (bij radix 10 zou je dus groepen maken van getallen die beginnen met 0, 1, 2, ... 9). Daarna zou je elk van deze groepen opnieuw bekijken en daar opnieuw die regel op toepassen om zo de volgende groep te maken, ... (tot daar mijn korte uitleg over radix sort).

Nu bestaat een unsigned int in c++ uit 4 bytes. Ik gebruik nu elke byte om op te delen in groepen. Voor de meeste beduidende byte krijgen we dus radix = 256. We gaan de elementen dus opdelen in groepen van 256. Wanneer ik dit nu doe voor een tabel van 10 elementen is de kans groot dat alle elementen in een aparte groep belanden (wat ook zo is), als we nu de groepen in juiste volgorde sorteren kunnen we enkel uit de hoogste byte al de juiste volgorde halen. (Zo kan je de getallen 3454,4333,1222 ook sorteren door alleen naar de eerste getallen te kijken vermits de 3 getallen in een andere groep zouden belanden).

Goed, alle getallen zitten in een aparte groep, de groepen worden correct gesorteerd, maar tot mijn verbazing zijn de getallen zelf niet gesorteerd!

Klein voorbeeldje:
Iemand die een verklaring kan geven waarom ik die groepen krijg voor die getallen?

Ik denk dat ik zelf al een stukje verder ben. Blijkbaar geeft rand() allemaal waarden terug die gaan tot max 2^15 (een signed int van 16 bits). Hoe krijg ik random unsigned int's van 32 bit?

Simpel:

eerst vul je de eerste twee bytes in met je random en dan de volgende twee bytes met een nieuwe random.

wel ervan uitgaan dat 4 bytes uit 32 bits bestaat:

0..65535 en dan nog eens 0..65535

Goed, alle getallen zitten in een aparte groep, de groepen worden correct gesorteerd, maar tot mijn verbazing zijn de getallen zelf niet gesorteerd!

Waarom verwacht je dat de 'least significant byte' iets zegt over de uiteindelijke positie van het totale getal?

Stel dat je 124 en 39 gaat sorteren (radix = 10). Je begint dan met 4 en 9 te sorteren. Deze staan al in de juiste volgorde dus je doet niks. Dit betekent logischer wijs dat de getallen nog steeds in de verkeerde volgorde staan. Bij de volgende stap vergelijk je 2 en 3. Wederom doe je niks. Daarna vergelijk je 1 en 0. Nu draai je 124 en 39 om om op de juiste volgorde te komen.

Waarom verwacht je dat de 'least significant byte' iets zegt over de uiteindelijke positie van het totale getal?

Dat doe ik ook niet, ik sprak wel degelijk over de meeste significante byte.

Je moet het dan zien als je 124 en 039 gaat sorteren, eerst vergelijk je 0 en 1, 039 zal dus voor 124 komen. Vermits beiden in een andere deelgroep zitten kan je stoppen met vergelijken van de volgende getallen.

Maar het probleem waarom mijn code niet werkt is omdat ik vermoed dat c++ daar zelf int's heeft ingestoken die ik uit de rand() heb gehaald, ipv unsigned int's die ik wil. Hierdoor zijn de 2 meest significante bytes niet ingevuld geweest vermoed ik waardoor die geen betekenis hebben in dit geval.

Schwartz schreef:Simpel:

eerst vul je de eerste twee bytes in met je random en dan de volgende twee bytes met een nieuwe random.

wel ervan uitgaan dat 4 bytes uit 32 bits bestaat:

0..65535 en dan nog eens 0..65535

En hoe vul ik 1 unsigned integer met 2 16 int getallen?

Ok het probleem is opgelost. Blijkbaar worden de bytes opgeslagen van minst significant naar meest significant, waardoor ik eerst moet groeperen op de laatste byte en niet op de eerste. Waarom ze dit op deze manier opslaan is mij een raadsel, maar het probleem is dus wel opgelost

Waarom ze dit op deze manier opslaan is mij een raadsel, maar het probleem is dus wel opgelost

Endianness.

Ik overigens benieuwd hoe jij de 4 bytes uit je int haalt.

Ik ben overigens benieuwd hoe jij de 4 bytes uit je int haalt.

p is nu een pointer naar de eerste byte, de 2de byte is dan natuurlijk p+1 enzovoort. Indien je het ding wil afdrukken in een cout o.i.d. moet je het wel terugcasten naar een int.

Dat is mijn inziens niet echt netjes (en bovendien introduceer je op deze manier machineafhankelijkheid).

Je had mijn inziens beter iets in de volgende trant kunnen doen:

Die code was gegeven door een docent. Sowieso ben je toch afhankelijk van je systeem als ik die endianness goed versta.

Het is ook de bedoeling om die radix sort meer algemeen te maken zodat het ook strings e.d. kan gaan sorteren en dan is het makkelijker om met een pointer systeem te gaan werken om zo algemeen mogelijk te blijven.

Sowieso ben je toch afhankelijk van je systeem als ik die endianness goed versta.

Nee, dat is niet zo. Als je namelijk met bijvoorbeeld (i & 0xFF) de onderste 8 bits van je integer bekijkt, krijg je altijd het least significant byte. Dit is onafhankelijk van endianness.

Het is ook de bedoeling om die radix sort meer algemeen te maken zodat het ook strings e.d. kan gaan sorteren en dan is het makkelijker om met een pointer systeem te gaan werken om zo algemeen mogelijk te blijven.

Daar ben ik het wel mee eens, maar ik denk dat je dit alleen kunt doen als je ook methodes levert waarmee je dan garandeert dat de strings/integers/whatever op die manier worden uitgelezen zodat ze juist gesorteerd gaan worden.