Bogosort Multiple Choice Questions and Answers (MCQs)

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

1. Which of the following is not an alternative name of bogosort?
a) stupid sort
b) permutation sort
c) donkey sort
d) monkey sort
View Answer

Answer: c
Explanation: Bogosort is also known by names like stupid sort, monkey sort, permutation sort, slow sort and shotgun sort.These names are particularly chosen due to its inefficient algorithm.

2. 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
View Answer

Answer: a
Explanation: Bogosort algorithm successively generates permutations of its input. This process is repeated until the sorted version of the array is found.

3. What is the auxiliary space requirement of bogosort?
a) O(n)
b) O(1)
c) O(log n)
d) O(n log n)
View Answer

Answer: b
Explanation: Bogosort algorithm do not require any extra space for sorting the input array. Thus its auxiliary space requirement is O(1).
advertisement
advertisement

4. What is the best case time complexity of bogosort?
a) O(n2)
b) O(n)
c) O(n log n)
d) O(1)
View Answer

Answer: b
Explanation: Best case time complexity of bogosort occurs when the input array is already sorted. So in such a case we only need to check whether all the elements are sorted which can be done in O(n) time.

5. What is the worst case time complexity of bogosort?
a) O(n2)
b) O(n*n!)
c) O(infinity)
d) O(n log n)
View Answer

Answer: c
Explanation: There is no upper bound to the worst case of this algorithm. It can go on to take very large amount of time if the array has many elements. So the worst case of this algorithm can be taken as O(infinity).

6. Which of the following sorting algorithm is not stable __________
a) insertion sort
b) bubble sort
c) merge sort
d) bogosort
View Answer

Answer: d
Explanation: Out of the given algorithms only bogosort is not stable. This is because it creates permutations of the input array in order to obtain the sorted version. So there is no guarantee that the sorted version obtained by such a method gives a stable output.

7. Which of the following is an in-place sorting algorithm?
a) Merge sort
b) Bogosort
c) Radix sort
d) Counting sort
View Answer

Answer: b
Explanation: Out of the given algorithms only bogosort is an in-place sorting algorithm. It is because bogosort algorithm do not require any extra space for sorting the input array.
advertisement

8. Sleep sort should be preferred over bogosort as it has better time complexity.
a) true
b) false
View Answer

Answer: b
Explanation: If we sort an array using sleep sort then there is no guarantee that the output we get is correctly sorted. So even though sleep sort is better than bogosort in time complexity but it cannot be preferred due to its inaccuracy.

9. What is the average case time complexity of bogosort?
a) O(n2)
b) O(n*n!)
c) O(infinity)
d) O(n log n)
View Answer

Answer: b
Explanation: For calculating the average we first need to calculate the number of possible permutations an array of size n can have. This will be equal to n!. As each permutation also needs to be checked whether it is sorted or not so this takes another n time. Thus overall time complexity becomes O(n*n!).
advertisement

10. 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); 
}
View Answer
Answer: a
Explanation: To implement bogosort algorithm we need to shuffle the input array until we get the sorted array. So we first check whether the array is sorted using function isSorted(). If it is not, then we shuffle it using function shuffle(). This process is repeated until we get a sorted array.
 
 

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.