Selection Sort Algorithm
Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.
Working of Selection Sort
Selection Sort works by repeatedly finding the smallest (or largest) element from the unsorted part of the array and placing it at the beginning of the sorted part.
Step-by-Step Working:
- Start from the first element.
- Find the minimum element in the entire array.
- Swap it with the first element.
- Now, the first element is sorted.
- Move to the second element and repeat the process for the remaining unsorted part of the array.
- Continue this process until the whole array is sorted.
Example of Selection Sort
Given Array: [64, 25, 12, 22, 11]
Pass 1:
- Find the smallest element in the array: 11
- Swap it with the first element 64
Result: [11, 25, 12, 22, 64]
Pass 2:
- Find the smallest element in the rest [25, 12, 22, 64] → 12
- Swap with 25
Result: [11, 12, 25, 22, 64]
Pass 3:
- Find smallest in [25, 22, 64] → 22
- Swap with 25
Result: [11, 12, 22, 25, 64]
Pass 4:
- Find smallest in [25, 64] → 25
- Already in correct place
Result: [11, 12, 22, 25, 64]
Final Sorted Array:
[11, 12, 22, 25, 64]
Selection Sort Python code:
for i = 0 to n-1:
minIndex = i
for j = i+1 to n-1:
if arr[j] < arr[minIndex]:
minIndex = j
swap(arr[i], arr[minIndex])
Time Complexity of Selection Sort:
|
Case |
Time Complexity |
Explanation |
|
Best Case |
O(n²) |
It still scans the entire array to find the minimum, even if sorted. |
|
Average Case |
O(n²) |
Always performs n(n−1)/2 comparisons regardless of input. |
|
Worst Case |
O(n²) |
No optimization based on input ordering. |
Space Complexity:
- O (1) (in-place sorting, no extra memory used)
Note:
Selection Sort is more efficient than Bubble Sort in terms of swaps (does at most n-1 swaps), but time complexity remains quadratic, making it unsuitable for large datasets.