GATE CSE 2013 | Question: 6

Question

Which one of the following is the tightest upper bound that represents the number of swaps required to sort $n$ numbers using selection sort?

• A. $O(\log n$)
• B. $O(n$)
• C. $O(n \log n$)
• D. $O(n^{2}$)

Comments

Ohk thanks

---

anyone please comment on the same question for (1) Merge (2) Quick (3) Insertion sort

---

Sorting Algorithm	Comparisons (Worst-Case)	Swaps / Movements (Worst-Case)
Selection Sort	O(n²)	O(n)
Bubble Sort	O(n²)	O(n²)
Insertion Sort	O(n²)	O(n²)
Quick Sort	O(n²)	O(n²)
Heap Sort	O(n log n)	O(n log n)
Merge Sort	O(n log n)	O(n log n) (writes)

Answer 1

In selection max you can do is $n$ swaps..selecting the smallest element from all the elements and replacing it correct position so $O(n)$

Correct Answer: $B$

Comments

will the maximum number not be n/2.  If we have made n/2 swaps .. that would mean the rest half of the elements would already be in their right positions

---

Number of swap  in selection sort is always n-1

---

@Gaurav nitkkriit Not "always". But in worst case. If array is already sorted, no swaps needed.

Answer 2

Correct Answer : $B$

Best, Average and worst case will take maximum $O(n)$ swaps.
Selection sort time complexity $O(n^2)$ in terms of number of comparisons. Each of these scans requires one swap for $n-1$ elements (the final element is already in place).

Answer 3

Sure, let's go through an example to demonstrate the number of swaps in selection sort.

Consider the array \( A = [64, 25, 12, 22, 11] \).

Step-by-Step Selection Sort with Swaps:

1. Initial array:\([64, 25, 12, 22, 11]\)

   - Find the minimum element (11).

   - Swap it with the first element (64).

   - Array after 1st swap:** \([11, 25, 12, 22, 64]\)

2.Second iteration \([11, 25, 12, 22, 64]\)

   - Find the minimum element from the remaining unsorted portion (12).

   - Swap it with the second element (25).

   - Array after 2nd swap: \([11, 12, 25, 22, 64]\)

3. Third iteration:\([11, 12, 25, 22, 64]\)

   - Find the minimum element from the remaining unsorted portion (22).

   - Swap it with the third element (25).

   - Array after 3rd swap:\([11, 12, 22, 25, 64]\)

4. Fourth iteration:\([11, 12, 22, 25, 64]\)

   - The minimum element from the remaining unsorted portion is already in its place (25).

   - No swap needed, but if we were to count this as a swap, it would be with itself.

After sorting, the array is \([11, 12, 22, 25, 64]\). The total number of swaps is 3.

General Case:

In a general case, for an array of \( n \) elements, the selection sort makes exactly \( n - 1 \) swaps. This is because each iteration, except the last one, performs one swap to place the minimum element in its correct position.

So, for \( n \) elements, the mathematical expression for the number of swaps is:

\[ S(n) = n - 1 \]

where \( S(n) \) is the number of swaps required to sort the array.