[c] Vergelijken 1000 strings binnen array.

[Four]

Heren (dames),

Ik ben een beginnende programeur. Ik heb nu max 1000 tekens in een array staan, welk allen verweizen naar een string van max 1000 char's.

Ik wil deze sorteren op de lengte van de string.

Ik denk dat ik dit kan doen met ctrcmp of strlen.

Maar waar ik nou mee zit, als beginnende progger, is hoe kan ik het best 1000 mogelijkheden vergelijken? Het is nml goed mogelijk dat de waardes 10,3,6,8,7,9 zijn.

Ik begrijp nog niet hoe ik dit probleem te lijf moet gaan. Ik kan makkelijk zeggen
char* temp = array1[1] ; array1[1]=array1[2]; array1[2] = temp[1] Maar ik begrijp niet echt hoe ik de herhaling moet laten plaats vinden zonder de tel kwijt te raken.

Ik weet zeker dat hier truukjes voor zijn. Kan iemand me mischien een beetje op weg helpen? Ik zit al erg lang te bladeren en googlen maar ik kan het probleem nog niet aan.

mvg.

[Verwijderd]

Ik ben ook niet zo heel ver met programmeren, maar ken wel algoritmes waarmee je kunt sorteren..

Als je een array hebt met bijv. 100 elementen, dan kun je een tellertje (i) laten lopen van 0 tot 99, en telkens als het (i+1)de element groter is dan het i-de element, moet je die twee verwisselen. Hierna staat het grootste getal achteraan. Daarna laat je nog een tellertje lopen van 0 tot 98.. (weer hetzelfde verhaal), en zo krijg je de op een na grootste op de op een-na laatste plaats. (enzovoorts). Dit kun je het beste voor elkaar krijgen met een dubbele for-loop. (Deze methode heet ook wel de bubble-sort methode, omdat de grootste telkens 'boven komt drijven'. Hij is niet erg efficient, maar voor een beginnende programmeur goed te doen).

[Four]

Mooi idee. Moet werken! Waarom heb ik daar zelf niet aan gedacht Merci

[RobIII]

http://en.wikipedia.org/wiki/Quicksort bevat uitleg over Quicksort. Dit is sneller dan een lineaire sorteermethode (zoals je zelf voorstelt), maar toch nog begrijpelijk. Er zijn nog veel meer sorteeralgoritmes natuurlijk (ook nog snellere), maar die zijn allemaal vaak toepassingsafhankelijk. Enniewee, de link bevat ook voorbeeldcode in een hele bult programmeertalen, waaronder ook C. Lijkt me dat je daarmee een heel eind moet komen...

Kijk anders ook eens naar Buble sort, die vind ik vaak nog wat makkelijker te begrijpen. C code weer beschikbaar.

Bedenk wel dat deze voorbeelden arrays met integers sorteren op de waarde ervan, jij wil sorteren op de lengte. Je zult dus nog her en der wat moeten aanpassen.

[ Voor 38% gewijzigd door RobIII op 10-11-2004 19:10 ]

[Four]

Rob, ook bedankt. Ik moet er nu wel komen. Zat een beetje met die lus als probleem.

Gelukkig kennen jullie het probleem

[RobIII]

Four schreef op 10 november 2004 @ 19:18:
Gelukkig kennen jullie het probleem

Zo zijn wij ook begonnen
Vaak is het gewoon een kwestie van "het idee erachter" snappen, en dat omzetten in code. Je dient dan vaak wel goed te weten wat programmeertechnisch allemaal mogelijk is, dus je dient wel wat basiskennis te hebben (zoals for...next / do...loop / while..wend / repeat..until -lussen, if/then/else, variabelen, pointers, etc...)

Enniewee, ook wij zijn allemaal zo begonnen, en hebben allemaal wel eens een steuntje nodig gehad. Da's het mooie van GoT

In "mijn tijd" had ik alleen maar grijze boekjes en stond internet nog ergens bij het US Army in de luiers

[ Voor 73% gewijzigd door RobIII op 10-11-2004 19:23 ]

[Verwijderd]

Maar waar ik nou mee zit, als beginnende progger, is hoe kan ik het best 1000 mogelijkheden vergelijken? Het is nml goed mogelijk dat de waardes 10,3,6,8,7,9 zijn.

