Python Program For Selection Sort (With Code + Easy Explanation)

In this guide, you will learn about the Python program for selection sort.

Sorting is a fundamental operation in computer science, and there are several algorithms available to accomplish this task efficiently.

One such algorithm is selection sort, which repeatedly selects the smallest element from the unsorted portion of the array and swaps it with the element at the beginning of the sorted portion.

In this article, we will dive into the details of implementing the selection sort algorithm using Python.

Selection sort is a simple comparison-based sorting algorithm. It divides the input array into two parts

1. The sorted portion at the beginning
2. And the unsorted portion at the end

The algorithm repeatedly selects the smallest element from the unsorted portion and swaps it with the element at the beginning of the sorted portion.

This process continues until the entire array is sorted.

How does Selection Sort work?

The selection sort algorithm works in the following steps:

1. Find the minimum element in the unsorted portion of the array.
2. Swap the minimum element with the first element in the unsorted portion.
3. Expand the sorted portion by one element.
4. Repeat steps 1-3 until the entire array is sorted.

To implement the selection sort algorithm in Python, we can follow these steps:

1. Define a function, let’s call it selection_sort(), that takes an array as input.
2. Iterate through the array from the first element to the second-to-last element.
3. Find the index of the minimum element in the remaining unsorted portion of the array.
4. Swap the minimum element with the current element.
5. Repeat steps 3-4 until the array is sorted.

Here’s a Python program that implements the selection sort algorithm.

Python Program For Selection Sort

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]

# Test the selection_sort function
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array:", arr)

You can run this code on our free Online Python Compiler.

Output

Let’s consider an example to understand how the selection sort algorithm works. Suppose we have an array [64, 25, 12, 22, 11] that we want to sort in ascending order using selection sort.

Step 1: Sorting an Array using Selection Sort

The minimum element in the unsorted portion is 11, located at index 4.

Swap it with the first element (64).

Step 2: Sorting an Array using Selection Sort

The minimum element in the remaining unsorted portion is 12, located at index 2.

Swap it with the second element (25).

Step 3: Sorting an Array using Selection Sort

The minimum element in the remaining unsorted portion is 22, located at index 3.

Swap it with the third element (25).

Step 4: Sorting an Array using Selection Sort

The minimum element in the remaining unsorted portion is 25, located at index 3.

Swap it with the fourth element (25) itself.

Step 5: Sorting an Array using Selection Sort

The minimum element in the remaining unsorted portion is 64, located at index 4.

Since it is already at the correct position, we need no swapping.

The array is now sorted in ascending order.

The time complexity of selection sort is O(n²), where n is the number of elements in the array.

This is because, in each iteration, we have to find the minimum element from the remaining unsorted portion of the array, which takes O(n) time.

Since we repeat this process n-1 times, the overall time complexity is O(n²).

Selection sort has a few advantages and disadvantages.

Advantages of selection sort in Python

• Simple implementation.
• In-place sorting algorithm (requires only a constant amount of additional memory).
• Performs well for small arrays or when the memory write is a costly operation.

Disadvantages of selection sort in Python

• Inefficient for large datasets due to its quadratic time complexity.
• Not a stable sorting algorithm (the relative order of equal elements might change).

Q: What is the purpose of selection sort in Python?

The purpose of selection sort is to sort an array or a list of elements in ascending or descending order.

Q: How does selection sort differ from other sorting algorithms?

Unlike other sorting algorithms like merge sort or quicksort, selection sort is an in-place sorting algorithm.

It does not require additional memory proportional to the input size.

Q: Can selection sort handle large datasets efficiently?

No, selection sort is not efficient for large datasets.

Its time complexity of O(n²) makes it impractical for sorting large amounts of data.

Q: Is selection sort a stable sorting algorithm?

No, selection sort is not a stable sorting algorithm.

It means that the relative order of equal elements might change during the sorting process.

Q: How can we optimize selection sort in python?

One way to optimize selection sort is by implementing the “optimized selection sort” variant.

This variant reduces the number of swaps by finding both the minimum and maximum elements in each iteration.

Q: Are there any real-world applications of selection sort?

Selection sort is rarely used in practical scenarios due to its inefficiency for large datasets.

For real-world applications, we prefer other sorting algorithms like merge sort, quicksort, or heapsort.

In this article, we explored the selection sort algorithm and its implementation in Python.

Selection sort is a simple sorting algorithm that repeatedly selects the smallest element and places it in the correct position.

While it has a time complexity of O(n²) and is not efficient for large datasets, it is still a valuable algorithm to understand as it forms the foundation for more advanced sorting algorithms.