Bogo排序
無效的排序算法,它會連續生成其輸入的排列,直到找到要排序的輸入
在計算機科學中,Bogo排序(英語:Bogosort)是個非常低效率的排序演算法,通常用在教學或測試。其原理等同將一堆卡片拋起,落在桌上後檢查卡片是否已整齊排列好,若非就再拋一次。其名字源自Quantum bogodynamics,又稱bozo sort、blort sort或猴子排序(參見無限猴子定理)。
Bogo排序 | |
---|---|
概況 | |
類別 | 排序算法 |
資料結構 | 數組 |
複雜度 | |
平均時間複雜度 | [1] |
最壞時間複雜度 | |
最優時間複雜度 | |
空間複雜度 | |
最佳解 | No |
相關變量的定義 |
實現
編輯以下是偽代碼:
function bogosort(arr)
while arr is not ordered
arr := 隨機排列(arr)
其平均時間複雜度是 O(n × n!),在最壞情況所需時間是無限。它並非一個穩定的算法。
C
編輯#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void swap(void *a,void *b){
unsigned char *p=a;
unsigned char *q=b;
unsigned char tmp;
tmp=*p;
*p=*q;
*q=tmp;
}
/* 洗牌函數 */
void shuffle(void *x,int size_elem,int total_elem){
int i;
for(i=total_elem-1;i>=0;--i){
int r=rand()%(i+1);
swap(x+r*size_elem,x+i*size_elem);
}
}
int main(int argc,char *argv[]){
/* 為了洗牌而需要隨機化函數,此處的函數具有偽隨機性 */
srand((unsigned)time(NULL));
int l[]={5,2,1,3,4};
int n;
n=sizeof(l)/sizeof(l[0]);
/* 先設陣列未排序=0,已排序=1 */
int isSort=0;
int i;
while(!isSort){
/* 進行洗牌動作 */
/* 等同於從搖獎機或籤筒裡依序抽出n個數 */
/* 也等同於從搖獎機或籤筒裡抽出2個數x跟y並交換l[x]與l[y](Bozo排序) */
shuffle(l,sizeof(l[0]),n);
isSort=1;
/* 檢查從搖獎機或籤筒裡所抽出來的數是否比前一個數還大 */
for(i=0;i<n-1;i++){
if(l[i]>l[i+1]){ /* 若較大的陣列編號的值比較小時則重新洗牌 */
isSort=0;
break;
}
}
}
for(i=0;i<n;i++){
printf("%d ",l[i]);
}
printf("\n");
}
Python
編輯from random import shuffle
from itertools import izip, tee
def in_order(my_list):
"""Check if my_list is ordered"""
it1, it2 = tee(my_list)
it2.next()
return all(a<=b for a,b in izip(it1, it2))
def bogo_sort(my_list):
"""Bogo-sorts my_list in place."""
while not in_order(my_list):
shuffle(my_list)
Java
編輯Random random = new Random();
public void bogoSort(int[] n) {
while(!inOrder(n)){
shuffle(n);
}
}
public void shuffle(int[] n) {
for (int i = 0; i < n.length; i++) {
int swapPosition = random.nextInt(i + 1);
int temp = n[i];
n[i] = n[swapPosition];
n[swapPosition] = temp;
}
}
public boolean inOrder(int[] n) {
for (int i = 0; i < n.length-1; i++) {
if (n[i] > n[i+1]) {
return false;
}
}
return true;
}
# Julia Sample : BogoSort
function inOrder(A)
for i=1:length(A)-1
if A[i]>A[i+1]
return false
end
end
return true
end
function BogoSort(A)
while (!inOrder(A))
# Shuffle
for i=1:length(A)
r = rand(1:length(A))
A[i],A[r]=A[r],A[i]
end
end
return A
end
# Main Code
A = [16,586,1,31,354,43,3]
println(A) # Original Array
println(BogoSort2(A)) # Bogo Sort Array
運行時間
編輯這個排序算法基於可能性。平均而言,讓所有元素都被排好序的期望比較次數漸近於 ,期望的位置交換次數漸近 。[1] 期望的位置交換次數增長地比期望比較次數快,是因為只需要比較幾對元素就能發現元素是無序的,但是隨機地打亂順序所需要的交換次數卻與數據長度成比例。在最差的情況下,交換和比較次數都是無限的,這就像隨機投擲硬幣可能連續任意次正面向上。
最好的情況是所給的數據是已經排好序的,這種情況下不需要任何位置交換,而比較次數等於 。
對任何固定長度的數據,算法的預期運行時間像無限猴子定理一樣是無限的:總有一些可能性讓被正確排好序的序列出現。
相關算法
編輯Bozo排序
編輯Bozo排序是另一個基於隨機數的算法。如果列表是無序的,就隨機交換兩個元素的位置再檢查列表是否有序。
參見
編輯參考資料
編輯- ^ 1.0 1.1 H. Gruber, M. Holzer and O. Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms (頁面存檔備份,存於網際網路檔案館), 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, pp. 183-197.