The Slowest Sorting Algorithms

Last Updated : 02 Nov, 2023

A Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of the element in the respective data structure. But Below is some of the slowest sorting algorithms:

Stooge Sort: A Stooge sort is a recursive sorting algorithm. It recursively divides and sorts the array in parts.

Below are the steps of the Stooge Sort:

If the value at index 0 is greater than the value at the last index, swap them.
If the number of elements in the array is greater than two:
1. Recursively call stoogesort function for the initial 2/3rd elements of the array.
2. Recursively call stoogesort function for the last 2/3rd elements of the array.
3. Recursively call stoogesort function for the initial 2/3rd elements again to confirm the resultant array is sorted or not.
Print the sorted array.

Below is the implementation of the above approach:

C++

// C++ program for the stooge sort
#include <iostream>
using namespace std;
 
// Function to implement stooge sort
void stoogesort(int arr[], int l, int h)
{
    // Base Case
    if (l >= h)
        return;
 
    // If first element is smaller than
    // last element, swap them
    if (arr[l] > arr[h])
        swap(arr[l], arr[h]);
 
    // If there are more than 2 elements
    // in the array
    if (h - l + 1 > 2) {
        int t = (h - l + 1) / 3;
 
        // Recursively sort the first
        // 2/3 elements
        stoogesort(arr, l, h - t);
 
        // Recursively sort the last
        // 2/3 elements
        stoogesort(arr, l + t, h);
 
        // Recursively sort the first
        // 2/3 elements again
        stoogesort(arr, l, h - t);
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 4, 5, 3, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    stoogesort(arr, 0, N - 1);
 
    // Display the sorted array
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
 
    return 0;
}

Java

// Java program for the 
// stooge sort
class GFG{
     
// Function to implement 
// stooge sort
static void stoogesort(int arr[], 
                       int l, int h)
{
  // Base Case
  if (l >= h)
    return;
 
  // If first element is smaller
  // than last element, swap them
  if (arr[l] > arr[h]) 
  {
    int temp = arr[l];
    arr[l] = arr[h];
    arr[h] = temp;
  }
 
  // If there are more than 
  // 2 elements in the array
  if (h - l + 1 > 2) 
  {
    int t = (h - l + 1) / 3;
 
    // Recursively sort the 
    // first 2/3 elements
    stoogesort(arr, l, h - t);
 
    // Recursively sort the 
    // last 2/3 elements
    stoogesort(arr, l + t, h);
 
    // Recursively sort the 
    // first 2/3 elements again
    stoogesort(arr, l, h - t);
  }
}
 
// Driver Code
public static void main(String[] args)
{
  int arr[] = {2, 4, 5, 3, 1};
  int N = arr.length;
 
  // Function Call
  stoogesort(arr, 0, N - 1);
 
  // Display the sorted array
  for (int i = 0; i < N; i++) 
  {
    System.out.print(arr[i] + " ");
  }
}
}
 
// This code is contributed by Chitranayal

Python3

# Python3 program for the stooge sort
 
# Function to implement stooge sort
def stoogesort(arr, l, h):
     
    # Base Case
    if (l >= h):
        return
  
    # If first element is smaller than
    # last element, swap them
    if (arr[l] > arr[h]):
        temp = arr[l]
        arr[l] = arr[h]
        arr[h] = temp
 
    # If there are more than 2 elements
    # in the array
    if (h - l + 1 > 2):
        t = (h - l + 1) // 3
  
        # Recursively sort the first
        # 2/3 elements
        stoogesort(arr, l, h - t)
  
        # Recursively sort the last
        # 2/3 elements
        stoogesort(arr, l + t, h)
  
        # Recursively sort the first
        # 2/3 elements again
        stoogesort(arr, l, h - t)
     
# Driver Code
arr = [ 2, 4, 5, 3, 1 ]
N = len(arr)
  
# Function Call
stoogesort(arr, 0, N - 1)
 
# Display the sorted array
for i in range(N):
    print(arr[i], end = " ")
 
# This code is contributed by code_hunt

C#

// C# program for the 
// stooge sort
using System;
class GFG{
     
// Function to implement 
// stooge sort
static void stoogesort(int []arr, 
                       int l, int h)
{
  // Base Case
  if (l >= h)
    return;
 
  // If first element is smaller
  // than last element, swap them
  if (arr[l] > arr[h]) 
  {
    int temp = arr[l];
    arr[l] = arr[h];
    arr[h] = temp;
  }
 
  // If there are more than 
  // 2 elements in the array
  if (h - l + 1 > 2) 
  {
    int t = (h - l + 1) / 3;
 
    // Recursively sort the 
    // first 2/3 elements
    stoogesort(arr, l, h - t);
 
    // Recursively sort the 
    // last 2/3 elements
    stoogesort(arr, l + t, h);
 
    // Recursively sort the 
    // first 2/3 elements again
    stoogesort(arr, l, h - t);
  }
}
 
// Driver Code
public static void Main(String[] args)
{
  int []arr = {2, 4, 5, 3, 1};
  int N = arr.Length;
 
  // Function Call
  stoogesort(arr, 0, N - 1);
 
  // Display the sorted array
  for (int i = 0; i < N; i++) 
  {
    Console.Write(arr[i] + " ");
  }
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// Javascript program for the
// stooge sort
 
// Function to implement
// stooge sort
function stoogesort(arr, l, h)
{
     
    // Base Case
    if (l >= h)
        return;
     
    // If first element is smaller
    // than last element, swap them
    if (arr[l] > arr[h])
    {
        let temp = arr[l];
        arr[l] = arr[h];
        arr[h] = temp;
    }
     
    // If there are more than
    // 2 elements in the array
    if (h - l + 1 > 2)
    {
        let t = Math.floor((h - l + 1) / 3);
         
        // Recursively sort the
        // first 2/3 elements
        stoogesort(arr, l, h - t);
         
        // Recursively sort the
        // last 2/3 elements
        stoogesort(arr, l + t, h);
         
        // Recursively sort the
        // first 2/3 elements again
        stoogesort(arr, l, h - t);
    }
}
 
// Driver Code
let arr = [ 2, 4, 5, 3, 1 ];
let N = arr.length;
 
// Function Call
stoogesort(arr, 0, N - 1);
 
// Display the sorted array
for (let i = 0; i < N; i++)
{
    document.write(arr[i] + " ");
}
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Output

1 2 3 4 5

Time Complexity: O(N^2.709). Therefore, it is slower than even the Bubble Sort that has a time complexity of O(N²).

Slow Sort: The slow sort is an example of Multiply And Surrender a tongue-in-cheek joke of divide and conquer. Slow sort stores the maximum element of the array at the last position by recursively divides the array by half and compares each of them. Then it recursively calls the array without the previous maximum element and stores the new maximum element at the new last position.

Below are the steps of Slow sort:

Find the maximum of the array and place it at the end of the array by
1. Recursively call slowsort function for the maximum of the first N/2 elements.
2. Recursively call slowsort function for the maximum of the remaining N/2 elements.
3. Find the largest of that two maximum and store it at the end.
4. Recursively call slowsort function for the entire array except for the maximum.
Print the sorted array.

Below is the implementation of the above approach:

C++

// C++ program to implement Slow sort
#include <bits/stdc++.h>
using namespace std;
 
// Function for swap two numbers using
// pointers
void swap(int* xp, int* yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
 
// Function that implements Slow Sort
void slowSort(int A[], int i, int j)
{
    // Base Case
    if (i >= j)
        return;
 
    // Middle value
    int m = (i + j) / 2;
 
    // Recursively call with left half
    slowSort(A, i, m);
 
    // Recursively call with right half
    slowSort(A, m + 1, j);
 
    // Swap if first element
    // is lower than second
    if (A[j] < A[m]) {
        swap(&A[j], &A[m]);
    }
 
    // Recursively call with whole
    // array except maximum element
    slowSort(A, i, j - 1);
}
 
// Function to print the array
void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}
 
// Driver Code
int main()
{
    int arr[] = { 6, 8, 9, 4, 12, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    slowSort(arr, 0, N - 1);
 
    // Display the sorted array
    printArray(arr, N);
 
    return 0;
}

Java

// Java program to implement Slow sort
import java.util.*;
 
class GFG
{
 
// Function that implements Slow Sort
static void slowSort(int A[], int i, int j)
{
    // Base Case
    if (i >= j)
        return;
 
    // Middle value
    int m = (i + j) / 2;
 
    // Recursively call with left half
    slowSort(A, i, m);
 
    // Recursively call with right half
    slowSort(A, m + 1, j);
 
    // Swap if first element
    // is lower than second
    if (A[j] < A[m]) 
    {
        int temp = A[j];
        A[j] = A[m];
        A[m] = temp;
    }
 
    // Recursively call with whole
    // array except maximum element
    slowSort(A, i, j - 1);
}
 
// Function to print the array
static void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        System.out.print(arr[i]+ " ");
    System.out.println();
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 6, 8, 9, 4, 12, 1 };
    int N = arr.length;
 
    // Function call
    slowSort(arr, 0, N - 1);
 
    // Display the sorted array
    printArray(arr, N);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python program to implement Slow sort
 
# Function that implements Slow Sort
def slowSort(A, i, j):
   
    # Base Case
    if (i >= j):
        return;
 
    # Middle value
    m = (i + j) // 2;
 
    # Recursively call with left half
    slowSort(A, i, m);
 
    # Recursively call with right half
    slowSort(A, m + 1, j);
 
    # Swap if first element
    # is lower than second
    if (A[j] < A[m]):
        temp = A[j];
        A[j] = A[m];
        A[m] = temp;
 
    # Recursively call with whole
    # array except maximum element
    slowSort(A, i, j - 1);
 
# Function to print the array
def printArray(arr, size):
    i = 0;
    for i in range(size):
        print(arr[i], end=" ");
    print();
 
# Driver Code
if __name__ == '__main__':
    arr = [6, 8, 9, 4, 12, 1];
    N = len(arr);
 
    # Function call
    slowSort(arr, 0, N - 1);
 
    # Display the sorted array
    printArray(arr, N);
 
# This code contributed by gauravrajput1

C#

// C# program to implement Slow sort
using System;
class GFG
{
 
// Function that implements Slow Sort
static void slowSort(int []A, int i, int j)
{
    // Base Case
    if (i >= j)
        return;
 
    // Middle value
    int m = (i + j) / 2;
 
    // Recursively call with left half
    slowSort(A, i, m);
 
    // Recursively call with right half
    slowSort(A, m + 1, j);
 
    // Swap if first element
    // is lower than second
    if (A[j] < A[m]) 
    {
        int temp = A[j];
        A[j] = A[m];
        A[m] = temp;
    }
 
    // Recursively call with whole
    // array except maximum element
    slowSort(A, i, j - 1);
}
 
// Function to print the array
static void printArray(int []arr, int size)
{
    int i;
    for (i = 0; i < size; i++)
        Console.Write(arr[i] + " ");
    Console.WriteLine();
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 6, 8, 9, 4, 12, 1 };
    int N = arr.Length;
 
    // Function call
    slowSort(arr, 0, N - 1);
 
    // Display the sorted array
    printArray(arr, N);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 //Javascript program to implement Slow sort
 
// Function that implements Slow Sort
function slowSort(A, i,j)
{
    // Base Case
    if (i >= j)
        return;
 
    // Middle value
    var m = parseInt((i + j) / 2);
 
    // Recursively call with left half
    slowSort(A, i, m);
 
    // Recursively call with right half
    slowSort(A, m + 1, j);
 
    // Swap if first element
    // is lower than second
    if (A[j] < A[m]) {
        //swapp(A[j], A[m]);
        var t = A[j];
        A[j]=A[m];
        A[m]=t;
    }
     
    // Recursively call with whole
    // array except maximum element
    slowSort(A, i, j - 1);
 
}
 
// Function to print the array
function printArray(arr, size)
{
    var i;
    for (i = 0; i < size; i++)
        document.write( arr[i] + " ");
    document.write("<br>");
}
 
var arr = [ 6, 8, 9, 4, 12, 1 ];
var N = arr.length;
 
// Function call
slowSort(arr, 0, N - 1);
 
// Display the sorted array
printArray(arr, N);
 
//This code is contributed by SoumikMondal
</script>

Output

1 4 6 8 9 12

Time Complexity:

Base Case: O(N^{((log N)/(2+e))} where, e > 0
Average Case: O(N^(log(N)/2))

Even the best case is worse than Bubble sort. It is less efficient than Stooge sort.

Sleep Sort: Below are the steps of Sleep sort:

Create different threads for each of the elements in the input array and then each thread sleeps for an amount of time which is proportional to the value of the corresponding array element.
The thread having the least amount of sleeping time wakes up first and the number gets printed and then the second least element and so on.
The largest element wakes up after a long time and then the element gets printed at the last. Thus, the output is a sorted one.

All this Multithreading process happens in the background and at the core of the OS

Below is the implementation of the above approach:

C++

// C++ program to implement Sleep sort
#ifdef _WIN32
 
// sleep() function for windows machine
#include <Windows.h>
#else
 
// sleep() function for linux machine
#include <unistd.h>
#endif
#include <iostream>
#include <thread>
#include <vector>
 
using namespace std;
 
// Array for storing the sorted values
vector<int> A;
 
// Function for print the array
void printArray(vector<int> arr, int size)
{
    int i;
    for (i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
}
 
// The instruction set for a thread
void add(int x)
{
    // Temporarily suspend execution
    // of each thread for x amount
    // of seconds
    sleep(x);
 
    // Every thread will wake up after
    // a particular time and push the
    // value in sorted array
    A.push_back(x);
}
 
// Function for Sleep sort
void sleepSort(int arr[], int N)
{
 
    vector<thread> threads;
    for (int i = 0; i < N; i++) {
 
        // New threads were launched by
        // using function pointer as
        // callable
        threads.push_back(
            thread(add, arr[i]));
    }
 
    // Waiting for each thread
    // to finish execution
    for (auto& th : threads) {
        th.join();
    }
 
    // Display the sorted array
    cout << "Array after sorting: ";
    printArray(A, A.size());
}
 
// Driver Code
int main()
{
    int arr[] = { 8, 9, 1, 4, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // sleep_sort function call
    sleepSort(arr, N);
 
    return 0;
}
 
// To run compile using -pthread
// {  1, 3, 4, 8, 9}

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
class Main {
    // List for storing the sorted values
    private static List<Integer> A = Collections.synchronizedList(new ArrayList<Integer>());
 
    // Function for print the list
    private static void printList(List<Integer> list) {
        for (int i : list) {
            System.out.print(i + " ");
        }
    }
 
    // The instruction set for a thread
    private static class Add implements Runnable {
        private int x;
 
        Add(int x) {
            this.x = x;
        }
 
        // Temporarily suspend execution
        // of each thread for x amount
        // of seconds
        @Override
        public void run() {
            try {
                Thread.sleep(x * 1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
 
            // Every thread will wake up after
            // a particular time and push the
            // value in sorted list
            A.add(x);
        }
    }
 
    // Function for Sleep sort
    private static void sleepSort(List<Integer> list) {
        List<Thread> threads = new ArrayList<Thread>();
        for (int i : list) {
            // New threads were launched by
            // using runnable interface as
            // callable
            threads.add(new Thread(new Add(i)));
        }
 
        // Start each thread
        for (Thread th : threads) {
            th.start();
        }
 
        // Waiting for each thread
        // to finish execution
        for (Thread th : threads) {
            try {
                th.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
 
        // Display the sorted list
        System.out.print("List after sorting: ");
        Collections.sort(A);
        printList(A);
    }
 
    // Driver Code
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(8);
        list.add(9);
        list.add(1);
        list.add(4);
        list.add(3);
 
        // sleepSort function call
        sleepSort(list);
    }
}

Python3

# Python code for the above approach
import threading
import time
 
# Array for storing the sorted values
A = []
 
# Function for print the array
def printArray(arr):
    for i in arr:
        print(i, end=' ')
 
# The instruction set for a thread
def add(x):
    # Temporarily suspend execution
    # of each thread for x amount
    # of seconds
    time.sleep(x)
 
    # Every thread will wake up after
    # a particular time and push the
    # value in sorted array
    A.append(x)
 
# Function for Sleep sort
def sleepSort(arr):
    threads = []
    for i in arr:
        # New threads were launched by
        # using function pointer as
        # callable
        threads.append(threading.Thread(target=add, args=(i,)))
 
    # Start each thread
    for th in threads:
        th.start()
 
    # Waiting for each thread
    # to finish execution
    for th in threads:
        th.join()
 
    # Display the sorted array
    print("Array after sorting: ", end='')
    printArray(sorted(A))
 
# Driver Code
if __name__ == '__main__':
    arr = [8, 9, 1, 4, 3]
 
    # sleepSort function call
    sleepSort(arr)
 
     
# This code is contributed by sdeadityasharma

C#

using System;
using System.Collections.Generic;
using System.Threading;
 
class Program {
    // List for storing the sorted values
    static List<int> A = new List<int>();
 
    // Function for print the array
    static void PrintArray(List<int> arr, int size)
    {
        for (int i = 0; i < size; i++) {
            Console.Write(arr[i] + " ");
        }
    }
 
    // The instruction set for a thread
    static void Add(int x)
    {
        // Temporarily suspend execution
        // of each thread for x amount
        // of milliseconds
        Thread.Sleep(x);
 
        // Every thread will wake up after
        // a particular time and add the
        // value to the sorted list
        lock(A) { A.Add(x); }
    }
 
    // Function for Sleep sort
    static void SleepSort(int[] arr, int N)
    {
        List<Thread> threads = new List<Thread>();
        for (int i = 0; i < N; i++) {
 
            // New threads were launched by
            // using lambda expression as
            // the ThreadStart delegate
            threads.Add(new Thread(() = > Add(arr[i])));
            threads[i].Start();
        }
 
        // Waiting for each thread
        // to finish execution
        foreach(var thread in threads) { thread.Join(); }
 
        // Display the sorted array
        Console.Write("Array after sorting: ");
        PrintArray(A, A.Count);
    }
 
    // Driver Code
    static void Main()
    {
        int[] arr = { 8, 9, 1, 4, 3 };
        int N = arr.Length;
 
        // SleepSort function call
        SleepSort(arr, N);
    }
}
 
// Output: Array after sorting: 1 3 4 8 9

Javascript

// JavaScript code for the above approach
 
// Array for storing the sorted values
let A = [];
 
// Function for print the array
function printArray(arr) {
    console.log(arr.join(' '))
    // for (let i of arr) {
    //     console.log(i, end=' ');
    // }
}
 
// The instruction set for a "thread"
function add(x) {
    // Temporarily suspend execution
    // of each "thread" for x amount
    // of milliseconds
    setTimeout(() => {
        // Every "thread" will wake up after
        // a particular time and push the
        // value in sorted array
        A.push(x);
    }, x);
}
 
// Function for Sleep sort
function sleepSort(arr) {
    let threads = [];
    for (let i of arr) {
        // New "threads" were launched by
        // using function pointer as
        // callable
        add(i);
    }
 
    // Waiting for all "threads"
    // to finish execution
    setTimeout(() => {
        // Display the sorted array
       process.stdout.write("Array after sorting: ");
        printArray(A.sort());
    }, Math.max(...arr));
}
 
// Driver Code
let arr = [8, 9, 1, 4, 3];
 
// sleepSort function call
sleepSort(arr);
 
// Contributed by adityasha4x71

Output

Array after sorting 1 3 4 8 9

Time Complexity: O(max(input) + N) where, input = value of array element

Other algorithm’s time complexity depends upon the number of data but for sleep sort, it depends on the amount of data. This algorithm won’t work for negative numbers as a thread cannot sleep for a negative amount of time.

Bogo Sort: Two versions of this algorithm exist: one enumerates all permutations until it hits a sorted one, and a randomized version that randomly permutes its input.

Example 1:

C++

// C++ program to implement Bogo Sort
// using permutation
#include <bits/stdc++.h>
using namespace std;
 
// Function to sort array using bogosort
void bogosort(int arr[], int N)
{
    // Run the loop until
    // array is not sorted
    while (!is_sorted(arr, arr + N)) {
 
        // All possible permutations
        next_permutation(arr, arr + N);
    }
}
// Driver Code
int main()
{
 
    int arr[] = { 8, 9, 1, 4, 3 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    bogosort(arr, N);
 
    // Display the sorted array
    cout << "Array after sorting ";
    for (int i = 0; i < N; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
 
    return 0;
}

Java

import java.util.*;
 
public class BogoSort {
    public static void bogosort(int[] arr) {
        Random rand = new Random();
        while (!isSorted(arr)) {
            for (int i = 0; i < arr.length; i++) {
                int randomIndex = rand.nextInt(arr.length);
                int temp = arr[i];
                arr[i] = arr[randomIndex];
                arr[randomIndex] = temp;
            }
        }
    }
 
    public static boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }
 
    public static void main(String[] args) {
        int[] arr = { 8, 9, 1, 4, 3 };
        bogosort(arr);
        System.out.println("Array after sorting: " + Arrays.toString(arr));
    }
}

Python3

import random
 
# Function to sort array using bogosort
def bogosort(arr):
    # Run the loop until array is sorted
    while not all(arr[i] <= arr[i+1] for i in range(len(arr)-1)):
        # All possible permutations
        random.shuffle(arr)
 
# Driver Code
if __name__ == "__main__":
    arr = [8, 9, 1, 4, 3]
    # Function Call
    bogosort(arr)
    # Display the sorted array
    print("Array after sorting", arr)

C#

using System;
 
class Program {
    static void Main(string[] args)
    {
        int[] arr = { 8, 9, 1, 4, 3 };
        int N = arr.Length;
 
        // Function Call
        bogosort(arr, N);
 
        // Display the sorted array
        Console.Write("Array after sorting: ");
        for (int i = 0; i < N; ++i) {
            Console.Write(arr[i] + " ");
        }
        Console.WriteLine();
    }
 
    // Function to sort array using bogosort
    static void bogosort(int[] arr, int N)
    {
        // Run the loop until
        // array is not sorted
        while (!is_sorted(arr, N)) {
            // All possible permutations
            next_permutation(arr, N);
        }
    }
 
    static bool is_sorted(int[] arr, int N)
    {
        for (int i = 0; i < N - 1; ++i) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }
 
    static void next_permutation(int[] arr, int N)
    {
        // Find non-increasing suffix
        int i = N - 1;
        while (i > 0 && arr[i - 1] >= arr[i]) {
            i--;
        }
        if (i <= 0) {
            // Array is sorted in descending order, so
            // reverse it
            Array.Reverse(arr, 0, N);
            return;
        }
 
        // Find successor to pivot
        int j = N - 1;
        while (arr[j] <= arr[i - 1]) {
            j--;
        }
 
        // Swap pivot with its successor
        int temp = arr[i - 1];
        arr[i - 1] = arr[j];
        arr[j] = temp;
 
        // Reverse the suffix
        j = N - 1;
        while (i < j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
}

Javascript

// JS Equivalent
 
let arr = [8, 9, 1, 4, 3];
 
// Function to sort array using bogosort
function bogosort(arr) {
  // Run the loop until array is sorted
  while (!arr.every((val, i) => (i === arr.length - 1) ? true : val <= arr[i + 1])) {
    // All possible permutations
    arr.sort(() => Math.random() - 0.5);
  }
}
 
// Function Call
bogosort(arr);
 
// Display the sorted array
console.log("Array after sorting", arr);

Output

Array after sorting 1 3 4 8 9

Time Complexity:

Base Case: O(N)
Average Case: O(N!)
Worst Case: O(N!)

Example 2:

C++

// C++ program to implement Bogo Sort
// using random shuffle
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if array is
// sorted or not
bool isSorted(int a[], int N)
{
    while (--N > 1) {
 
        // Break condition for
        // unsorted array
        if (a[N] < a[N - 1])
            return false;
    }
    return true;
}
 
// Function to generate permutation
// of the array
void shuffle(int a[], int N)
{
    for (int i = 0; i < N; i++)
        swap(a[i], a[rand() % N]);
}
 
// Function to sort array using
// Bogo sort
void bogosort(int a[], int N)
{
    // If array is not sorted
    // then shuffle array again
    while (!isSorted(a, N)) {
 
        shuffle(a, N);
    }
}
 
// Function to print the array
void printArray(int a[], int N)
{
    for (int i = 0; i < N; i++) {
 
        printf("%d ", a[i]);
    }
    printf("\n");
}
 
// Driver Code
int main()
{
    int a[] = { 3, 2, 5, 1, 0, 4 };
    int N = sizeof a / sizeof a[0];
 
    // Function Call
    bogosort(a, N);
    printf("Array after sorting:");
    printArray(a, N);
    return 0;
}

Java

// Java program to implement Bogo Sort
// using random shuffle
import java.util.*;
 
public class GFG
{
   
  // Function to check if array is
  // sorted or not
  static boolean isSorted(int[] a, int N)
  {
    while (--N > 0) {
 
      // Break condition for
      // unsorted array
      if (a[N] < a[N - 1])
        return false;
    }
    return true;
  }
 
  // Function to generate permutation
  // of the array
  static void shuffle(int[] a, int N)
  {
    Random rnd = new Random();
    for (int i = 0; i < N; i++) {
      int y = rnd.nextInt();
      y = (((y) % N) + N) % N;
 
      // document.write(y);
      int temp = a[i];
      a[i] = a[y];
      a[y] = temp;
    }
  }
   
  // Function to sort array using
  // Bogo sort
  static void bogosort(int[] a, int N)
  {
     
    // If array is not sorted
    // then shuffle array again
    while (isSorted(a, N) == false) {
 
      shuffle(a, N);
    }
  }
   
  // Function to print the array
  static void printArray(int[] a, int N)
  {
    for (int i = 0; i < N; i++) {
      System.out.print(a[i] + " ");
    }
  }
 
  public static void main(String[] args)
  {
    int[] a = { 3, 2, 5, 1, 0, 4 };
    int N = 6;
 
    // Function Call
    bogosort(a, N);
    System.out.print("Array after sorting:");
    printArray(a, N);
  }
}
 
// This code is contributed by Karandeep1234

Python3

# Python program to implement Bogo Sort
# using random shuffle
import random
 
# Function to check if array is 
# sorted or not
def isSorted(a,N):
    while(N > 1):
        N = N - 1
         
        # Break condition for
        # unsorted array
        if (a[N] < a[N - 1]):
            return False
    return True
 
# To generate permutation 
# of the array
def shuffle(a, N):
    for i in range (0, N):
        r = random.randint(0,N-1)
        a[i], a[r] = a[r], a[i]
 
# Function to sort array using
# Bogo sort
def bogosort(a, N):
    # If array is not sorted
    # then shuffle array again
    while (not isSorted(a, N)):
        shuffle(a, N)
 
# Function to print the array
def printArray(a, N):
    for i in range(N):
        print(a[i], end=" ")
    print()
     
# Driver code to test above
a = [3, 2, 5, 1, 0, 4]
N=len(a)
 
# Function Call
bogosort(a,N)
print("Array after sorting:",end="")
printArray(a, N)
 
# This code is contributed by Pushpesh Raj.

C#

// C# program to implement Bogo Sort
// using random shuffle
using System;
class GfG 
{
   
  // Function to check if array is
  // sorted or not
  static bool isSorted(int[] a, int N)
  {
    while (--N > 1) {
 
      // Break condition for
      // unsorted array
      if (a[N] < a[N - 1])
        return false;
    }
    return true;
  }
   
  // Function to generate permutation
  // of the array
  static void shuffle(int[] a, int N)
  {
    Random rnd = new Random();
    for (int i = 0; i < N; i++) {
      int y = rnd.Next() + 1;
      y = y % N;
       
      // document.write(y);
      int temp = a[i];
      a[i] = a[y];
      a[y] = temp;
    }
  }
  // Function to sort array using
  // Bogo sort
  static void bogosort(int[] a, int N)
  {
    // If array is not sorted
    // then shuffle array again
    while (isSorted(a, N) == false) {
 
      shuffle(a, N);
    }
  }
  // Function to print the array
  static void printArray(int[] a, int N)
  {
    for (int i = 0; i < N; i++) {
      Console.Write(a[i] + " ");
    }
  }
 
  static void Main()
  {
    int[] a = { 3, 2, 5, 1, 0, 4 };
    int N = 6;
 
    // Function Call
    bogosort(a, N);
    Console.Write("Array after sorting:");
    printArray(a, N);
  }
}
 
// This code is contributed by garg28harsh.

Javascript

// Javascript program to implement Bogo Sort
// using random shuffle
<script>
 
// Function to check if array is
// sorted or not
function isSorted(a, N)
{
    while (--N > 1) {
 
        // Break condition for
        // unsorted array
        if (a[N] < a[N - 1])
            return false;
    }
    return true;
}
 
// Function to generate permutation
// of the array
function shuffle(a,  N)
{
    for (let i = 0; i < N; i++)
    {
        let y = Math.floor((Math.random() * 100) + 1);
        y= y%N;
        // document.write(y);
        let temp= a[i];
        a[i]= a[y];
        a[y]= temp;
    }
}
 
// Function to sort array using
// Bogo sort
function bogosort(a, N)
{
    // If array is not sorted
    // then shuffle array again
    while (!isSorted(a, N)) {
 
        shuffle(a, N);
    }
}
 
// Function to print the array
function printArray(a,  N)
{
    document.write(a);
}
 
// Driver Code
 
    let a = [ 3, 2, 5, 1, 0, 4 ];
    let N = 6;
 
    // Function Call
    bogosort(a, N);
    document.write("Array after sorting:");
    printArray(a, N);
</script>

Output

Array after sorting:0 1 2 3 4 5

Time Complexity:

Base Case: O(N)
Average Case: O(N*N!)
Worst Case: O(∞)

Clearly, in the worst situation, Bogo sort using random shuffle takes an infinite amount of time to sort an array, and we may say that this is the slowest sorting algorithm. But the thing about Bogo Sort is that it violates some rules in Complexity Analysis. One of the rules is that you actually have to progress towards a goal. You can’t just obviously waste time for example by putting delay loops. The Slow Sort or stooge sort algorithm actually never makes a wrong move. Once it swaps two nodes the nodes will be in the correct order relative to each other and their order will not be reversed.

scorchingeagle

Improve

Algorithms | Sorting | Question 5

The Slowest Sorting Algorithms

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?