# Bogo排序

Bogo排序

## 实现

 function bogosort(arr)
while arr is not ordered
arr := 隨機排列(arr)

### 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 = total_elem - 1;
for(i ; 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個數*/
shuffle(l, sizeof(l[0]), n);
isSort = 1;
/*檢查從搖獎機或籤筒裡所抽出來的數是否比前一個數還大*/
for(i = 0; i < n-1; i++) {
if (l[i] > l[i+1]) {/*若較大的陣列編號的值比較小時則重新洗牌*/
isSort = 0;
break;
}
}
}
}


### 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;
}


## 相关算法

### Bozo排序

Bozo排序是另一个基于随机数的算法。如果列表是无序的，就随机交换两个元素的位置再检查列表是否有序。

## 参考资料

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.