Bozo-Sort

Bozo-Sort is a variation of Bogosort. It is another highly inefficient randomized algorithm based on the trial and error approach.

Bozo-sort sorts the input list by repeatedly swapping 2 random elements of the list and checking if the list is sorted or not. The process is repeated till the input list is sorted.

Implementation

In this section, we will see C implementation of Bozo-sort.

Steps

  1. Check if the input list is sorted or not.
  2. If the input list is sorted, terminate the program.
  3. If the input list is not sorted, choose any 2 random elements and swap them.
  4. Go back to step 1.
#include <stdio.h> 
#include <stdlib.h> 
#include<time.h> 

// swap 2 random elements of arr
void swap_random(int* arr, int n) {

	int r1, r2, temp;
	srand(time(0));
	r1 = rand() % n;
	r2 = rand() % n;
	temp = arr[r1];
	arr[r1] = arr[r2];
	arr[r2] = 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)) {
		swap_random(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: 4
Enter Array Elements: 4 3 2 1
Array After Sort: 1 2 3 4
Time Taken to sort: 26.066000

Bozo-sort took 26 seconds to sort an array of size 4.

Time Complexity

Best Case: Best case occurs when the array is already sorted. The complexity to check if an array is sorted or not is O(N).

Average Case: The average case time complexity of Bozo-sort is O(N!).

Worst Case: Bozo-sort is a randomized algorithm. It is possible that we never generate a sorted sequence. Thus, the program will never terminate.

References

Gruber H., Holzer M., Ruepp O. (2007) Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms. In: Crescenzi P., Prencipe G., Pucci G. (eds) Fun with Algorithms. FUN 2007. Lecture Notes in Computer Science, vol 4475. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72914-3_17

Leave a Comment

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