# 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 uses which of the following method to implement sorting?

A) Merging
B) Partitioning
C) Selection
D) Exchanging

Explanation: Sorting in Gnome is accomplished by swapping out of order adjacent elements. As a result, the process of sorting it employs is known as exchanging.

2. 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)

Explanation: There will be no need to decrease the value of the index variable at any point if the input array is already sorted. As we keep increasing its value after each iteration, only O(n) time is needed in this case.

3. 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++;
}
}```

Explanation: The first if statement increases the value of index if it is found to be zero, allowing for comparison of this variable. The second if statement determines whether or not the adjacent pair of elements is in order. They are swapped under the else statement if they are found out of order, and the index is decremented.

4. 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)

Explanation: When the input array is reverse sorted, the worst case scenario happens since it will have the most decrements while sorting. As a result, the algorithm has an O(n2) time complexity in this case.

5. 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)

Explanation: When any adjacent pair of elements is out of place in gnome sort, the loop must take one step backwards, giving it an average time complexity of O(n2).

6. Gnome sort is also called __________
A) Smart sort
B) Stupid sort
C) Bogo sort
D) Special sort

Explanation: Gnome sort was originally known as dumb sort, but it was changed to gnome sort later on.

7. 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

Explanation: If the adjacent pair of elements are out of place, the variable representing the index number is not incremented in this sorting algorithm. Instead, its meaning is decremented in this situation. As a result, it is possible to implement sorting with only one loop.

8. 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

Explanation: When any of these sorting algorithms is used, the elements with similar values appear in the same order in the output array as they did in the input array.

9. Auxiliary space used by gnome sort is _________
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)

Explanation: GNOME sort’s auxiliary space is O(1) since it doesn’t need any extra space to manipulate the input. As a result, it can also be classified as an in-place sorting algorithm.

10. 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

Explanation: One pair of elements, i.e. 4,3, is out of place, causing the loop to take a step backward, necessitating 6 iterations.

In 2000, Iranian computer scientist Hamid Sarbazi-Azad (professor of Computer Science and Engineering at Sharif University of Technology) proposed the Gnome sort (dubbed dumb sort) sorting algorithm. The sort was first known as stupid sort (not to be confused with bogosort), before being identified and named gnome sort by Dick Grune. The gnome sort is a sorting algorithm that deals with one item at a time, similar to insertion sort, but moves the item to its proper location through a series of swaps, similar to a bubble sort. It’s conceptually easy and doesn’t include any nested loops. The average execution time is O(n2), but it appears to be O(n) if the list is almost sorted at the start.