Question

If a list is having 'n' elements, then how many passes 'Selection Sort' will require to sort the list?

• A. 1
• B. n - 1
• C. n
• D. 0

Hint:

Most comparison-based sorting algorithms (Bubble Sort, Selection Sort, Insertion Sort) require exactly $n-1$ passes to guarantee a completely sorted list of size $n$.

Answer 1

The Correct Option is B

Step 1: Understanding the Question:
The question asks for the total number of passes needed to sort an unsorted list of $n$ elements using the Selection Sort algorithm.

Step 2: Key Operational Logic of Selection Sort:
- Selection sort sorts an array by repeatedly finding the minimum element (for ascending order) from the unsorted part and putting it at the beginning.
- The algorithm divides the list into a sorted sublist and an unsorted sublist.

Step 3: Detailed Explanation:
- Let us trace the progress of the algorithm across a collection of size $n$:
- In the 1st pass, the algorithm searches the entire list of $n$ elements, finds the minimum, and swaps it with the element at index 0. Now, the first element is sorted.
- In the 2nd pass, the search begins at index 1 to find the minimum of the remaining $n-1$ elements, swapping it with the element at index 1.
- This process continues sequentially.
- By the time we complete the $(n-1)$-th pass, $n-1$ elements have been successfully placed in their correct sorted positions.
- Consequently, the final remaining 1 element must automatically be in its correct sorted position at the end of the list.
- Thus, no further $n$-th pass is required. The total number of passes needed to sort the entire list of size $n$ is exactly $n-1$.

Step 4: Final Answer:
An array of size $n$ requires exactly $n-1$ passes to be fully sorted using Selection Sort.
Hence, option (B) is the correct choice.