Class | Sorting |
---|---|
Data structure | Array |
Worst-case performance | Unbounded (randomized version), (deterministic version) |
Best-case performance | [1] |
Average performance | [1] |
Worst-case space complexity |
In computer science, bogosort [1] [2] (also known as permutation sort and stupid sort [3]) is a sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one that is sorted. It is not considered useful for sorting, but may be used for educational purposes, to contrast it with more efficient algorithms.
Two versions of this algorithm exist: a deterministic version that enumerates all permutations until it hits a sorted one, [2] [4] and a randomized version that randomly permutes its input. An analogy for the working of the latter version is to sort a deck of cards by throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted. In a worst-case scenario with this version, the random source is of low quality and happens to make the sorted permutation unboundedly unlikely to occur. The algorithm's name is a portmanteau of the words bogus and sort. [5]
The following is a description of the randomized algorithm in pseudocode:
while not sorted(deck): shuffle(deck)
Here is an implementation in C:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// executes in-place bogo sort on a given array
static void bogo_sort(int* a, int size);
// returns 1 if given array is sorted and 0 otherwise
static int is_sorted(int* a, int size);
// shuffles the given array into a random order
static void shuffle(int* a, int size);
void bogo_sort(int* a, int size) {
while (!is_sorted(a, size)) {
shuffle(a, size);
}
}
int is_sorted(int* a, int size) {
for (int i = 0; i < size-1; i++) {
if (ai > ai+1]) {
return 0;
}
}
return 1;
}
void shuffle(int* a, int size) {
int temp, random;
for (int i = 0; i < size; i++) {
random = (int) ((double) rand() / ((double) RAND_MAX + 1) * size);
temp = arandom];
arandom = ai];
ai = temp;
}
}
int main() {
// example usage
int input[] = { 68, 14, 78, 98, 67, 89, 45, 90, 87, 78, 65, 74 };
int size = sizeof(input) / sizeof(*input);
// initialize pseudo-random number generator
srand(time(NULL));
bogo_sort(input, size);
// sorted result: 14 45 65 67 68 74 78 78 87 89 90 98
printf("sorted result:");
for (int i = 0; i < size; i++) {
printf(" %d", inputi]);
}
printf("\n");
return 0;
}
Here is the above pseudocode rewritten in Python 3:
import random
# bogosort
# what happens is there is a random array that is generated by the last function
# the first function checks whether the array is sorted or not
# the second function repeatedly shuffles the array for as long as it remains unsorted
# and that's it
# happy coding =>
# this function checks whether or not the array is sorted
def is_sorted(random_array):
for i in range(1, len(random_array)):
if random_arrayi < random_arrayi - 1]:
return False
return True
# this function repeatedly shuffles the elements of the array until they are sorted
def bogo_sort(random_array):
while not is_sorted(random_array):
random.shuffle(random_array)
return random_array
# this function generates an array with randomly chosen integer values
def generate_random_array(size, min_val, max_val):
return random.randint(min_val, max_val) for _ in range(size)]
# the size, minimum value and maximum value of the randomly generated array
size = 10
min_val = 1
max_val = 100
random_array = generate_random_array(size, min_val, max_val)
print("Unsorted array:", random_array)
sorted_arr = bogo_sort(random_array)
print("Sorted array:", sorted_arr)
This code assumes that data
is a simple, mutable, array-like data structure—like Python's built-in list
—whose elements can be compared without issue.
If all elements to be sorted are distinct, the expected number of comparisons performed in the average case by randomized bogosort is asymptotically equivalent to (e − 1)n!, and the expected number of swaps in the average case equals (n − 1)n!. [1] The expected number of swaps grows faster than the expected number of comparisons, because if the elements are not in order, this will usually be discovered after only a few comparisons, no matter how many elements there are; but the work of shuffling the collection is proportional to its size. In the worst case, the number of comparisons and swaps are both unbounded, for the same reason that a tossed coin might turn up heads any number of times in a row.
The best case occurs if the list as given is already sorted; in this case the expected number of comparisons is n − 1, and no swaps at all are carried out. [1]
For any collection of fixed size, the expected running time of the algorithm is finite for much the same reason that the infinite monkey theorem holds: there is some probability of getting the right permutation, so given an unbounded number of tries it will almost surely eventually be chosen.
Class | Sorting |
---|---|
Data structure | Array |
Worst-case performance | Unbounded (randomized version), (deterministic version) |
Best-case performance | [1] |
Average performance | [1] |
Worst-case space complexity |
In computer science, bogosort [1] [2] (also known as permutation sort and stupid sort [3]) is a sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one that is sorted. It is not considered useful for sorting, but may be used for educational purposes, to contrast it with more efficient algorithms.
Two versions of this algorithm exist: a deterministic version that enumerates all permutations until it hits a sorted one, [2] [4] and a randomized version that randomly permutes its input. An analogy for the working of the latter version is to sort a deck of cards by throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted. In a worst-case scenario with this version, the random source is of low quality and happens to make the sorted permutation unboundedly unlikely to occur. The algorithm's name is a portmanteau of the words bogus and sort. [5]
The following is a description of the randomized algorithm in pseudocode:
while not sorted(deck): shuffle(deck)
Here is an implementation in C:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// executes in-place bogo sort on a given array
static void bogo_sort(int* a, int size);
// returns 1 if given array is sorted and 0 otherwise
static int is_sorted(int* a, int size);
// shuffles the given array into a random order
static void shuffle(int* a, int size);
void bogo_sort(int* a, int size) {
while (!is_sorted(a, size)) {
shuffle(a, size);
}
}
int is_sorted(int* a, int size) {
for (int i = 0; i < size-1; i++) {
if (ai > ai+1]) {
return 0;
}
}
return 1;
}
void shuffle(int* a, int size) {
int temp, random;
for (int i = 0; i < size; i++) {
random = (int) ((double) rand() / ((double) RAND_MAX + 1) * size);
temp = arandom];
arandom = ai];
ai = temp;
}
}
int main() {
// example usage
int input[] = { 68, 14, 78, 98, 67, 89, 45, 90, 87, 78, 65, 74 };
int size = sizeof(input) / sizeof(*input);
// initialize pseudo-random number generator
srand(time(NULL));
bogo_sort(input, size);
// sorted result: 14 45 65 67 68 74 78 78 87 89 90 98
printf("sorted result:");
for (int i = 0; i < size; i++) {
printf(" %d", inputi]);
}
printf("\n");
return 0;
}
Here is the above pseudocode rewritten in Python 3:
import random
# bogosort
# what happens is there is a random array that is generated by the last function
# the first function checks whether the array is sorted or not
# the second function repeatedly shuffles the array for as long as it remains unsorted
# and that's it
# happy coding =>
# this function checks whether or not the array is sorted
def is_sorted(random_array):
for i in range(1, len(random_array)):
if random_arrayi < random_arrayi - 1]:
return False
return True
# this function repeatedly shuffles the elements of the array until they are sorted
def bogo_sort(random_array):
while not is_sorted(random_array):
random.shuffle(random_array)
return random_array
# this function generates an array with randomly chosen integer values
def generate_random_array(size, min_val, max_val):
return random.randint(min_val, max_val) for _ in range(size)]
# the size, minimum value and maximum value of the randomly generated array
size = 10
min_val = 1
max_val = 100
random_array = generate_random_array(size, min_val, max_val)
print("Unsorted array:", random_array)
sorted_arr = bogo_sort(random_array)
print("Sorted array:", sorted_arr)
This code assumes that data
is a simple, mutable, array-like data structure—like Python's built-in list
—whose elements can be compared without issue.
If all elements to be sorted are distinct, the expected number of comparisons performed in the average case by randomized bogosort is asymptotically equivalent to (e − 1)n!, and the expected number of swaps in the average case equals (n − 1)n!. [1] The expected number of swaps grows faster than the expected number of comparisons, because if the elements are not in order, this will usually be discovered after only a few comparisons, no matter how many elements there are; but the work of shuffling the collection is proportional to its size. In the worst case, the number of comparisons and swaps are both unbounded, for the same reason that a tossed coin might turn up heads any number of times in a row.
The best case occurs if the list as given is already sorted; in this case the expected number of comparisons is n − 1, and no swaps at all are carried out. [1]
For any collection of fixed size, the expected running time of the algorithm is finite for much the same reason that the infinite monkey theorem holds: there is some probability of getting the right permutation, so given an unbounded number of tries it will almost surely eventually be chosen.