Selection Sort Algorithm and Step-by-Step Trace

Selection Sort ek in-place comparison sorting algorithm hai. Is algorithm ka core logic yeh hota hai ki yeh array ko do parts me divide karta hai: Sorted subarray (left) aur Unsorted subarray (right). Har pass me unsorted part me se sabse minimum element ko select karke unsorted part ke first element ke saath swap kar diya jata hai.

Step-by-Step Working Mechanism

Initial Array: [ 64, 25, 12, 22, 11 ]

Pass 1 (i=0):
Find min in [64, 25, 12, 22, 11] -> Min is 11 at index 4
Swap A[0](64) with A[4](11):
Array: [ 11 | 25, 12, 22, 64 ]

Pass 2 (i=1):
Find min in [25, 12, 22, 64] -> Min is 12 at index 2
Swap A[1](25) with A[2](12):
Array: [ 11, 12 | 25, 22, 64 ]

Pass 3 (i=2):
Find min in [25, 22, 64] -> Min is 22 at index 3
Swap A[2](25) with A[3](22):
Array: [ 11, 12, 22 | 25, 64 ]

Pass 4 (i=3):
Find min in [25, 64] -> Min is 25 at index 3 (already in place)
Array: [ 11, 12, 22, 25, 64 ] -> Sorted!

Selection Sort Algorithm

SELECTION_SORT(A, N)
1. For i = 0 to N - 2 do:
2.     Set min_idx = i
3.     For j = i + 1 to N - 1 do:
4.         If A[j] < A[min_idx] then:
5.             min_idx = j
6.     End For
7.     If min_idx != i then:
8.         Swap(A[i], A[min_idx])
9. End For

Complexity and Properties

• Comparisons: Hamesha n(n-1)/2 comparisons hote hain, chahe array already sorted ho ya reverse sorted.
• Time Complexity: Best Case = O(n^2), Average Case = O(n^2), Worst Case = O(n^2).
• Swaps: Maximum O(n) swaps lagte hain (yeh iska sabse bada advantage hai jab memory write operations costly hon).
• Space Complexity: O(1) auxiliary space (In-place).
• Stability: Unstable sorting algorithm (e.g. [4a, 5, 4b, 2] me 4a aur 2 swap hone par 4a baad me chala jata hai).

Agli post me hum cover karenge Insertion Sort Algorithm and In-Place Analysis.