Selection Sort Program in Python

Python - Selection Sort

In this tutorial, we will implement the Selection Sort Algorithm in Python. The Selection Sort algorithm is an in-place comparison-based sorting algorithm that works by repeatedly selecting the minimum element from the unsorted portion of the list and swapping it with the element at the current position.

The algorithm divides the list into two parts: a sorted part and an unsorted part. It repeatedly selects the smallest element from the unsorted part and swaps it with the first unsorted element, moving the boundary of the sorted portion one step forward.

Python Program

def selection_sort(nlist):
    for i in range(0, len(nlist) - 1):
        smallest = i
        for j in range(i + 1, len(nlist)):
            if nlist[j] < nlist[smallest]:
                smallest = j
        nlist[i], nlist[smallest] = nlist[smallest], nlist[i]

#input list
alist = [1, 74, 96, 5, 42, 63]
print('Input List\n', alist)

#sort list
selection_sort(alist)
print('Sorted List\n', alist)

Explanation:

  1. The outer loop iterates over the entire list. For each iteration, it assumes that the current position i holds the smallest element.
  2. The inner loop compares the current element with the remaining unsorted elements. If it finds a smaller element, it updates the position of smallest.
  3. After the inner loop completes, the smallest element is swapped with the element at the current position i, thus growing the sorted part of the list by one element.
  4. This process continues until the entire list is sorted.

Output

Input List
 [1, 74, 96, 5, 42, 63]
Sorted List
 [1, 5, 42, 63, 74, 96]

Optimizing Selection Sort

Although Selection Sort is simple and works well for small lists, it is not the most efficient sorting algorithm for larger datasets due to its O(n^2) time complexity. However, we can optimize it slightly by reducing unnecessary swaps. Currently, the algorithm always swaps the current element with the smallest element, but if the smallest element is already in the correct position, no swap is necessary.

Let's modify the program to handle this case:

Optimized Python Program

def selection_sort(nlist):
    for i in range(0, len(nlist) - 1):
        smallest = i
        for j in range(i + 1, len(nlist)):
            if nlist[j] < nlist[smallest]:
                smallest = j
        if smallest != i:
            nlist[i], nlist[smallest] = nlist[smallest], nlist[i]

#input list
alist = [1, 74, 96, 5, 42, 63]
print('Input List\n', alist)

#sort list
selection_sort(alist)
print('Sorted List\n', alist)

Explanation of Optimization:

  1. The optimization ensures that a swap is only performed if the smallest element is not already at the current position i.
  2. This reduces the number of unnecessary swaps, although the algorithm's time complexity remains O(n^2).

Output

Input List
 [1, 74, 96, 5, 42, 63]
Sorted List
 [1, 5, 42, 63, 74, 96]

Additional Example: Sorting a List with Duplicate Values

In cases where the list contains duplicate values, Selection Sort still performs correctly, but let's demonstrate how it behaves with such cases:

Python Program

alist = [5, 1, 3, 3, 74, 42, 5]
selection_sort(alist)
print('Sorted List\n', alist)

Output

Sorted List
 [1, 3, 3, 5, 5, 42, 74]

Summary

In this tutorial, we learned how to implement the Selection Sort algorithm in Python. We discussed how the algorithm works by selecting the smallest element in the unsorted portion of the list and placing it in its correct position. We also introduced an optimization to reduce unnecessary swaps, and demonstrated how Selection Sort handles lists with duplicates.

Python Libraries