Bogosort

Bogosort is just another sorting algorithm. Bogosort is highly inefficient compared to other sorting algorithms. It is a randomized algorithm and is based on the trial and error paradigm. Bogosort basically generates random permutations of the input list and check if the list is sorted or not. This process is continued until the input list is sorted.

For example, suppose we want to sort a deck of cards. Using Bogosort to sort the deck of cards is like repeatedly throwing the deck of cards in the air and then randomly picking up the cards and checking if the cards are sorted or not.

Implementation

Bogosort is never used for practical purposes due to it’s non-deterministic nature and high complexity. It is limited to academia.

Below is the implementation of Bogosort in the C language. The program also displays the time it took to sort the array.

#include <stdio.h> 
#include <stdlib.h> 
#include<time.h> 

// shuffle arr
// generate a random permutation of arr
void shuffle(int* arr, int n) {

	int r, i, temp;

	srand(time(0));

	for (i = n - 1; i > 0; --i) {

		r = rand() % (i + 1);
		temp = arr[r];
		arr[r] = arr[i];
		arr[i] = temp;

	}

}

// returns 1 if arr is sorted in ascending order
// otherwise returns 0
int is_sorted(int* arr, int n) {

	int i;
	for (i = 0; i < n - 1; ++i) {
		if (arr[i] > arr[i + 1])
			return 0;
	}
	return 1;
}

// bogosort function
void bogosort(int* arr, int n) {

	while (!is_sorted(arr, n)) {
		shuffle(arr, n);
	}

}

int main() {

	int n;
	clock_t t;
	int arr[100];

	printf("Enter size of array: ");
	scanf("%d", &n);

	printf("Enter Array Elements: ");
	for (int i = 0; i < n; ++i) {
		scanf("%d", &arr[i]);
	}

	t = clock();
	bogosort(arr, n);
	t = clock() - t;

	printf("Array After Sort: ");
	for (int i = 0; i < n; ++i) {
		printf("%d ", arr[i]);
	}
	printf("\nTime Taken to sort: %llf", ((double)t) / CLOCKS_PER_SEC);

}

Output

Enter size of array: 5
Enter Array Elements: 5 2 3 1 4
Array After Sort: 1 2 3 4 5
Time Taken to sort: 6.286000

As you can see, Bogosort took 6.3 seconds to sort an array of 5 elements. Since the permutations are randomly generated, the time taken to sort may change on each execution.

Time Complexity

Best Case: In the best case, the array is already sorted. We require N iterations to check if an array is sorted or not. Time complexity is O(N).

Average Case: There are N! permutations. There can only be one sorted permutation.

Probability to get sorted permutation = 1/N!

Average number of tries required to get sorted permutation = N!

Generating each permutation and checking if the permutation is sorted or not requires O(N) comparisions.

Thus, average time complexity of bogosort = O(N*N!)

Worst Case: It is possible that the program may never generate a sorted permutation. Thus, the program may never terminate.

There is a deterministic implementation of Bogosort, known as Permutation Sort. Instead of generating random permutations, we generate each permutation only once. Permutation Sort is guaranteed to produce results, unlike Bogosort.

Leave a Comment

Your email address will not be published. Required fields are marked *