Selection Sort in Descending Order in Python

1. Introduction

In this blog post, we will learn how to write a Python program to sort an array of integers in a Descending Order using the Selection Sort algorithm.

Selection Sort is a straightforward and comparison-based sorting algorithm. The fundamental concept behind this algorithm is to divide the list into two segments: a sorted portion and an unsorted one. During each iteration, the largest element from the unsorted section is identified and swapped with the first unsorted element, thereby extending the sorted section. We'll break down this algorithm in Python, focusing on sorting in descending order.

2. Program Overview

1. selection_sort(): The main function that implements the selection sort algorithm in descending order.

2. print_list(): A utility function to display the contents of the list.

3. A sample list to showcase the sorting process.

3. Code Program

def selection_sort(arr):
    n = len(arr)
    
    # Traverse through all list elements
    for i in range(n):
        # Find the maximum element in the remaining unsorted list
        max_idx = i
        for j in range(i+1, n):
            if arr[j] > arr[max_idx]:
                max_idx = j
                
        # Swap the found maximum element with the first element
        arr[i], arr[max_idx] = arr[max_idx], arr[i]

def print_list(arr):
    for i in arr:
        print(i, end=" ")
    print()

# Driver code to test the functions
if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
    print("Original list is:")
    print_list(arr)
    
    selection_sort(arr)
    
    print("\nSorted list in descending order is:")
    print_list(arr)

Output:

Original list is:
64 34 25 12 22 11 90 

Sorted list in descending order is:
90 64 34 25 22 12 11 

4. Step By Step Explanation

1. selection_sort(): This function employs the Selection Sort method to sort the list in descending order. The outer loop covers all elements, while the inner loop hunts for the largest value in the unsorted segment. When identified, the largest element is swapped with the initial unsorted element.

2. print_list(): A helper function to display list elements.

3. Driver code: This illustrates the functionality using a sample list.

While the Selection Sort algorithm is intuitive and simple, it's worth noting that its O(n^2) time complexity makes it less suitable for long lists. The essence of this method revolves around selecting the largest element from the unsorted segment and placing it in the sorted portion.