Als je waarden inderdaad 10,3,6,8,7,9 zijn (oftewel allemaal anders en tussen de 1 en de 1000) is een binsort het effectiefst. Maar dat verwacht ik niet.
Anders inderdaad een hypsort of quicksort. Bubble sort en vergelijkbare algoritmes zijn van Orde N^2, Quicksort/Hypsort, N* log (N) en Binsort werkt met orde N.

[RobIII]

En als je dan een Binsort en de post hierboven (@Jan-Klaasen: Hij's beginnende programmeur...) ook nog wil begrijpen, dan lees je http://ciips.ee.uwa.edu.a...ear2/PLDS210/binsort.html (waar onderaan de pagina zelfs een knop staat die mooi grafisch laat zien hoe een binsort werkt)

Meer routines (en geanimeerde voorbeelden) op http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/ds_ToC.html, onder "hoofdstuk 7"

...en ik neem aan dat Jan Klaasen met een hypsort een heapsort bedoelt

[ Voor 30% gewijzigd door RobIII op 10-11-2004 22:00 ]

[.oisyn]

Standaard C heeft ook gewoon een quicksort functie genaamd qsort ()

[Soultaker]

En ik blijf het zeggen: quicksort is O(N²) worst-case. Verder is het zogenaamde O(N) gedrag van binsort nogal misleidend. Het is helemaal geen algemeen sorteeralgoritme. Voor een algemeen soorteeralgoritme is O(N log N) bewezen minimaal. Simpele worst-case O(N log N) algoritmen zijn mergesort en heapsort, maar in de praktijk is quicksort ook prima geschikt, mits er een aantal hacks zijn toegepast om het worst-case gedrag te vermijden.

[ Voor 30% gewijzigd door Soultaker op 10-11-2004 22:26 ]

[Verwijderd]

Volgens mij heeft C zelf een eigen Quicksort functie. Dus hoef je alleen maar die functie aan te roepen.

[riezebosch]

Soultaker schreef op 10 november 2004 @ 22:25:
En ik blijf het zeggen: quicksort is O(N²) worst-case. Verder is het zogenaamde O(N) gedrag van binsort nogal misleidend. Het is helemaal geen algemeen sorteeralgoritme. Voor een algemeen soorteeralgoritme is O(N log N) bewezen minimaal. Simpele worst-case O(N log N) algoritmen zijn mergesort en heapsort, maar in de praktijk is quicksort ook prima geschikt, mits er een aantal hacks zijn toegepast om het worst-case gedrag te vermijden.

Ik had idd ooit in m'n quicksort controle ingebouwd in hoeverre de elementen van links en rechts niet al op volgorde lagen. De worst-case (in als de lijst al gesorteerd is) wordt dan een best-case van O(N). Wat dan precies de worst-case is, vind ik moeilijk te zeggen. Maar het gaat tenslotte ook om de gemiddelde snelheid. Natuurlijk is het ook een idee om cut-offs toe te passen, zodat je bij rijen van kleiner dan 3 een merge-sort toepast ofzo. Maar ik vind dat zelf minder elegant omdat je dan zelf vast moet stellen hoe groot die cut-off is, en je algoritme eigenlijk minder generiek (IMHO).

[Four]

RobIII schreef op 10 november 2004 @ 21:45:
Meer routines (en geanimeerde voorbeelden) op http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/ds_ToC.html, onder "hoofdstuk 7"

...en ik neem aan dat Jan Klaasen met een hypsort een heapsort bedoelt

Bedankt Ik ben inderdaad dusdanig noob dat ik hier nog een hele hoop aan heb

Soultaker schreef op 10 november 2004 @ 22:25:
En ik blijf het zeggen: .... worst-case gedrag te vermijden.

Hmmmm magic got it Ik vanaf hier gaat het topic boven me pet uit, maar ik zal het zeker proberen te begrijpen

Edit:
O(N2) O(N) Ik ben ZO noob

[ Voor 4% gewijzigd door Four op 10-11-2004 23:17 ]

[ThunderNet]

Valt wel mee hoe n00b je bent hoor
Ik wil niet weten hoe mijn eerste programma's er uit zaggen
(in QBasic / QuickBasic) vond het fantastisch om tekst op het beeld te krijgen, en later zelfs lijntjes.
En al doende leert men, en komt men steeds verder.

;-) En over een poosje leg jij weer moeilijke dingen uit aan nieuwe "n00bs"

[MSalters]

