Engineering Questions with Answers - Multiple Choice Questions

# Gnome Sort Multiple Choice MCQ

1 - Question

Gnome sort is also called __________
a) Smart sort
b) Stupid sort
c) Bogo sort
d) Special sort

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

2 - Question

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: 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 - Question

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: 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 - Question

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

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

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: 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 - Question

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

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

7 - Question

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: 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 - Question

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

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: 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 - Question

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)