Weergegeven resultaten: 1 t/m 6 van 6
  1. #1
    Gevorderd   rommeke's schermafbeelding
    Geregistreerd
    10 May 2005
    Locatie
    cyberspace
    Berichten
    207
    Bedankjes
    40
    Bedankt
    65 keer in 37 posts

    Quick sort & tree sort

    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
    Laatst gewijzigd door rommeke; 1 May 2010 om 22:25

  2. De volgende gebruiker bedankt rommeke voor deze nuttige post:

    ultddave ( 1 May 2010)

  3. #2
    Administrator   ultddave's schermafbeelding
    Geregistreerd
    24 June 2006
    Locatie
    Genk
    Berichten
    1.492
    Bedankjes
    4.892
    Bedankt
    2.330 keer in 1.175 posts
    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
    Laatst gewijzigd door ultddave; 2 May 2010 om 00:02
    "Friendship. It's the hardest thing in the world to explain. It's not something you learn in school. But if you haven't learned the meaning of friendship, you really haven't learned anything." ~ Muhammad Ali

  4. De volgende gebruiker bedankt ultddave voor deze nuttige post:

    rommeke ( 2 May 2010)

  5. #3
    Administrator   ultddave's schermafbeelding
    Geregistreerd
    24 June 2006
    Locatie
    Genk
    Berichten
    1.492
    Bedankjes
    4.892
    Bedankt
    2.330 keer in 1.175 posts
    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
    "Friendship. It's the hardest thing in the world to explain. It's not something you learn in school. But if you haven't learned the meaning of friendship, you really haven't learned anything." ~ Muhammad Ali

  6. De volgende gebruiker bedankt ultddave voor deze nuttige post:

    rommeke ( 2 May 2010)

  7. #4
    Gevorderd   rommeke's schermafbeelding
    Geregistreerd
    10 May 2005
    Locatie
    cyberspace
    Berichten
    207
    Bedankjes
    40
    Bedankt
    65 keer in 37 posts
    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

  8. De volgende gebruiker bedankt rommeke voor deze nuttige post:

    ultddave ( 2 May 2010)

  9. #5
    Administrator   ultddave's schermafbeelding
    Geregistreerd
    24 June 2006
    Locatie
    Genk
    Berichten
    1.492
    Bedankjes
    4.892
    Bedankt
    2.330 keer in 1.175 posts
    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
    "Friendship. It's the hardest thing in the world to explain. It's not something you learn in school. But if you haven't learned the meaning of friendship, you really haven't learned anything." ~ Muhammad Ali

  10. #6
    Gevorderd   rommeke's schermafbeelding
    Geregistreerd
    10 May 2005
    Locatie
    cyberspace
    Berichten
    207
    Bedankjes
    40
    Bedankt
    65 keer in 37 posts
    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.

    Laatst gewijzigd door rommeke; 2 May 2010 om 15:44

  11. De volgende gebruiker bedankt rommeke voor deze nuttige post:

    ultddave ( 2 May 2010)

Discussie informatie

Users Browsing this Thread

Momenteel bekijken 1 gebruikers deze discussie. (0 leden en 1 gasten)

Soortgelijke discussies

  1. Quick Time
    Door narcis13 in forum Audiovisueel
    Reacties: 1
    Laatste bericht: 2 January 2007, 19:16

Favorieten/bladwijzers

Favorieten/bladwijzers

Regels voor berichten

  • Je mag geen nieuwe discussies starten
  • Je mag niet reageren op berichten
  • Je mag geen bijlagen versturen
  • Je mag niet je berichten bewerken
  •