Example and Analysis of Selection Sort
Let’s take a closer look at Selection Sort through an example and analyze its performance in terms of time and space complexity.
Example Walkthrough of Selection Sort
Suppose we have an unsorted array:
[29, 10, 14, 37, 13]
We will use Selection Sort to sort this array in ascending order. The goal is to find the smallest (or largest) element from the unsorted portion of the array and place it in the correct position in the sorted portion.
Step-by-step Process:
Initial Array:
[29, 10, 14, 37, 13]
First Pass (i = 0):
-
The unsorted portion is the entire array: [29, 10, 14, 37, 13].
-
Find the smallest element in this unsorted portion:
- Compare 29 with 10 → 10 is smaller.
- Compare 10 with 14 → 10 is smaller.
- Compare 10 with 37 → 10 is smaller.
- Compare 10 with 13 → 10 is smaller.
-
The smallest element is 10 at index 1.
-
Swap the smallest element (10) with the first element (29).
After the first pass, the array becomes:
[10, 29, 14, 37, 13]
Second Pass (i = 1):
-
The unsorted portion is [29, 14, 37, 13].
-
Find the smallest element in this unsorted portion:
- Compare 29 with 14 → 14 is smaller.
- Compare 14 with 37 → 14 is smaller.
- Compare 14 with 13 → 13 is smaller.
-
The smallest element is 13 at index 4.
-
Swap the smallest element (13) with the element at index 1 (29).
After the second pass, the array becomes:
[10, 13, 14, 37, 29]
Third Pass (i = 2):
-
The unsorted portion is [14, 37, 29].
-
Find the smallest element in this unsorted portion:
- Compare 14 with 37 → 14 is smaller.
- Compare 14 with 29 → 14 is smaller.
-
The smallest element is 14 at index 2. Since it's already in the correct position, no swap is needed.
After the third pass, the array remains:
[10, 13, 14, 37, 29]
Fourth Pass (i = 3):
-
The unsorted portion is [37, 29].
-
Find the smallest element in this unsorted portion:
- Compare 37 with 29 → 29 is smaller.
-
The smallest element is 29 at index 4.
-
Swap the smallest element (29) with the element at index 3 (37).
After the fourth pass, the array becomes:
[10, 13, 14, 29, 37]
Fifth Pass (i = 4):
- The unsorted portion is just
[37], so no comparison or swapping is necessary.
The array is now fully sorted:
[10, 13, 14, 29, 37]
Time Complexity Analysis
To analyze the time complexity of Selection Sort, we consider the number of comparisons and swaps the algorithm performs:
Outer Loop:
- The outer loop runs n times, where n is the size of the array.
Inner Loop:
- In each iteration of the outer loop, the inner loop searches through the remaining unsorted portion of the array to find the smallest element.
- In the first pass, the inner loop runs n - 1 times.
- In the second pass, the inner loop runs n - 2 times.
- This continues until the outer loop reaches the last element, where the inner loop runs just 1 time.
Thus, the total number of comparisons is:
(n−1)+(n−2)+(n−3)+…+1=2n(n−1)=O(n2)
So, the time complexity of Selection Sort is:
- Best Case: O(n²) — This occurs because the algorithm still performs the same number of comparisons, regardless of whether the array is already sorted or not.
- Worst Case: O(n²) — In the worst case, the array is in reverse order, but the number of comparisons is still O(n²).
- Average Case: O(n²) — On average, the algorithm also performs O(n²) comparisons.
Why is it O(n²) in all cases?
- Selection Sort does not take advantage of any existing ordering in the array, so the number of comparisons remains the same whether the array is partially sorted or completely unsorted.
Swaps:
- Selection Sort performs at most n - 1 swaps, since one element is placed in its correct position in each iteration of the outer loop. However, the number of swaps is significantly less than the number of comparisons.
Space Complexity Analysis
- Space Complexity: O(1)
- Selection Sort is an in-place sorting algorithm, meaning it does not require any additional memory outside of the input array. It only uses a few extra variables for looping and swapping elements, making its space complexity constant, O(1).
Advantages of Selection Sort
- Simplicity: Selection Sort is easy to understand and implement.
- In-place Sorting: It doesn't require any extra memory (apart from a few temporary variables), which makes it space-efficient.
- Fewer Swaps: It only performs n - 1 swaps, which may be useful if the cost of swapping is higher than comparing elements.
Disadvantages of Selection Sort
- Inefficient for Large Datasets: Selection Sort has a time complexity of O(n²), making it inefficient for large arrays. Other algorithms like Merge Sort or Quick Sort are more efficient for large datasets.
- Not Adaptive: It does not take advantage of partially sorted data, meaning its time complexity is always O(n²) regardless of the input.
- Not Stable: Selection Sort is not a stable sorting algorithm. This means that equal elements might not maintain their relative order after sorting.
Conclusion
Selection Sort is a simple and easy-to-understand sorting algorithm, but its O(n²) time complexity makes it impractical for large arrays. It is mainly useful for small datasets or as a teaching tool for understanding basic sorting principles. In practice, more efficient algorithms like Merge Sort, Quick Sort, or Heap Sort are typically used for sorting larger datasets.