Boguslajittelu

Kohteesta Wikipedia
Loikkaa: valikkoon, hakuun

Boguslajittelu (bogosort) on hyvin hidas ja epävakaa lajittelualgoritmi. Sen pääperiaatteena on sekoittaa listaa kunnes se on oikeassa järjestyksessä, joka vastaa korttipakan heittämistä ilmaan ja korttien keräämistä maasta yksi kerrallaan kunnes satut keräämään kortit oikeassa järjestyksessä.

Boguslajittelun suoritusaika on keskimäärin O(n * n!), parhaimmillaan θ(n) ja pahimmillaan Ω(∞) (suoritus ei pääty koskaan).

Pseudokoodi boguslajittelulle menisi näin:

 bogusLajittelu(lista) {
   while (!järjestyksessä(lista))      // 'järjestyksessä' on funktio, joka palauttaa totuusarvon riippuen siitä onko lista oikeassa järjestyksessä vai ei
     sekoita(lista)                    // 'sekoita' sekoittaa listan kaikki alkiot
 }