演算法實現/排序/隨機排序
隨機排序（也稱為隨機排序、散彈排序或猴子排序）是一種特別無效的排序演算法。它唯一的作用是用於教育目的，將其與其他更現實的演算法進行對比。如果隨機排序被用來對一副牌進行排序，它將包括檢查這副牌是否按順序排列，如果不是，就會把這副牌扔到空中，隨機撿起卡片，然後重複這個過程，直到這副牌排序完成。它的名字來源於單詞bogus。
以下是用虛擬碼描述的演算法。
while not inOrder(deck) do
shuffle(deck);
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
static const int NUM = 7;
bool IsInOrder(const vector<int>& x) {
return adjacent_find(x.begin(), x.end(), greater<int>()) == x.end();
}
int main() {
int counter = 0;
srand(time(0));
vector<int> bogo;
// Initiate the vector with NUM random numbers
generate_n(back_inserter(bogo), NUM, rand);
// Bogosort
while(!IsInOrder(bogo)) {
random_shuffle(bogo.begin(), bogo.end());
copy(bogo.begin(), bogo.end(), ostream_iterator<int>(cout, " "));
cout << "\n\n";
counter++;
}
cout << "Sorting took " << counter << " tries." << endl;
}
import java.util.*;
public void bogoSort(List<Integer> deck) {
while(!isInOrder(deck)) {
Collections.shuffle(deck);
}
}
public boolean isInOrder(List<Integer> deck) {
for (int i = 0; i < deck.size() - 1; i++) {
if (deck.get(i) > deck.get(i+1)) return false;
}
return true;
}
function is_sorted(t)
local last_v = t[1]
local current_v
for i = 2, #t do
current_v = t[i]
if last_v > current_v then
return false
end
last_v = current_v
end
return true -- if the length of the table is 1, it will return as if it is sorted
end
function bogosort(t)
while not is_sorted(t) do
local nt = {t[1]}
for i = 2, #t do
table.insert(nt, math.random(1, #nt), t[i])
end
t = nt
end
return t
end
use List::Util qw{shuffle};
sub inorder (&@) {
my $sub = shift;
while (scalar(@_) > 1) {
return unless ( $sub->(shift, $_[0]) )
}
return 1;
}
my @list = (1, 2, 3, 4, 5, 6);
@list = do { shuffle @list } until inorder { $_[0] <= $_[1] } @list;
或者，對於一副牌
use List::Util qw{shuffle};
sub inorder (&@) {
my $sub = shift;
while (scalar(@_) > 1) {
return unless ( $sub->(shift, $_[0]) )
}
return 1;
}
my @list = qw{2 3 4 5 6 7 8 9 A J K Q};
@list = do { shuffle @list } until inorder { $_[0] le $_[1] } @list;
my @list = 1, 2, 3, 4, 5, 6;
@list .= pick(*) until [<=] @list;
或者，對於一副牌
my @deck = <2 3 4 5 6 7 8 9 A J K Q>;
@deck .= pick(*) until [le] @deck;
from random import *
from time import *
seed()
valeurs = []
for i in range(0, 10):
valeurs.append(randint(0, 100))
def inorder(valeurs):
i = 0
j = len(valeurs)
while i + 1 < j:
if valeurs[i] > valeurs[i + 1]:
return(False)
i += 1
return(True)
def bogo(valeurs):
while not inorder(valeurs):
shuffle(valeurs)
return valeurs
start = time()
print("Before: ", valeurs)
valeurs = bogo(valeurs)
print("After: ", valeurs)
print("%.2f seconds" % (time() - start))
class Array
def bogosort!
shuffle! until sorted?
end
def sorted?
each_cons(2).all? { |a,b| a <= b }
end
end
(define (bogosort to-sort)
(cond
((list? to-sort) (vector->list (bogosort (list->vector to-sort))))
((sorted? to-sort) to-sort)
(else (bogosort (shuffle to-sort)))))
(define (sorted? to-sort)
(define (check-index-and-next n)
(or (>= n (- (vector-length to-sort) 1))
(and (<= (vector-ref to-sort n) (vector-ref to-sort (+ 1 n)))
(check-index-and-next (+ n 1)))))
(check-index-and-next 0))
(define (shuffle deck)
(define (set-index-to-random n)
(if (< n 1)
deck
(begin
(let ((rand (random (+ 1 n)))
(val-at-n (vector-ref deck n)))
(vector-set! deck n (vector-ref deck rand))
(vector-set! deck rand val-at-n))
(set-index-to-random (- n 1)))))
(set-index-to-random (- (vector-length deck) 1)))
|deck|
deck := (1 to:10) asArray randomShuffle.
[ deck isSorted ] whileFalse:[
deck randomShuffle
]
在 C++ 中還有各種其他實現，包括一個STL風格的演算法，它源於 ACCU General 郵件列表中的討論。
- H. Gruber, M. Holzer 和 O. Ruepp: 排序的慢速方式：對反常的糟糕隨機排序演算法的分析，第四屆演算法樂趣國際會議，義大利卡斯蒂利亞切洛，2007 年，計算機科學講義 4475，第 183-197 頁。
- Jargon File 中的“bogo-sort”條目，“典型的反常的糟糕演算法”
- http://c2.com/cgi/wiki?BogoSort
- 隨機排序：一種在類 Unix 系統上執行的實現，類似於標準排序程式。
- 隨機排序 和 jmmcg::bogosort：隨機排序演算法的簡單而反常的 C++ 實現。