Results 1 to 9 of 9

Thread: Sorting Out Sorting - The Movie

  1. #1

    Sorting Out Sorting - The Movie

    Visuele uitleg over een negental sorteeralgoritmes.

    http://video.google.com/videoplay?do...47752111188923

    Voor wie een halfuurtje niets te doen heeft. :-)
    1+1=b

  2. #2
    John Kuiper
    Join Date
    Apr 2007
    Location
    Almere
    Posts
    8,747
    Nou, dat half uurtje werd 15 minuten. Toch wel leuk om te zien dat deze algoritmes nog steeds in de huidige tijd gebruikt worden. Wat is die tree snel.
    Voor kleine sortering maak ik nog steeds gebruik van bubblesort. Maar dan spreken we van 100 items? Met de huidige computer zo gebeurd.
    Delphi is great. Lazarus is more powerfull

  3. #3
    mov rax,marcov; push rax marcov's Avatar
    Join Date
    Apr 2004
    Location
    Ehv, Nl
    Posts
    10,357
    Tsja, maar dat kost wel centen. In een huidige computer (itt tot ouwe machines) gebruikt een rekenende computer meer stroom dan een niet rekende.

    Denk een beetje groen :-)

    De URL is overigens erg leuk, afgezien van de erg valse audio. Ik kijk hem af.

    Praktisch gezien kopieer ik meestal een heapsort rond. Minder kans op fouten dan steeds vanaf 0 implementeren (en de heapsort is sneller voor al gesorteerde data, wat een scenario is wat vaak voorkomt, toevoegen van een paar items aan een al gesorteerde set)
    Last edited by marcov; 02-Jan-11 at 19:42.

  4. #4
    Is die heapsort daar ook sneller dan de dual-pivot quicksort?

  5. #5
    mov rax,marcov; push rax marcov's Avatar
    Join Date
    Apr 2004
    Location
    Ehv, Nl
    Posts
    10,357
    Geen idee. De beslissing is gebaseerdop een zeer oude test in 16-bit tijden zelfs, dus het kan best dat de tradeoffs tegenwoordig anders zijn. (b.v. vanwege andere compare vs swap tradeoffs).

    Maar och, nooit echt problemen mee gehad. Als sorteer performance een probleem is, ga je tenslotte toch meestal naar een situatie toe waar je de datastructuren ordered bijhoudt. Een 10-30% verandering van sorteer algoritme red je dan meestal ook niet meer, dus ik heb het nooit opnieuw getest.

  6. #6
    Een van de dingen waarvan ik inderdaad begrepen heb die echt anders zijn tegenwoordig is dat vaak (niet als je integers vergelijkt) de compare functie meestal domineert over de swap. Tenzij je complete objecten, ipv de pointers ernaar verwisselt.

    Ik zou ook gokken dat de huidige caching het heel veel belangrijker maakt om bij een quicksort de kleine subarrays niet (recursief) te quicksorten. Maar getest heb ik het allemaal nog niet

  7. #7
    Wat gebruikt de functie sort in bijvoorbeeld een listbox voor een algoritme, weet iemand dat ?
    En zou dat nog te optimaliseren zijn ?

  8. #8
    Dat is een beetje rotte implementatie van een quicksort, vziw. Eentje die je O(n^2) geheugen en tijd kunt laten gebruiken. Maar voordat je daar last van hebt moet je er wel meer dan 10K elementen in stoppen, denk ik.

  9. #9
    mov rax,marcov; push rax marcov's Avatar
    Join Date
    Apr 2004
    Location
    Ehv, Nl
    Posts
    10,357
    Quote Originally Posted by StephanEggermon View Post
    Ik zou ook gokken dat de huidige caching het heel veel belangrijker maakt om bij een quicksort de kleine subarrays niet (recursief) te quicksorten. Maar getest heb ik het allemaal nog niet
    Het grappige is dat bovenstaande antieke video beide dingen noemt (dus dat compare/swap tradeoffs kunnen verschillen, en dat je kleine subarrays beter met bubble sort kan doen).

    Niks nieuws onder de zon dus. Alleen blijven denken en experimenteren.

    (IMHO wordt het tijd een "experimentele IT" opleiding op te zetten)

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •