Boguslajittelu

Boguslajittelu (bogosort) on hyvin hidas ja epävakaa lajittelualgoritmi. Sen pääperiaatteena on sekoittaa listaa kunnes se on oikeassa järjestyksessä, mikä 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
  }

Lajittelualgoritmit