Python Program to Implement Selection Sort

Selection Sort is a simple sorting algorithm that works by repeatedly selecting the minimum (or maximum) element from an unsorted part of an array and placing it at the beginning of the sorted part. This process continues until the entire array is sorted. While not the most efficient sorting algorithm for large datasets, it is easy to understand and implement.

Problem Statement

You are given an unsorted array of integers. Your task is to implement the Selection Sort in Python algorithm to sort the array in ascending order.

Python Program to Implement 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

        # Swap the found minimum element with the first element
        arr[i], arr[min_index] = arr[min_index], arr[i]

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

How it Works

1. Initial Array: Consider an unsorted array as an example: [64, 34, 25, 12, 22, 11, 90].
2. Iteration 1: The algorithm starts by searching for the minimum element in the entire array. In this case, the minimum element is 11. It’s then swapped with the element at the first position (which was 64), resulting in [11, 34, 25, 12, 22, 64, 90].
3. Iteration 2: Now, the algorithm focuses on the remaining unsorted part: [34, 25, 12, 22, 64, 90]. It finds the minimum element in this subarray (12) and swaps it with the element at the second position (which was 34), resulting in [11, 12, 25, 34, 22, 64, 90].
4. Iteration 3: Following the same process, the algorithm selects the minimum element 22 from the remaining subarray [25, 34, 22, 64, 90] and swaps it with the element at the fourth position (which was 25), resulting in [11, 12, 22, 34, 25, 64, 90].
5. Iterations Continue: The algorithm continues this process for each iteration, selecting the minimum element from the remaining unsorted portion and swapping it with the first element of that portion. As the iterations progress, the sorted part of the array expands from left to right, and the unsorted part shrinks.
6. Final Sorted Array: After completing all iterations, the sorted part of the array covers the entire array, and the unsorted part becomes empty. The array is now fully sorted: [11, 12, 22, 25, 34, 64, 90].

Key Points to Note:

• During each iteration, the algorithm identifies the minimum element from the unsorted portion of the array.
• This minimum element is then swapped with the first element of the unsorted portion, effectively expanding the sorted portion and reducing the unsorted portion.
• The process continues until the entire array is sorted.

Time Complexity:

Selection Sort’s time complexity is O(n^2), where n is the number of elements in the array. This is because for each element, it searches through the remaining unsorted part to find the minimum element, resulting in n*(n-1)/2 comparisons and swaps.

While Selection Sort is not efficient for large arrays due to its quadratic time complexity, it is relatively easy to understand and implement, making it a useful teaching tool and suitable for small datasets or scenarios where simplicity is more important than speed.

Input/ Output