What is Selection Sort?
Selection Sort is a simple and intuitive sorting algorithm that divides the input array into two parts: a sorted section and an unsorted section. It repeatedly selects the smallest (or largest, depending on the order) element from the unsorted section and swaps it with the first element of the unsorted section, effectively growing the sorted section one element at a time.
While not as efficient as algorithms like Merge Sort or Quick Sort, Selection Sort is easy to understand and implement. It is most suitable for small datasets due to its simplicity and predictable behavior.
When to Use Selection Sort?
Selection Sort is not the fastest algorithm for large datasets, but it has some use cases where it might be a reasonable choice:
Small Datasets: For small arrays, the simplicity of Selection Sort can make it a convenient choice.
Limited Memory: Selection Sort sorts in place, meaning it requires minimal additional memory, making it suitable for memory-constrained applications.
Understanding Sorting Fundamentals: Its straightforward nature makes Selection Sort an excellent starting point for learning about sorting algorithms.
However, for larger datasets, Selection Sort's inefficiency becomes apparent due to its O(n²) time complexity in both average and worst-case scenarios.
How Selection Sort Works
Selection Sort operates in a step-by-step process that involves finding the smallest (or largest) element in the unsorted section and moving it to the sorted section.
Step-by-Step Explanation
Here's how Selection Sort works:
-
Find the Smallest Element:
- Start from the first element of the array and traverse through the unsorted section to find the smallest element.
-
Swap the Smallest Element:
- Swap the smallest element with the first element of the unsorted section, effectively growing the sorted section by one.
-
Repeat:
- Move to the next element and repeat the process until the entire array is sorted.
Visual Representation of Selection Sort
To sort the array [29, 10, 14, 37, 13]:
- Find the smallest element (10) and swap it with the first element: [10, 29, 14, 37, 13]
- Find the next smallest element (13) and swap it with the second element: [10, 13, 14, 37, 29]
- Continue this process until the array is fully sorted: [10, 13, 14, 29, 37]
Pseudocode for Selection Sort
function selectionSort(arr):
for i from 0 to size of arr - 1:
minIndex = i
for j from i + 1 to size of arr:
if arr[j] < arr[minIndex]:
minIndex = j
swap arr[i] with arr[minIndex]
return arr
Implementing Selection Sort in Kotlin
fun selectionSort(arr: IntArray): IntArray {
for (i in arr.indices) {
// Assume the first unsorted element is the smallest
var minIndex = i
for (j in i + 1 until arr.size) {
if (arr[j] < arr[minIndex]) {
minIndex = j
}
}
// Swap the smallest element with the first unsorted element
val temp = arr[i]
arr[i] = arr[minIndex]
arr[minIndex] = temp
}
return arr
}
Code Walkthrough
-
Outer Loop:
- The outer loop starts from the first element and moves towards the last, representing the growing sorted section.
-
Inner Loop:
- The inner loop scans the unsorted section of the array to find the smallest element.
-
Swap Operation:
- The smallest element is swapped with the first element of the unsorted section, ensuring the sorted section grows by one.
Visual Step-by-Step Process
Initial Array: [29, 10, 14, 37, 13]
Pass 1:
[29, 10, 14, 37, 13] // Find minimum in entire array
↓ ↓
[10, 29, 14, 37, 13] // 10 is minimum, swap with first element
✓
Pass 2:
[10, 29, 14, 37, 13] // Find minimum in unsorted portion
✓ ↓ ↓
[10, 13, 14, 37, 29] // 13 is minimum, swap with second element
✓ ✓
Pass 3:
[10, 13, 14, 37, 29] // Find minimum in unsorted portion
✓ ✓ ↓
[10, 13, 14, 37, 29] // 14 is already in position
✓ ✓ ✓
Pass 4:
[10, 13, 14, 37, 29] // Find minimum in unsorted portion
✓ ✓ ✓ ↓ ↓
[10, 13, 14, 29, 37] // 29 is minimum, swap with fourth element
✓ ✓ ✓ ✓
Final Result:
[10, 13, 14, 29, 37] // Array is sorted
✓ ✓ ✓ ✓ ✓
Legend:
- ↓ : Elements being compared
- ✓ : Sorted portion
- Unmarked: Unsorted portion
Time Complexity Analysis
Best Case: O(n²)
- Even if the array is already sorted, Selection Sort still needs to verify this by comparing all elements
- For each element i, it needs to scan through (n-i) elements to confirm it's in the right position
- Total comparisons: (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2
Worst Case: O(n²)
- Occurs when array is sorted in reverse order
- Same number of comparisons as best case
- Maximum number of swaps needed (n-1 swaps)
Average Case: O(n²)
- Regardless of input distribution, Selection Sort always makes the same number of comparisons
- Number of comparisons: n(n-1)/2
- Number of swaps ranges from 0 to (n-1)
Space Complexity: O(1)
- Only requires a single additional memory space for the swap operation
- Sorts in-place, modifying the original array
Detailed Performance Breakdown
Number of Operations
For an array of size n:
- Comparisons:
- First pass: (n-1) comparisons
- Second pass: (n-2) comparisons
- Third pass: (n-3) comparisons And so on...
Total comparisons = (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2
- Swaps:
- Best case: 0 swaps (already sorted)
- Worst case: (n-1) swaps (reverse sorted)
- Average case: (n-1)/2 swaps
Performance Table
Array Size (n) | Comparisons | Best Case Swaps | Worst Case Swaps |
---|---|---|---|
10 | 45 | 0 | 9 |
100 | 4,950 | 0 | 99 |
1,000 | 499,500 | 0 | 999 |
Optimization Techniques
-
Early Termination
- If no swaps are made in a pass, the array is sorted
- However, this doesn't improve the big-O complexity
Memory Usage Optimization
fun selectionSort(arr: IntArray) {
for (i in arr.indices) {
var minIdx = i
for (j in i + 1 until arr.size) {
if (arr[j] < arr[minIdx]) minIdx = j
}
// Single swap operation using XOR
if (i != minIdx) {
arr[i] = arr[i] xor arr[minIdx]
arr[minIdx] = arr[i] xor arr[minIdx]
arr[i] = arr[i] xor arr[minIdx]
}
}
}
Comparison with Other Sorting Algorithms
Algorithm | Time Complexity (Average) | Space Complexity | Stable | In-Place |
---|---|---|---|---|
Selection Sort | O(n²) | O(1) | No | Yes |
Bubble Sort | O(n²) | O(1) | Yes | Yes |
Quick Sort | O(n log n) | O(log n) | No | Yes |
Merge Sort | O(n log n) | O(n) | Yes | No |
Advantages and Disadvantages of Selection Sort
Advantages:
- Simple to understand and implement
- Performs well on small datasets
- Requires no additional memory
Disadvantages:
- Inefficient for large datasets due to O(n²) time complexity
- Not a stable sorting algorithm (does not preserve the order of equal elements)
Conclusion
Selection Sort is a straightforward sorting algorithm best suited for small datasets or learning purposes. While it may not match the efficiency of more advanced algorithms like Merge Sort or Quick Sort, its simplicity and in-place sorting make it a useful tool in specific scenarios.
Top comments (0)