Bogo排序是一種基於生成和測試範例的高效無效的排序功能。 該函式連續生成其輸入的排列，直到找到排序的排列。 它對於排序沒有用，但可以用於教育目的，以將其與更有效的算法進行對比。
存在兩個版本的函式：一個為確定性版本，它枚舉所有排列直到它遇到一個排序的，和一個隨機排列其輸入的隨機版本。 後一版本的工作類比是通過將甲板扔到空中，隨機挑選卡片並重複該過程直到甲板被分類來對一副紙牌進行分類。 它的名字來自偽造一詞.
基本介紹
- 中文名：Bogo排序
- 外文名：Bogosort
功能說明,運行時間和終止,相關算法,運行時間分析,
功能說明
以下是偽代碼中隨機函式的描述：
while not isInOrder(deck): shuffle(deck)
以下是在Python 3中重寫的上述偽代碼：
import randomdef 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)
當然，這假設數據是一個簡單的，可變的數據類型 - 就像Python的內置列表 - 其元素可以毫無問題地進行比較。
以下是標準ML中帶有shuffle的代碼示例：
val _ = load "Random"; load "Int"; val rng = Random.newgen (); fun select (y::xs, 0) = (y, xs) | 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;運行時間和終止
如果要排序的所有元素都是不同的，那么通過隨機化bogosort在平均情況下執行的預期比較次數漸近等效於（e-1）n！ ，平均情況下預期的掉期數等於（n-1）n！預期的交換數量比預期的比較數量增長得快，因為如果元素不按順序排列，通常只需要進行幾次比較就可以發現，無論有多少元素;但洗牌的工作與其規模成正比。在最壞的情況下，比較和交換的數量都是無界限的，原因與拋擲的硬幣可能連續多次翻起頭部的原因相同。
如果給定的列表已經排序，則會出現最好的情況;在這種情況下，預期的比較次數是n-1，並且根本不進行交換。
對於任何固定大小的集合，算法的預期運行時間是有限的，這與無限猴子定理所持有的原因大致相同：有一些獲得正確置換的機率，所以給定無限次數的嘗試，它幾乎肯定會最終被選中。
相關算法
1、Gorosort
2、Bogobogosort
3、Bozosort
4、Worstsort
運行時間分析
這裡有一些Python代碼可以有效地測試Bogosort的平均複雜度。
#!/usr/bin/env python3.6import sysimport timeimport randomfrom multiprocessing import Process, Queueimport numpy as npimport matplotlib.pyplot as pltfrom scipy.special import factorialfrom tqdm import tqdmWORKCOUNT = 8TRIALCOUNT = 10def 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() result = output.get() 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) fig, axarr = plt.subplots(2, 1, figsize=(8, 6)) 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 Trueclass 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 cause we gotta check all items for sorted if is_sorted(new_list): self.counts.put(self.count) self.output.put(new_list) break else: self.counts.put(self.count) breakif __name__ == '__main__': sys.exit(main())