词条 | Bogosort |
释义 |
|image = |class=Sorting |data=Array |time=Unbounded (randomized version),[1] {{math|O((n+1)!)}} (deterministic version) |average-time={{math|O((n+1)!)}}[1] |best-time={{math|O(n)}}[1] |space= |optimal=No }} In computer science, bogosort[1][1] (also known as permutation sort, stupid sort,[2] slowsort,[3] shotgun sort or monkey sort) is a highly ineffective sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one that is sorted. It is not useful for sorting, but may be used for educational purposes, to contrast it with more efficient algorithms. Two versions of this algorithm exist: a deterministic version that enumerates all permutations until it hits a sorted one,[1][3] and a randomized version that randomly permutes its input. An analogy for the working of the latter version is to sort a deck of cards by throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted. Its name is a portmanteau of the words bogus and sort.[4] Description of the algorithmThe following is a description of the randomized algorithm in pseudocode: '''while not''' isInOrder(deck): shuffle(deck) Here is the above pseudocode re-written in Python 3: import random def is_sorted(data): for i in range(len(data) - 1): if data[i] > data[i + 1]: return False return True def bogosort(data): while not is_sorted(data): random.shuffle(data) return data This code assumes that data is a simple, mutable datatype—like Python's built-in {{code|list}}—whose elements can be compared without issue. Here is an example with shuffle in Standard ML: val _ = load "Random"; load "Int"; val rng = Random.newgen (); | select (x::xs, i) = let val (y, xs') = select (xs, i-1) in (y, x::xs') end | select (_, i) = raise Fail ("Short by " ^ Int.toString i ^ " elements."); (* Recreates a list in random order by removing elements in random positions *) fun shuffle xs = let fun rtake [] _ = [] | rtake ys max = let val (y, ys') = select (ys, Random.range (0, max) rng) in y :: rtake ys' (max-1) end in rtake xs (length xs) end; fun bogosort xs comp = let fun isSorted (x::y::xs) comp = comp(x,y) <> GREATER andalso isSorted (y::xs) comp | isSorted _ comp = true; val a = ref xs; in while(not(isSorted (!a) comp)) do ( a := shuffle (!a) ); (!a) end; Running time and terminationIf all elements to be sorted are distinct, the expected number of comparisons performed in the average case by randomized bogosort is asymptotically equivalent to , and the expected number of swaps in the average case equals .[5] The expected number of swaps grows faster than the expected number of comparisons, because if the elements are not in order, this will usually be discovered after only a few comparisons, no matter how many elements there are; but the work of shuffling the collection is proportional to its size. In the worst case, the number of comparisons and swaps are both unbounded, for the same reason that a tossed coin might turn up heads any number of times in a row. The best case occurs if the list as given is already sorted; in this case the expected number of comparisons is , and no swaps at all are carried out.[5] For any collection of fixed size, the expected running time of the algorithm is finite for much the same reason that the infinite monkey theorem holds: there is some probability of getting the right permutation, so given an unbounded number of tries it will almost surely eventually be chosen. Related algorithms
Analysis of RuntimeHere is some Python code to efficiently test the average complexity of Bogosort.
import sys import time import random from multiprocessing import Process, Queue import numpy as np import matplotlib.pyplot as plt from scipy.special import factorial from tqdm import tqdm WORKCOUNT = 8 TRIALCOUNT = 10 def main(): listlengths = range(2, 10) times = [] for listlength in listlengths: print(listlength) trials = {'time': [], 'cycles': []} for trial in tqdm(range(TRIALCOUNT)): stime = time.time() array = random.sample(list(range(listlength)), k=listlength) workers = [] output = Queue() counts = Queue() for _ in range(WORKCOUNT): w = Sorter(array, output, counts) workers.append(w) w.start() total_count = 0 for _ in range(WORKCOUNT): total_count += counts.get() for _ in range(WORKCOUNT): output.put('DEATH') for w in workers: w.join() etime = time.time() trials['time'].append(etime - stime) trials['cycles'].append(total_count) times.append(trials) for i, (length, trial) in enumerate(zip(listlengths, times)): axarr[0].plot(np.ones(TRIALCOUNT) * length, np.log(trial['time']), 'rx', alpha=0.4) axarr[0].plot(listlengths, [np.log(sum(t['time']) / len(t['time'])) for t in times], label='Average Result') axarr[0].legend(loc=0) axarr[0].set_xlabel('Length of Initial List') axarr[0].set_ylabel('Average Time Elapsed - ln(seconds)') for i, (length, trial) in enumerate(zip(listlengths, times)): axarr[1].plot(np.ones(TRIALCOUNT) * length, np.log(trial['cycles']), 'rx', alpha=0.4) axarr[1].plot(listlengths, [np.log(sum(t['cycles']) / len(t['cycles'])) for t in times], label='Average Result') axarr[1].plot(listlengths, np.log([n * factorial(n) for n in listlengths]), label=r'$n \\cdot n!$') axarr[1].legend(loc=0) axarr[1].set_xlabel('Length of Initial List') axarr[1].set_ylabel('Average Time Elapsed - ln(Operations)') fig.suptitle('Parallel Bogosort') plt.tight_layout() plt.savefig('bogosort.png') def is_sorted(some_list): for x, y in zip(some_list[:-1], some_list[1:]): if x > y: return False return True class Sorter(Process): def __init__(self, array, output, counts, *args, **kwargs): super().__init__(*args, **kwargs) self.array = array self.length = len(array) self.output = output self.count = 0 self.counts = counts def run(self): while True: if self.output.empty(): new_list = random.sample(self.array, k=len(self.array)) self.count += self.length # not just one, we have to check all items if is_sorted(new_list): self.counts.put(self.count) self.output.put(new_list) break else: self.counts.put(self.count) break if __name__ == '__main__': See also
References1. ^1 {{citation | last1 = Kiselyov | first1 = Oleg | last2 = Shan | first2 = Chung-chieh | last3 = Friedman | first3 = Daniel P. | last4 = Sabry | first4 = Amr | contribution = Backtracking, interleaving, and terminating monad transformers: (functional pearl) | doi = 10.1145/1086365.1086390 | pages = 192–203 | series = SIGPLAN Notices | title = Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05) | url = http://www.dicta.org.uk/programming/LogicT.pdf | year = 2005}} 2. ^E. S. Raymond. "bogo-sort". The New Hacker’s Dictionary. MIT Press, 1996. 3. ^1 {{citation | last = Naish | first = Lee | contribution = Negation and quantifiers in NU-Prolog | doi = 10.1007/3-540-16492-8_111 | pages = 624–634 | publisher = Springer-Verlag | series = Lecture Notes in Computer Science | title = Proceedings of the Third International Conference on Logic Programming | volume = 225 | year = 1986}}. 4. ^{{cite web|title=Bogosort|url=http://www.catb.org/jargon/html/B/bogo-sort.html|work=The Jargon File 4.4.8|accessdate=11 April 2013|year=2003}} 5. ^1 2 3 4 5 6 {{citation | last1 = Gruber | first1 = H. | last2 = Holzer | first2 = M. | last3 = Ruepp | first3 = O. | contribution = Sorting the slow way: an analysis of perversely awful randomized sorting algorithms | doi = 10.1007/978-3-540-72914-3_17 | pages = 183–197 | publisher = Springer-Verlag | series = Lecture Notes in Computer Science | title = 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007 | url = http://www.hermann-gruber.com/pdf/fun07-final.pdf | volume = 4475}}. 6. ^[https://code.google.com/codejam/contest/dashboard?c=975485#s=p3 Google Code Jam 2011, Qualification Rounds, Problem D] 7. ^Bogobogosort 8. ^https://www.arxiv.org/abs/1406.1077 External links{{wikibooks|Algorithm Implementation|Sorting/Bogosort|Bogosort}}
3 : Sorting algorithms|Comparison sorts|Computer humor |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。