Selection Sort – Data Structure Questions and Answers

Data Structures & Algorithms Computer Science & Engineering

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Selection Sort”.

1. What is the advantage of selection sort over other sorting techniques?
A) It requires no additional storage space
B) It is scalable
C) It works best for inputs which are already sorted
D) It is faster than any other sorting technique

Explanation: Selection sort does not require additional storage since it is an in-place sorting algorithm.

2. What is the average case complexity of selection sort?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(n2)

Explanation: Even if the input is partially sorted, selection sort acts as if the entire array is not sorted in the typical case. The input has no effect on the selection sort.

3. What is the disadvantage of selection sort?
A) It requires auxiliary memory
B) It is not scalable
C) It can be used for small keys
D) It takes linear time to sort the elements

Explanation: The efficiency of selection sort degrades as the input size grows.

4. The given array is arr = {3,4,5,2,1}. The number of iterations in bubble sort and selection sort respectively are __________
A) 5 and 4
B) 4 and 5
C) 2 and 4
D) 2 and 5

Explanation: Bubble sort takes 5 iterations and selection sort takes 4(n-1) iterations since the input array is not sorted.

5. The given array is arr = {1,2,3,4,5}. (bubble sort is implemented with a flag variable)The number of iterations in selection sort and bubble sort respectively are __________
A) 5 and 4
B) 1 and 4
C) 0 and 4
D) 4 and 1

Explanation: Since selection sort is insensitive to input, 4(n-1) iterations are needed. Bubble sort, on the other hand, just iterates once to set the flag to 0 since the input has already been sorted.

6. What is the best case complexity of selection sort?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(n2)

Explanation: The best, average and worst case complexities of selection sort is O(n2).
(n-1) + (n-2) + (n-3) + …. + 1 = (n(n-1))/2 ~ (n2)/2.

7. What is an in-place sorting algorithm?
A) It needs O(1) or O(logn) memory to create auxiliary locations
B) The input is already sorted and in-place
C) It requires additional storage
D) It requires additional space

Explanation: Auxiliary memory is needed to temporarily store the data.

8. In the following scenarios, when will you use selection sort?
A) The input is already sorted
B) A large file has to be sorted
C) Large values need to be sorted with small keys
D) Small values need to be sorted with large keys

Explanation: Since selection sort is based on keys, it can efficiently sort a file with large values and small keys.

9. What is the worst case complexity of selection sort?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(n2)

Explanation: The selection sort produces a sub-list, with the LHS of the ‘min’ part already sorted and the RHS to sort. The ‘min’ factor begins with the first element and progresses to the last element.

10. Select the appropriate code that performs selection sort.
A)

        int min;
	for(int j=0; j<arr.length-1; j++)
	{
		min = j;
		for(int k=j+1; k<=arr.length-1; k++)
		{
			if(arr[k] < arr[min])
				min = k;
		}
		int temp = arr[min];
		arr[min] = arr[j];
		arr[j] = temp;
       }

B)

        int min;
	for(int j=0; j<arr.length-1; j++)
	{
		min = j;
		for(int k=j+1; k<=arr.length; k++)
		{
			if(arr[k] < arr[min])
				min = k;
		}
		int temp = arr[min];
		arr[min] = arr[j];
		arr[j] = temp;
	}

C)

        int min;
	for(int j=0; j<arr.length-1; j++)
	{
		min = j;
		for(int k=j+1; k<=arr.length-1; k++)
		{
			if(arr[k] > arr[min])
				min = k;
		}
		int temp = arr[min];
		arr[min] = arr[j];
		arr[j] = temp;
	}

D)

        int min;
	for(int j=0; j<arr.length-1; j++)
	{
		min = j;
		for(int k=j+1; k<=arr.length; k++)
		{
			if(arr[k] > arr[min])
				min = k;
		}
		int temp = arr[min];
		arr[min] = arr[j];
		arr[j] = temp;
	}


Explanation: Selection sort loops through the list, starting with the first element as the ‘min’ element, to pick the least element, which is then swapped with the ‘min’ element.

Selection sort is a sorting algorithm for in-place comparisons in computer science. It has an O(n2) time complexity, making it inefficient on broad lists and generally outperforming the insertion type. Selection sort is known for its simplicity, and in some cases, such as when auxiliary memory is small, it outperforms more complicated algorithms. Since selection sort’s time efficiency is quadratic, there are a variety of sorting techniques with lower time complexity than selection sort. Selection sort differs from other sorting algorithms in that it performs the fewest number of swaps possible, n 1 in the worst case.

Leave a Reply

Your email address will not be published. Required fields are marked *