Overview

Selection sort is a simple and intuitive sorting algorithm. It works by repeatedly selecting the minimum element from the unsorted portion of the list and moving it to the beginning. The algorithm divides the input list into two parts: the sorted part and the unsorted part.

Python Implementation

def selection_sort(arr):
    """
    Sorts an array in ascending order using the selection sort algorithm.

    Parameters:
    arr (list): A list of elements to be sorted.

    Returns:
    list: The sorted list.
    """
    n = len(arr)
    for i in range(n):
        # Assume the minimum is the first element of the unsorted part
        min_index = i
        for j in range(i + 1, n):
            # Update min_index if the current element is smaller
            if arr[j] < arr[min_index]:
                min_index = j
        # Swap the found minimum element with the first element
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# Example usage:
if __name__ == "__main__":
    sample_array = [64, 25, 12, 22, 11]
    print("Original array:", sample_array)
    sorted_array = selection_sort(sample_array)
    print("Sorted array:", sorted_array)

Explanation of the Program Structure

• Function Definition:The function selection_sort(arr) takes a list arr as input and sorts it in place.
• Outer Loop:The outer loop iterates through each element in the list. The index i represents the boundary between the sorted and unsorted parts.
• Inner Loop:The inner loop searches for the minimum element in the unsorted part of the list. It starts from the index i + 1 to the end of the list.
• Swap:After finding the minimum element, it swaps the minimum element with the first element of the unsorted part, thereby expanding the sorted part of the list.
• Return Statement:The sorted list is returned at the end of the function.

Example Output

When you run the program with the example array [64, 25, 12, 22, 11], the output will be:

Original array: [64, 25, 12, 22, 11]
Sorted array: [11, 12, 22, 25, 64]