Bogosort

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 15. maj 2021; checks kræver 5 redigeringer .

Bogosort  (fra Amer. comp. slang. bogus - inoperable, non-functional, useless) er en ineffektiv sorteringsalgoritme , der kun bruges til undervisningsformål og i modsætning til andre, mere realistiske algoritmer.

Hvis bogosort bruges til at sortere et sæt kort , så skal du først i algoritmen kontrollere, om alle kortene er i orden, og hvis de ikke er det, så bland det tilfældigt, tjek om alle kortene nu er i orden, og gentag processen, indtil dækket er sorteret.

Gennemsnitlig køretid for algoritmen

Når du gentager løkken en gang i sekundet, kan det i gennemsnit tage at sortere følgende antal elementer:

Antal elementer en 2 3 fire 5 6 7 otte 9 ti elleve 12
Gennemsnitlig tid 1 s 4 sek 18 sek 96 sek 10 min 1,2 t 9,8 timer 3,7 dage 37,8 dage 1,15 år 13,9 år 182 år gammel

Med en 4-core processor, der kører ved 2,4 GHz (9,6 milliarder operationer pr. sekund):

Antal elementer ti elleve 12 13 fjorten femten 16 17 atten 19 tyve
Gennemsnitlig tid 0,0037 s 0,045 s 0,59 s 8,4 sek 2,1 min 33,6 min 9,7 timer 7,29 dage 139 dage 7,6 år 160 år

Et spil med 32 kort vil blive sorteret af en computer i gennemsnit 2,7⋅10 19  år.

Implementeringseksempel

#inkluder <hjælpeprogram> bool korrekt ( int * arr , int størrelse ) { mens ( -- størrelse > 0 ) if ( arr [ størrelse - 1 ] > arr [ størrelse ]) returnere sandt ; returnere falsk ; } void shuffle ( int * arr , int størrelse ) { for ( int i = 0 ; i < størrelse ; ++ i ) std :: swap ( arr [ i ], arr [( rand () % størrelse )]); } void bogoSort ( int * arr , int størrelse ) { mens ( korrekt ( arr , størrelse )) blande ( arr , størrelse ); }

Se også

Links

 Sorteringsalgoritmer
Teori Kompleksitet O notation Ordreforhold Sorter typer bæredygtige Indre Ekstern
Udveksling
Valg
indsætter
fusion
Ingen sammenligninger
hybrid
Andet
upraktisk