Selection Sort is one of the most basic and easiest-to-understand sorting algorithms in computer science. This article provides a step-by-step guide on how Selection Sort works and how to implement it in Python.
Table of Contents
Open Table of Contents
Overview of Selection Sort
Selection Sort works by dividing the input array or list into two parts - the sorted part and the unsorted part. It repeatedly searches for the minimum element in the unsorted part and swaps it with the leftmost element in the unsorted part.
The key steps involved in Selection Sort are:
-
Set the first element as minimum.
-
Compare minimum with the second element. If the second element is smaller than minimum, assign minimum to the second element.
-
Compare minimum with the third element. Again, if the third element is smaller, then assign minimum to the third element otherwise do nothing. The minimum is again compared to the fourth element and so on.
-
After each iteration, minimum is placed in the front of the unsorted list.
-
This process continues iterating through the list until all the elements are placed at their correct positions.
The main advantage of Selection Sort is its simplicity and ease of implementation. The space complexity is O(1) as it only requires a single additional memory space. The time complexity is O(n2) as there are two nested iterations.
Python Implementation of Selection Sort
Here is a step-by-step implementation of the Selection Sort algorithm in Python:
1. Define the selection_sort function
def selection_sort(arr):
The selection_sort function takes the array or list that needs to be sorted as the argument.
2. Traverse through array elements
We need two for loops to traverse through the array elements. The outer for loop selects an element as minimum and inner for loop compares the minimum to the next elements.
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
3. Find minimum element
We compare the minimum element with the next element in the array and swap if the next element is smaller.
if arr[min_idx] > arr[j]:
min_idx = j
4. Swap minimum element with first element
After we have found the minimum element, we swap it with the first element.
arr[i], arr[min_idx] = arr[min_idx], arr[i]
5. Complete selection_sort function
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
6. Test the selection sort code
We test the code on an example array:
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print(arr)
Output:
[11, 12, 22, 25, 64]
The selection_sort function was able to sort the array in ascending order.
Analysis of Selection Sort
Now let’s analyze the time and space complexity of Selection Sort:
Time Complexity
-
Best Case Complexity: O(n2) - When the array is already sorted, the outer loop runs for n iterations whereas the inner loop does not execute at all.
-
Average Case Complexity: O(n2) - Outer loop runs n times and the inner loop runs (n-i) times due to which the overall complexity is n*(n-1)/2 ~ n2
-
Worst Case Complexity: O(n2) - When the array is reverse sorted, the inner loop runs maximum number of times for every iteration of outer loop causing O(n2) complexity.
So in all cases, the time complexity of Selection Sort is O(n2).
Space Complexity
- O(1) - Selection Sort requires constant O(1) space as the only extra memory required is for temp variable used in swapping.
So Selection Sort makes O(n2) comparisons and swaps to sort the array. The good thing is there are minimum number of swaps required.
Optimized Selection Sort in Python
The basic selection sort algorithm can be optimized by stopping the inner loop early if the minimum element has already been found.
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
In this implementation, we are breaking out of the inner loop as soon as we find an element smaller than the current minimum. This reduces the number of comparisons in cases where the minimum element is towards the start of the unsorted array.
When to Use Selection Sort?
The key advantages of Selection Sort are:
- Simple implementation
- Efficient for smaller arrays
- Minimum swaps required
- Works well even for reverse sorted arrays
- In-place sorting algorithm, doesn’t require extra space
Selection Sort is useful when:
- A small array needs to be sorted
- Cost of swapping does not matter
- Checking of all elements is compulsory
- Easy to implement in any programming language
It is however not suitable for sorting large arrays as its average and worst case complexity is O(n2).
Applications of Selection Sort
Some real-world applications where Selection Sort is a good choice:
- Sorting small arrays where number of writes is critical
- Sorting an array which is already almost sorted
- Selecting the kth smallest element in an array
For example, in graphics algorithms, we need to find the kth smallest element repeatedly to render the scene. Selection sort can find the kth order statistic in O(n) time.
Conclusion
In this article, we learned how the Selection Sort algorithm works by dividing the array into sorted and unsorted parts. We looked at a Python implementation to sort the array by repeatedly finding the minimum element and placing it in the sorted part.
The time complexity of Selection Sort is O(n2) in all cases. It is quite efficient for small arrays and is easier to implement than other quadratic sorting algorithms like Insertion Sort and Bubble Sort. The space complexity is O(1).
Selection Sort has several applications where cost of swap is very high and number of writes needs to be minimized. It works well on almost sorted data. Though not suitable for large data, Selection Sort is fundamental for understanding the concept of sorting.