Bogosort

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 15 maj 2021; kontroller kräver 5 redigeringar .

Bogosort  (från Amer. comp. slang. bogus - inoperable, non-functional, useless) är en ineffektiv sorteringsalgoritm som endast används för utbildningsändamål och i motsats till andra, mer realistiska algoritmer.

Om bogosort används för att sortera en kortlek måste du först i algoritmen kontrollera om alla kort är i ordning, och om de inte är det, blanda den slumpmässigt, kontrollera om alla kort nu är i ordning och upprepa processen tills däcket är sorterat.

Genomsnittlig körtid för algoritmen

När du itererar genom slingan en gång per sekund kan det i genomsnitt ta att sortera följande antal element:

Antal element ett 2 3 fyra 5 6 7 åtta 9 tio elva 12
Snittid 1 s 4 s 18 s 96 s 10 min 1,2 h 9,8 timmar 3,7 dagar 37,8 dagar 1,15 år 13,9 år 182 år gammal

Med en processor med 4 kärnor som körs på 2,4 GHz (9,6 miljarder operationer per sekund):

Antal element tio elva 12 13 fjorton femton 16 17 arton 19 tjugo
Snittid 0,0037 s 0,045 s 0,59 s 8,4 s 2,1 min 33,6 min 9,7 timmar 7,29 dagar 139 dagar 7,6 år 160 år

En kortlek med 32 kort kommer att sorteras av en dator i genomsnitt 2,7⋅10 19  år.

Implementeringsexempel

#inkludera <verktyg> bool korrekt ( int * arr , int storlek ) { medan ( -- storlek > 0 ) if ( arr [ storlek - 1 ] > arr [ storlek ]) returnera sant ; returnera falskt ; } void shuffle ( int * arr , int storlek ) { för ( int i = 0 ; i < storlek ; ++ i ) std :: swap ( arr [ i ], arr [( rand () % storlek )]); } void bogoSort ( int * arr , int storlek ) { medan ( korrekt ( arr , storlek )) blanda ( arr , storlek ); }

Se även

Länkar

 Sorteringsalgoritmer
Teori Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern
Utbyta
Val
Insatser
fusion
Inga jämförelser
hybrid
Övrig
opraktisk