Hier een overzicht van hoe de algoritmes volgens mij werken en wat er mis/goed aan is. (Je moet toch wat doen als je een paar daagjes thuis zit

).
Ik heb ze gesorteerd van slechts naar best (discussie is mogelijk).
De eerste drie werken met verwisselen van een gesorteerd array. Bij alle drie is het resulterende array niet goed random. Hiermee bedoel ik dat de kans dat een willekeurig gekozen nummer op een willekeurig gekozen plaats eindigt niet gelijk is voor alle nummers/plaatsen.
Tot deze categorie behoren:
shuffle8() B-Top ("randomness" is erg slecht)
shuffle1() RobIII / crisp
shuffle2() John_Smith / RobIII (snelste van de drie)
De tweede categorie werkt met "trial and error", d.w.z.: blijf random nummers of random plaatsen proberen en als het nummer al bestaat of de plaats al bezet is, genereer dan opnieuw een nummer, net zolang tot het array gevuld is. Deze algoritmes zorgen WEL voor een goed random resultaat, maar het nadeel is dat ze traag kunnen worden, vooral als het aantal nummers groot wordt.
Tot deze categorie behoren:
shuffle4() Clay
shuffle5() crisp (veel sneller dan 4)
De laatste categorie werkt door steeds een willekeurig element uit een gesorteerd array te halen, dit te verwijderen en in een "resultaat"-array te stoppen, dan wel een gesorteerd nummer steeds op een willekeurige plaats in een resultaat-array te inserten.
Tot deze categorie behoren:
shuffle3() Cheatah (werkt het traagst van de drie)
shuffle6() Cheatah / John Smith
shuffle7() John_Smith (werkt het snelst van allemaal)
**********************************************
Overzicht van alle algoritmes in bovengenoemde volgorde, de genoemde tijden zijn voor een array van 25 elementen (10.000 keer) en voor een array van 100 elementen (1000 keer). Benchmarks uitgevoerd door crisp.
shuffle8() B-Top
* start met geordend array
* sorteer met "random" sorteerfunctie. De sorteerfunctie vertelt of element A groter, kleiner of gelijk is aan element B (+1, 0 , -1). Door random +1, 0 of -1 te
geven, wordt er min of meer random "gesorteerd".
uniform verdeeld: nee
probleem: de kans dat een nummer dicht in de buurt vanzijn originele plaats eindigt is erg groot
tijd: 5.138/4.646
shuffle1() RobIII / crisp
* start met geordend array
* kies steeds 2 random elementen en verwissel, herhaal dit 2 * size maal
uniform verdeeld: nee
probleem: er is een redelijke kans dat een element nooit verwisseld wordt
tijd: 4.677/1.642
shuffle2() John_Smith / RobIII
* start met geordend array
* verwissel elk element met een random gekozen ander element
uniform verdeeld: nee
probleem: niet alle mogelijke verwisselingen komen even vaak voor
tijd: 1.993/0.912
shuffle4() Clay
* genereer steeds een random nummer in de juiste range
* als dit nummer al in het "resultaat" array zit, gooi hem weg en genereeer een nieuw nummer
* herhaal dit tot het array gevuld is
uniform verdeeld: ja
tijd: 30.414/61.098
probleem: vooral het vinden van de laatste nummers zal erg lang duren omdat er dan meestal een al bestaand nummer gegenereerd zal worden
shuffle5() crisp
* genereer steeds een random nummer in de juiste range
* als er op deze plaats al een nummer staat, ga dan een nieuw nummer genereren
* zo niet, zet dan het i-de nummer op deze plaats
Lijkt op shuffle4(), maar dan veel efficienter
uniform verdeeld: ja
tijd: 3.525/6.319
probleem: bij grote size zal dit algoritme ook traag worden
shuffle3() Cheatah
* start met geordend array
* kies steeds random een element uit dit array; verwijder dit uit het geordende array en stop het in een "resultaat"-array, herhaal dit tot het geordende array leeg is
uniform verdeeld: ja
tijd: 6.720/6.289
shuffle6() Cheatah / John Smith
* start met leeg "resultaat"-array
* genereer steeds een random nummer dat de grootte van het "resultaat"-array + 1 is
* "insert" het i-de nummer op het random gegenereerde plaatsnummer, herhaal tot array gevuld is
Lijkt op shuffle3(), maar nu wordt maar 1 array gebruikt
uniform verdeeld: ja
tijd: 3.725/3.475
shuffle7() John_Smith
* start met geordend array
* verdeel het array denkbeeldig in twee: het voorste deel bestaat uit nog niet gebruikte nummers, het achterste deel bestaat uit nummers in random volgorde
* kies steeds random een van de voorste nummers (dit groepje wordt steeds kleiner), verwissel dit random gekozen nummer met het eerste nummer van de
"achterkant". De voorkant is nu 1 kleiner geworden en de groep random nummers (achterkant) is 1 groter geworden. Ga door tot alle nummers naar achteren zijn gewerkt.
Lijkt op shuffle3(), maar efficienter omdat inserten/deleten niet nodig is.
uniform verdeeld: ja
tijd: 1.902/0.891
**************************************
Conclusie: de eerste drie algoritmes zijn niet aan te bevelen omdat ze niet goed werken. De volgende twee zijn niet aan te bevelen als "shuffle" algoritme, maar zijn wel zeer geschikt om een klein aantal unieke willekeurige nummers uit een groot aantal te kiezen. De laatste drie algoritmes werken goed en zijn efficient. De eerste van de laatste drie laat het duidelijkst zien hoe het werkt, de laatste is een aantal maal sneller dan de eerste.