't is overigens niet handig om bij elke vergelijking weer opnieuw een strlen() te moeten doen. Jouw algoritme gebruikt zo'n 1000*1000 strlen's (alles met alles vergelijken), vandaar de O(N²) opmerking. Een beter algoritme als qsort hoeft maar iets van 1000*10 strlen's te doen, en dat heet dus O(N log N).
Met nog slimmere trucs doe je een keer een strlen, en hergebruik je dat resultaat.

[Verwijderd]

Four schreef op 10 november 2004 @ 23:15:
Bedankt Ik ben inderdaad dusdanig noob dat ik hier nog een hele hoop aan heb
...
Hmmmm magic got it Ik vanaf hier gaat het topic boven me pet uit, maar ik zal het zeker proberen te begrijpen
...
O(N2) O(N) Ik ben ZO noob

Da's niet erg hoor Wij hebben het ook allemaal moeten leren, eveneens met vallen en weer opstaan. Je moet maar één ding onthouden: succes is een kwestie van één keer meer opstaan dan vallen

Maar even iets anders. Als je nog niet (goed) vertrouwd bent met dit soort dingen, zou je kunnen overwegen om eens een boek te lezen over datastructuren en algoritmen. Zeker als je de intentie hebt om verder te doen met dit soort dingen, i.e. als dit niet een once-in-your-life project is. Daardoor leer je een aantal 'basis' datastructuren kennen (array, list in alle soorten, tree in allerlei soorten, stack, queue, etc) en een aantal basisalgoritmen (ik denk vooral aan zoek- en sorteeralgoritmen enzo). Het lijkt misschien overkill om nu meteen zo'n boek te gaan lezen, maar geloof me: het is een investering want die basisdingen komen steeds maar terug. En je hoeft het boek daarom niet noodzakelijk meteen tot de laatste letter uit te pluizen natuurlijk.
Ik heb destijds het boek "fundamentals of data structures in pascal" gelezen (omdat ik toen pascal heel goed kende en C/C++/Java nog niet) en daar heb ik nooit spijt van gehad Er is ook een C of zelfs C++ versie van dacht ik. Er zijn ongetwijfeld vele andere (en betere) boeken over het onderwerp. Je moet maar es op 'data structures' zoeken op amazon en je krijgt echt een hele hoop boeken naar je kop. Maar een goede inleiding kan al volstaan om een flinke sprong voorwaarts te maken. Ik wil je niet gelijk de hele serie 'The art of computer programming' van D.Knuth laten uitpluizen, want dat is bij momenten nogal zware kost kan ik uit ervaring zeggen Als je daaruit bvb deel 3 (searching and sorting) leest en helemaal begrepen hebt dan weet je wel iets over de algoritmen die hier de revue passeren

Het is maar een hint voor het geval je interesse hebt in dit soort materie

[Verwijderd]

RobIII schreef op 10 november 2004 @ 21:45:
En als je dan een Binsort en de post hierboven (@Jan-Klaasen: Hij's beginnende programmeur...) ook nog wil begrijpen, dan lees je http://ciips.ee.uwa.edu.a...ear2/PLDS210/binsort.html (waar onderaan de pagina zelfs een knop staat die mooi grafisch laat zien hoe een binsort werkt)

Tsja, er bestaat ook nog zoals als google. Zo moeilijk zou het niet moeten zijn om een omschrijving van het algoritme te vinden. Ik zie trouwens ook geen beschrijvingen van Quicksort. Maar ja, om een heapsort te vinden zou ik wel eens moeten leren spellen.

...en ik neem aan dat Jan Klaasen met een hypsort een heapsort bedoelt

Maar goed, eigenlijk denk ik dat een licht gemodificeerde variant van Binsort hier wel zou moeten werken. Er moet tenslotte enkel op lengte gesorteerd worden en die is beperkt tot max 1000. Door nu bins te maken die meer dan 1 object kunnen bevatten kan je alle objecten van dezelfde lengte in dezelfde bin kwijt.

En voor de mensen die nog niet weten hoe een bin sort werkt.
Stel je bent postbode en je staat voor een flatgebouw met een stapel brieven voor die flat. Noem elke brievenbus een bin. Pak brief 1 en stop die in de juiste bus, pak brief 2, enz. Simpel genoeg?

[Verwijderd]

Hier zie je een handol sorteeralgoritmes en zie je ook hoe ze werken:
http://cg.scs.carleton.ca/~morin/misc/sortalg/