- Vergeleken
- Gemarkeerd (kleinste, pivot of sleutel)
- Verwisseld of verplaatst
- Op zijn plek
| Plaats | Sortering | Vergelijkingen of leesacties | Verwisselingen of verplaatsingen | Operaties |
|---|
Sorteerrace
Welk sorteeralgoritme is het snelst? Dat hangt af van de lijst. Sorteerrace laat alle acht sorteeralgoritmen tegelijk op dezelfde lijst lopen, elk in een eigen baan, en telt elke vergelijking, leesactie, verwisseling en verplaatsing als één operatie. De banen gaan verder naarmate hun telling oploopt, dus je ziet de efficiënte sorteringen finishen terwijl de trage nog aan het verwisselen zijn, en je ziet de volgorde veranderen als de lijst bijna gesorteerd of omgekeerd is. Druk op Afspelen om alle acht sorteeralgoritmen op dezelfde lijst te zien racen, of gebruik Stap en Terug om per operatie te gaan. Sleep de schuif om ergens naartoe te springen. Elke vergelijking, leesactie, verwisseling of verplaatsing telt als één operatie, en elke baan gaat verder naarmate haar eigen telling oploopt, dus de sortering die de minste operaties nodig heeft, is als eerste klaar. Kies hoeveel staven en hoe ze beginnen, of typ je eigen getallen. Als het bord geselecteerd is, zetten de pijltjestoetsen een stap, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het eind.
Hoe het werkt
- Kies hoeveel staven en hoe ze beginnen: willekeurig, bijna gesorteerd, omgekeerd of met weinig unieke waarden. Of typ je eigen getallen.
- Druk op Afspelen en kijk naar de acht banen. Stap en Terug gaan één operatie per keer; de schuif springt naar elk punt in de race.
- Vergelijk de resultatentabel en probeer daarna een bijna gesorteerde en een omgekeerde lijst om de ranglijst te zien veranderen.
Hoe de race werkt
Alle acht sorteringen krijgen dezelfde lijst. Elke vergelijking van twee waarden, elk cijfer of elke waarde die radix sort en counting sort lezen, en elke verwisseling of verplaatsing telt als één operatie. Op elk moment van de race toont elke baan hoe ver haar sortering is met dat aantal operaties. Een sortering die minder operaties nodig heeft, is eerder bij het eind. De resultatentabel toont voor elke sortering de vergelijkingen, de verwisselingen of verplaatsingen, en het totaal.
Wat de resultaten laten zien
Bij 40 willekeurige waarden heeft counting sort ongeveer 120 operaties nodig, radix sort ongeveer 240, quicksort ongeveer 260 en mergesort ongeveer 380. Heapsort volgt met ongeveer 490, terwijl selection sort en insertion sort ongeveer 820 nodig hebben en bubblesort meer dan 1.100. Bij een bijna gesorteerde lijst wint insertion sort met ongeveer 50, en bubblesort wordt tweede. Bij een omgekeerde lijst hebben bubblesort en insertion sort allebei 1.560 nodig. Counting sort en radix sort winnen zo vaak omdat deze waarden kleine gehele getallen zijn; bij andere gegevens zijn ze helemaal niet te gebruiken.
Veelgestelde vragen
Welk sorteeralgoritme is het snelst?
Dat hangt af van de gegevens. Voor kleine gehele getallen hebben counting sort en radix sort de minste operaties nodig. Voor algemene gegevens zijn quicksort en mergesort het snelst op willekeurige lijsten, en insertion sort op lijsten die bijna gesorteerd zijn. Bubblesort en selection sort zijn traag, behalve op de kleinste lijsten.
Wat telt als een operatie?
Elke vergelijking van twee waarden, elk cijfer of elke waarde die radix sort en counting sort lezen, en elke verwisseling of verplaatsing van een waarde. Het is een eenvoudig model: echte looptijden hangen ook af van geheugentoegang en de kosten van elke operatie.
Waarom winnen counting sort en radix sort zo vaak?
Omdat ze nooit waarden vergelijken. Ze maken gebruik van het feit dat de waarden kleine gehele getallen zijn, dus hun werk groeit met n plus het bereik van de waarden, niet met n log n. Voor gegevens die niet uit kleine gehele getallen bestaan, zijn ze niet bruikbaar.
Waarom wint insertion sort bij een bijna gesorteerde lijst?
Omdat het werk gelijk is aan het aantal waarden plus het aantal paren in de verkeerde volgorde. Een bijna gesorteerde lijst heeft heel weinig van zulke paren, dus elke waarde schuift maar een plek of twee op.
Worden mijn getallen ergens naartoe gestuurd?
Nee. De race draait in je browser, en je laatste instellingen blijven in de lokale opslag van deze browser.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor