Quick sort & tree sort

[rommeke]

Yo minaticaleden

Ik ben bezig met wat sorteeralgoritmen ana het bekijken waaronder quicksort
hieronder al je je me bevindsel vinden het probleem is dat ik volgens geen plaats mee rheb om te swappen

Het volgende probleem is zouw er iemand zo braaf willen zijn om tree sort uit te leggen en als er een praktisch voorbeeld bij zou dat echt zijn.

----

Quicksort
Het quicksort-algoritme is doorgaans de beste keuze voor een intern sorteeralgoritme. Zoals de naam aangeeft, is dit het snelste gekende sorteeralgoritme. De gemiddelde uitvoeringstijd is O(n log n)en de slechts mogelijke uitvoeringstijd is O(n²), maar de kans dat dit slechtste geval zich voordoet kan zeer klein gemaakt worden.
De basis van quicksort is een recursief algoritme, dat steunt op het partioneren van de te sorteren rij. Een willekeurig element s uit de rij wordt gekozen; dit element wordt de spil (of pivot) genoemd. Vervolgens wordt de rij opgesplitst in twee deelrijen, nl. een deelrij met elementen kleiner dan de spil en een deelrij met elementen groter dan de spil. Deze twee deelrijen worden dan recursief gesorteerd, en aangeschakeld tot de uiteindelijke gesorteerde rij
Kies een pivot element: random (best om een element is het midden te kiezen)




Ik heb dus volgens mij geen plaats meer op 73 te swappen .
Mss lijk het wel wat raar om het zo eens manueel uit te rekenen maar zou kan je echt zien of je het algoritme verstaat of niet :d

[ultddave]

Hetgeen je al hebt is goed.

Maar er staat toch nergens dat je moet stoppen met swappen zodra je de pivot bereikt hebt.

De rechter pointer gaat nu staan op "17" en de linker op "73".

5 3 1 73 11 17 69 75 34 86


Die worden dan ook geswapped. Dus krijg je:

5 3 1 17 11 73 69 75 34 86

En dan schuift de rechter pointer op en de linker pointer op. En staan ze allebei op 11.

5 3 1 17 11 73 69 75 34 86

En aangezien "11 <= pivot" zal de linkerpointer nog eens naar rechts gaan. De rechterpointer blijft.

5 3 1 17 11 73 69 75 34 86

Op het moment dat beide pointers elkaar voorbij zijn gestoken stopt het algoritme.

De rechterpointer die op 11 staat, duidt het einde van het eerste deel aan.
Het eerste deel bevat dus: 5 3 1 17 en 11. Die zijn allemaal kleiner of gelijk aan de pivot.
De linkerpointer die op 73 staat, duidt het begin van het tweedde deel aan.
Het tweedde deel bevat dus: 73 69 75 34 en 86. Die zijn allemaal groter dan de pivot.

En dan moet je dus weeral quicksort toepassen op die 2 delen afzonderlijk. En zo doorgaan en dus steeds blijven opsplitsen totdat er maar 1 element overblijft in elke 'lijst'.

Als je die dan terug in 1 lijst zet, zijn ze gesorteerd.

Tree Sort heb ik zelf niet gezien, dus daar kan ik je niet direct een duidelijke uitleg over geven.

Heel kort antwoord op je probleem is dus:
- De pivot mag zelf ook verplaatst worden.

Succes.

Mvg,
Dave

[ultddave]

Aangezien ik mijn vorig bericht niet meer kon editeren heb ik maar een nieuwe geplaatst .

Ik denk dat ik in de toekomst (grote vakantie waarschijnlijk) eens een Nederlandstalige uitleg ga schrijven over sorteeralgoritmen en die dan op mijn website plaatsen. Tegen dan, zal ik die tree view wel eens hebben bekeken alleszins . Desnoods kan ik eventueel zo een duidelijk overzicht geven van alle algoritme en hun tijdscomplexiteit (best, average en worst case), of iets dergelijks.

PS: Als je aan het zoeken bent naar snelle algoritmes voor te sorteren raad ik Quicksort aan, en Heapsort. Beide zijn goede sorteeralgoritme, maar profiteren vooral van hun snelheidswinst (ten opzichte van andere algoritmes) bij grote lijsten die gesorteerd moeten worden.

Mvg,
Dave

[rommeke]

Hmm thnx voor de hint, als je hulp nodig hebt met de opmaak van je website ivm met technische kant van de sorteeralgoritmen wil ik wel helpen . Op codegearguru.com staan er een paar instructiefilmpjes ivm met sorteeralgoritmen eventueel eens bekijken voor op te frissen. Daarnaast wil ik ook opmerken dat quicksort inderdaad de snelste is als je hoog aantal gegevens wilt sorteren maar voor een tabel tussen de 5 en 20 zal selectionsort quicksort toch inhalen

[ultddave]

Bedankt . Ik zal er aan denken.

Yep voor kleine lijsten gebruik ik meestal een algoritme zoals selectionsort of bubblesort.

Mergesort voor grote lijsten is ook wel goed als je de 2 delen van de lijst op 2 apparte processoren kan uitvoeren. Dan gaat het ook heel snel . Het nadeel is wel dat zoiets implementeren wat tijd in beslag neemt. ^^

Mvg,
Dave

[rommeke]

phoh ge zou er ook countsort op kunnen smijten op een kleine tabel. Vermijt echt bubbelesort want is echt zo zwak algoritme als je daar mee afkomt denk ik dat je programmeer leerkracht je gaat aanvallen met een kruisbeeld of een instant hartattack zal krijgen

Ik heb je je op je hotmail acount die vermeld staat in je profiel gespamt met me verder uitwerking van quicksort omdat ik het forum nie wil volflikkeren.

Swat ik heb ondertussen eens tree sort uitgevogeld

Alsook als je het niet door had is dit een voorbereiding op de wel gevreesde examentjes.
Dus ik denk wel dat je dan eventuele me notes kan gebruiken voor je websitejeuh --> information should be free for everbidy after all (if it is not top secret or privacy).

Wat implementatie betreft kan je wel wat code vinden op net jammer genoeg zijn het meestal van die mensen die geen defitge variabele namen gebruiken. Waardoor je het amper zelf verstaat.