Bogosort – Multiple Choice Questions and Answers (MCQs)

Data Structures & Algorithms Computer Science & Engineering

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Bogosort”.

1. Which of the following sorting algorithm is not stable __________
A) insertion sort
B) bubble sort
C) merge sort
D) bogosort

Explanation: Only bogosort is not stable among the algorithms presented. This is because, in order to obtain the sorted version, it produces permutations of the input array. As a result, there is no guarantee that the sorted version obtained using this approach will produce a stable result.

2. Which of the following is an in-place sorting algorithm?
A) Merge sort
B) Bogosort
C) Radix sort
D) Counting sort
Explanation: Only bogosort is an in-place sorting algorithm among the algorithms presented. Since the bogosort algorithm does not need any additional space for sorting the input sequence, this is the case.

3. Sleep sort should be preferred over bogosort as it has better time complexity.
A) true
B) false

Explanation: If we use sleep sort to sort an array, there is no guarantee that the output will be correctly sorted. So, although sleep sort has a lower time complexity than bogosort, it cannot be preferred due to its inaccuracy.

4. What is the average case time complexity of bogosort?
A) O(n2)
B) O(n*n!)
C) O(infinity)
D) O(n log n)

Explanation: To measure the average, we must first determine the number of permutations that an array of size n can have. This would be the same as n! Since and permutation must be tested to see whether it is sorted or not, this takes an additional n seconds. As a result, the total time complexity is O(n*n!).

5. Which of the following code correctly implements bogosort algorithm?
A)

bool isSorted(int a[], int n) 
{ 
    while ( --n > 1 ) 
        if (a[n] < a[n-1]) 
            return false; 
    return true; 
} 
void shuffle(int a[], int n) 
{ 
    for (int i=0; i < n; i++) 
        swap(a[i], a[rand()%n]); 
} 
void bogosort(int a[], int n) 
{ 
 
    while ( !isSorted(a, n) ) 
        shuffle(a, n); 
}

B)

bool isSorted(int a[], int n) 
{ 
    while ( --n > 1 ) 
        if (a[n] < a[n-1]) 
            return true; 
    return false; 
} 
void shuffle(int a[], int n) 
{ 
    for (int i=0; i < n; i++) 
        swap(a[i], a[rand()%n]); 
} 
void bogosort(int a[], int n) 
{ 
 
    while ( !isSorted(a, n) ) 
        shuffle(a, n); 
}

C)

bool isSorted(int a[], int n) 
{ 
    while ( --n > 1 ) 
        if (a[n] > a[n-1]) 
            return true; 
    return false; 
}
void shuffle(int a[], int n) 
{ 
    for (int i=0; i < n; i++) 
        swap(a[i], a[rand()%n]); 
} 
void bogosort(int a[], int n) 
{ 
 
    while ( !isSorted(a, n) ) 
        shuffle(a, n); 
}

D)

bool isSorted(int a[], int n) 
{ 
    while ( --n > 1 ) 
        if (a[n] < a[n-1]) 
            return false; 
    return true; 
} 
void shuffle(int a[], int n) 
{ 
    for (int i=0; i < n; i++) 
        swap(a[i], a[rand()%n]); 
} 
void bogosort(int a[], int n) 
{ 
 
    while ( isSorted(a, n) ) 
        shuffle(a, n); 
}


Explanation:
We must shuffle the input array before we get the sorted array to implement the bogosort algorithm. So we use the feature isSorted to see if the array is sorted (). If it isn’t, we shuffle it using the shuffle function (). This procedure is repeated until the list is sorted.

6. Which of the following is not an alternative name of bogosort?
A) stupid sort
B) permutation sort
C) donkey sort
D) monkey sort

Explanation: Bogosort is also called “stupid type,” “monkey sort,” “permutation sort,” “slow sort,” and “shotgun sort.” These names were chosen in part because of the algorithm’s inefficiency.

7. Bogosort works by __________
A) generating random permutations of its input
B) partitioning the array
C) dividing the value of input elements
D) generating permutations according to the value of first element of array

Explanation: The Bogosort algorithm produces permutations of its input in a sequential manner. This method is repeated until the array’s sorted version is discovered.

8. What is the auxiliary space requirement of bogosort?
A) O(n)
B) O(1)
C) O(log n)
D) O(n log n)

Explanation: For sorting the input array, the Bogosort algorithm does not require any additional space. As a result, it has an auxiliary space requirement of O. (1).

9. What is the best case time complexity of bogosort?
A) O(n2)
B) O(n)
C) O(n log n)
D) O(1)

Explanation: When the input array is already sorted, bogosort has the best time complexity. In this case, all we have to do is verify if all of the elements are sorted, which takes O(n) time.

10. What is the worst case time complexity of bogosort?
A) O(n2)
B) O(n*n!)
C) O(infinity)
D) O(n log n)

Explanation: The worst case of this algorithm has no upper limit. If the array contains a large number of elements, it can take a long time to process. As a result, the worst-case scenario for this algorithm is O. (infinity).

Bogosort (also known as permutation sort, dumb sort, or slowsort) is a slow sorting algorithm based on the generate and evaluate paradigm of computer science. The function iterates through permutations of its input until it discovers one that is sorted. It is not useful for sorting, but it can be used to contrast it with more effective algorithms for educational purposes. There are two variants of this algorithm: a deterministic version that counts all permutations until it finds one that is sorted, and a randomised version that permutes the input randomly.

Leave a Reply

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