Gnome Sort Multiple Choice Questions and Answers (MCQs)

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

1. Gnome sort is also called __________
a) Smart sort
b) Stupid sort
c) Bogo sort
d) Special sort
View Answer

Answer: b
Explanation: Gnome sort was originally named as stupid sort but later on it got renamed as gnome sort.

2. How many loops are required to implement gnome sorting algorithm?
a) Single loop
b) 2 nested loops
c) 3 nested loops
d) It does not require any loop
View Answer

Answer: a
Explanation: In this sorting algorithm the variable representing the index number is not incremented in case the adjacent pair of elements are out of place. In such a case its value is decremented instead. Thus it is able to implement sorting using a single loop.

3. Which of the following pair of sorting algorithms are stable?
a) gnome sort and quick sort
b) merge sort and selection sort
c) gnome sort and merge sort
d) heap sort and merge sort
View Answer

Answer: c
Explanation: Gnome sort and merge sort are stable sorting algorithms as the elements with identical values appear in the same order in the output array as they were in the input array when any of these sorting algorithms are implemented.
advertisement
advertisement

4. Auxiliary space used by gnome sort is _________
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer

Answer: a
Explanation: Auxiliary space used by gnome sort is O(1) as it does not use any extra space for manipulating the input. Thus it also qualifies as an in place sorting algorithm.

5. The given array is arr = {1,2,4,3,5}.The number of iterations required to sort the array using gnome sort will be _________
a) 5
b) 6
c) 7
d) 8
View Answer

Answer: b
Explanation: 6 iterations will be required as one pair of elements i.e. {4,3} is out of place which causes the loop to take one step backward.

6. Gnome sort uses which of the following method to implement sorting?
a) Merging
b) Partitioning
c) Selection
d) Exchanging
View Answer

Answer: d
Explanation: Gnome sort implements sorting by exchanging the adjacent elements which are out of order. Thus its method of sorting is called exchanging.

7. What is the best case time complexity of gnome sort?
a) O(n)
b) O(n2)
c) O(n log n)
d) O(log n)
View Answer

Answer: a
Explanation: When the input array is already sorted then in that case there will be no need to decrease the value of the index variable at any stage. So only O(n) time is required in this case as we keep on increasing its value after each iteration.
advertisement

8. Select the appropriate code that performs gnome sort.
a)

while (index > n) 
{ 
        if (index == 0) 
            index++; 
        if (arr[index] <= arr[index - 1]) 
            index++; 
        else 
        { 
            swap(arr[index], arr[index - 1]); 
            index--; 
        } 
}

b)

advertisement
while (index < n) 
{ 
        if (index == 0) 
            index++; 
        if (arr[index] <= arr[index - 1]) 
            index++; 
        else 
        { 
            swap(arr[index], arr[index - 1]); 
            index--; 
        } 
}

c)

while (index < n) 
{ 
        if (index == 0) 
            index++; 
        if (arr[index] >= arr[index - 1]) 
            index++; 
        else 
        { 
            swap(arr[index], arr[index - 1]); 
            index--; 
        } 
}

d)

while (index < n) 
{ 
        if (index == 0) 
            Index--; 
        if (arr[index] >= arr[index - 1]) 
            index++; 
        else 
        { 
            swap(arr[index], arr[index - 1]); 
            Index++; 
        } 
}
View Answer
Answer: c
Explanation: The first if statement increments the value of index if found to be 0 so that comparison can take place for this element. Second if statement checks whether the adjacent pair of elements are in order or not. If found out of order they are swapped under the else statement and index is decremented.
 
 

9. What is the worst case time complexity of gnome sort?
a) O(n)
b) O(n2)
c) O(n log n)
d) O(log n)
View Answer

Answer: b
Explanation: Worst case occurs when the input array is reverse sorted as it will have the maximum number of decrements while sorting. This causes the algorithm to have a time complexity of O(n2) in this case.

10. What is the average case time complexity of gnome sort?
a) O(n)
b) O(n2)
c) O(n log n)
d) O(log n)
View Answer

Answer: b
Explanation: In gnome sort the loop has to take one step backwards every time any adjacent pair of elements is out of place which causes it to have time complexity of O(n2) on an average.

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

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.