Bogosort

Info
Algorytm opisany w tym artykule jest bardzo słaby, właściwie to informatyczny żart. Nie nadaje się on do praktycznych zastosowań.
REKLAMA

Bogosort – bardzo słaby algorytm sortowania oparty na metodzie prób i błędów. Polega na ustawianiu elementów w losowej kolejności i sprawdzaniu, czy są posortowane. Średnia złożoność tego algorytmu jest rzędu silnia, a w przypadku pesymistycznym algorytm będzie działał w nieskończoność.

Algorytm występuje też w nieco ulepszonej wersji, w której nie sprawdza się wielokrotnie tego samego ustawienia. Wówczas algorytm daje gwarancję znalezienia rozwiązania, jednak jego złożoność czasowa nadal jest rzędu silnia (w przypadku pesymistycznym trzeba sprawdzić wszystkie permutacje zbioru).

Ze względu na bardzo dużą złożoność czasową bogosort nie nadaje się do praktycznych zastosowań. Istnieją proste w implementacji, a znacznie wydajniejsze algorytmy sortujące, np. sortowanie przez wstawianie.

Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 28 stycznia 2017 11:04
Ostatnia edycja: 11 stycznia 2018 13:49

REKLAMA
Polityka prywatnościKontakt