How to Do Selection Sort in Python

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:

1. Find the minimum element from the unsorted portion of the array.
2. Swap it with the first element of the unsorted portion.
3. Move the boundary between the sorted and unsorted sections to include the newly sorted element.
4. 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 element 64.

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 element 25.

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 with 25.

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:

1. Inefficient for large datasets: Its O(n²) time complexity makes it slow for sorting large arrays compared to algorithms like quicksort or mergesort.
2. 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.
3. 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!

Read the following articles to learn how to implement Selection Sort:

In C++ – How to do Selection Sort in C++

In JavaScript – How to do Selection Sort in JavaScript

In Java – How to do Selection Sort in Java

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!