/home/wijet

Znalazłem trochę informacji w sieci, pierwszy sposób to Bogosort, algorytm bardzo prosty można przedstawić na przykładzie sortowania tali kart
tasujemy karty sprawdzamy czy są posortowane jeśli nie tasujemy jeszcze raz i tak aż do momentu kiedy talia będzie posortowana. Pesymistyczna złożoności obliczeniowa to O(n*n!), korzystamy z losowych permutacji zbioru co powoduje ze możemy nigdy nie otrzymać posortowanego zbioru. W najlepszym przypadku możemy otrzymać posortowany zbiór po jednym losowaniu permutacji zbioru.

Podobnym algorytmem sortowania do Bogosort jest Bozo sort, także opiera się na losowych permutacjach zbioru. Sprawdzamy czy zbiór jest posortowana jeśli nie wybieramy dwa losowe elementy zbioru i zamieniamy ze sobą i znowu sprawdzamy czy zbiór jest posortowany.
Oba algorytmy są wysoce nieefektywne, i raczej nie przydadzą sie w jakich kolwiek zastosowaniach. W wolnej chwili w ramach ćwiczenia rubiego napisałem kawałeczek kodu realizującego te dwa algorytmy.

class Array
  def bogosort!
    shake until is_sorted?
    self
  end
 
  def bozosort!
    until is_sorted?
      a = rand(size-1)
      b = rand(size-1)
      self[a], self[b] = self[b], self[a]
    end
    self
  end
 
  def is_sorted?
    for i in 0..size-2
      if self[i] > self[i+1]
        return false
      end
    end
    true
  end
 
  def shake
    for i in 0..size-1
      a = rand(size-1)
      self[i], self[a] = self[a], self[i]
    end
    self
  end
 
end