250+ TOP MCQs on Gnome Sort and Answers

Data Structures & Algorithms Multiple Choice Questions on “Gnome Sort”.

1. Gnome sort is also called __________
a) Smart sort
b) Stupid sort
c) Bogo sort
d) Special sort
Answer: b
Clarification: 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

Answer: a
Clarification: 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

Answer: c
Clarification: 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.

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

Answer: a
Clarification: 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
Clarification: 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
Clarification: 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(n²)
c) O(n log n)
d) O(log n)

Answer: a
Clarification: 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.

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)

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
Clarification: 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(n²)
c) O(n log n)
d) O(log n)

Answer: b
Clarification: 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(n²) in this case.

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

Answer: b
Clarification: 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(n²) on an average.

& Algorithms.

and Answers.