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.


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


  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> 

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

	int r1, r2, temp;
	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);



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.


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.

Leave a Comment

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