This algorithm is exactly what you expect it to be: at every iteration, the elements of the array are randomized and we check if it is sorted. If not, we keep on trying and hoping. Obviously, this algorithm’s worst case scenario time complexity is technically unbounded, meaning that there is a chance that we never land on the sorted array. Conversely, in best case scenario, where our first shuffle yields the sorted array, we have a time complexity of $O(n)$.
Pseudocode
We can describe the algorithm in pseudocode as follows:
1
2
3
4
| BOGOSORT(A)
while not sorted(A)
shuffle(A)
|
Implementation
Python
1
2
3
4
5
6
7
8
9
| import random
def bogosort(array):
while sorted(array) != array:
random.shuffle(array)
array = [43, 2, 21, 3, 70, 8]
bogosort(array)
print(array)
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| package main
import (
"fmt"
"math/rand"
"reflect"
"slices"
)
func bogosort(array []int) {
sorted := append([]int{}, array...)
slices.Sort(sorted)
for !reflect.DeepEqual(sorted, array) {
rand.Shuffle(len(array), func(i, j int) {
array[j], array[i] = array[i], array[j]
})
}
}
func main() {
array := []int{43, 2, 21, 3, 70, 8}
bogosort(array)
fmt.Println(array)
}
|
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| use rand::thread_rng;
use rand::seq::SliceRandom;
fn bogosort(array: &mut [i32]) {
let mut sorted = [0; 6];
sorted.copy_from_slice(&array);
sorted.sort();
while array != sorted {
array.shuffle(&mut thread_rng());
}
}
fn main() {
let mut array: [i32; 6] = [43, 2, 21, 3, 70, 8];
bogosort(&mut array);
println!("{:?}", array);
}
|
References
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 3rd Edition