Selection Sort in Python

 

Selection sort is an algorithm that sorts a list by repeatedly selecting the minimum element (or maximum element, depending on the desired order) from the unsorted portion of the list and placing it at the beginning (or end). Here is an implementation of selection sort in Python:

def selection_sort(lst):
    # Iterate through the list
    for i in range(len(lst)):
        # Find the minimum element in the unsorted portion of the list
        min_index = i
        for j in range(i + 1, len(lst)):
            if lst[j] < lst[min_index]:
                min_index = j
        
        # Swap the minimum element with the first element of the unsorted portion
        lst[i], lst[min_index] = lst[min_index], lst[i]

# Test the selection sort function
lst = [5, 4, 3, 2, 1]
selection_sort(lst)
print(lst)  # Output: [1, 2, 3, 4, 5]

Selection sort has a time complexity of O(n^2) in the worst case, which makes it less efficient for large lists compared to other sorting algorithms such as quicksort or mergesort. However, it is simple to implement and can be useful for small lists or as a teaching tool.

Note: In the above implementation, the list is sorted in ascending order. To sort the list in descending order, simply change the comparison operator from < to > in the inner loop.

Using Recursion

def selection_sort_recursive(lst, start_index):
    # Base case: if the start index is out of range, the list is sorted
    if start_index >= len(lst):
        return
    
    # Find the minimum element in the unsorted portion of the list
    min_index = start_index
    for i in range(start_index + 1, len(lst)):
        if lst[i] < lst[min_index]:
            min_index = i
    
    # Swap the minimum element with the first element of the unsorted portion
    lst[start_index], lst[min_index] = lst[min_index], lst[start_index]
    
    # Recursively call the function on the shortened list
    selection_sort_recursive(lst, start_index + 1)

# Test the selection sort function
lst = [5, 4, 3, 2, 1]
selection_sort_recursive(lst, 0)
print(lst)  # Output: [1, 2, 3, 4, 5]

This implementation works by sorting the list in a similar way to the iterative version of selection sort, but instead of using a loop to iterate through the list, it uses recursion to shorten the list by one element at each step. The base case for the recursion is when the start index is out of range, which means that the list is already sorted.

As with the iterative version of selection sort, this implementation has a time complexity of O(n^2) in the worst case, which makes it less efficient for large lists compared to other sorting algorithms. However, it can be a useful exercise to understand the concept of recursion and how it can be applied to sorting algorithms.