Selection sort is a simple comparison-based sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted portion of the array and moves it to its correct position. While not the most efficient for large datasets, selection sort is easy to understand and implement, making it a good choice for educational purposes or small datasets.
What is Selection Sort?
The selection sort divides the array into a sorted section and an unsorted section. It repeatedly selects the smallest element from the unsorted section and swaps it with the first unsorted element, growing the sorted section by one element at each step.
How Selection Sort Works:
- Find the minimum element from the unsorted portion of the array.
- Swap it with the first element of the unsorted portion.
- Move the boundary between the sorted and unsorted sections to include the newly sorted element.
- Repeat the process until the entire array is sorted.
Time Complexity:
- Best Case: O(n²)
- Worst Case: O(n²)
- Space Complexity: O(1) (in-place sorting)
Selection Sort Algorithm in Python
Here’s how you can implement selection sort in Python:
def selection_sort(arr): # Traverse through the entire array for i in range(len(arr)): # Find the minimum element in the remaining unsorted array min_idx = i for j in range(i + 1, len(arr)): if arr[j] < arr[min_idx]: min_idx = j # Swap the found minimum element with the first unsorted element arr[i], arr[min_idx] = arr[min_idx], arr[i] # Example usage: data = [64, 25, 12, 22, 11] selection_sort(data) print("Sorted array:", data)
Output:
Sorted array: [11, 12, 22, 25, 64]
Step-by-Step Explanation of Selection Sort
Let’s break down how selection sort works on the array [64, 25, 12, 22, 11]
step by step:
Step 1: Initial Array
[64, 25, 12, 22, 11] (Original array)
- Find the smallest element in the entire array:
11
- Swap
11
with the first element64
.
Array after Step 1:
[11, 25, 12, 22, 64]
Step 2: Second Pass
[11] | [25, 12, 22, 64] (First element is now part of the sorted section)
- Find the smallest element in the unsorted portion
[25, 12, 22, 64]
:12
- Swap
12
with the first unsorted element25
.
Array after Step 2:
[11, 12, 25, 22, 64]
Step 3: Third Pass
[11, 12] | [25, 22, 64] (First two elements are now sorted)
- Find the smallest element in the unsorted portion
[25, 22, 64]
:22
- Swap
22
with25
.
Array after Step 3:
[11, 12, 22, 25, 64]
Step 4: Fourth Pass
[11, 12, 22] | [25, 64] (First three elements are now sorted)
- Find the smallest element in the unsorted portion
[25, 64]
:25
- No swap is needed since
25
is already in place.
Array after Step 4:
[11, 12, 22, 25, 64]
Step 5: Final Pass
[11, 12, 22, 25] | [64] (First four elements are now sorted)
- Only one element (
64
) remains in the unsorted portion, so the array is fully sorted.
Array after Step 5:
[11, 12, 22, 25, 64] (Fully sorted array)
Limitations of Selection Sort
Selection sort is easy to understand but has some limitations:
- Inefficient for large datasets: Its O(n²) time complexity makes it slow for sorting large arrays compared to algorithms like quicksort or mergesort.
- Not a stable sort: Selection sort does not preserve the relative order of equal elements. If stability is required, a different algorithm like bubble sort or merge sort might be preferable.
- Too many comparisons: Even if the array is already sorted, selection sort will still perform O(n²) comparisons.
Conclusion
Selection sort is an intuitive and straightforward algorithm, best suited for small datasets or educational purposes. Despite its inefficiency for large datasets, it can be useful in situations where simplicity and clarity are more important than performance.
Congratulations on reading to the end of this tutorial!
For further reading on sorting algorithms in Python, go to the articles:
- How to do Insertion Sort in Python
- How to Do Bubble Sort in Python
- How to do Quick Sort in Python
- How to do Merge Sort in Python
- How to do Counting Sort in Python
- How to Do Radix Sort in Python
- How to Do Bucket Sort in Python
- How to Do Pigeonhole Sort in Python
- How To Do Comb Sort in Python
- How to Do Shell Sort in Python
- How To Do TimSort in Python
Go to the online courses page on Python to learn more about Python for data science and machine learning.
Have fun and happy researching!
Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.