Selection Sort Algorithm

Selection Sort is one of the simplest and most intuitive sorting algorithms. It is an in-place, comparison-based algorithm that divides the input list into two parts: the sublist of items already sorted (which is built up from left to right at the front of the list), and the sublist of items remaining to be sorted, occupying the rest of the list.

How Selection Sort Works:

1. Initial Setup:
   • The algorithm maintains two subarrays within the given array:
     • The first subarray is already sorted.
     • The second subarray is unsorted.
2. Finding the Minimum Element:
   • During each iteration, the smallest element from the unsorted subarray is selected and moved to the sorted subarray.
   • The algorithm scans the unsorted subarray to find the smallest (or largest, depending on the order of sorting) element.
3. Swapping:
   • Once the minimum element is found, it is swapped with the first element of the unsorted subarray.
   • This process places the smallest element at the beginning of the unsorted subarray, effectively expanding the sorted subarray by one element.
4. Repeat:
   • The algorithm then moves the boundary between the sorted and unsorted subarrays one element to the right and repeats the process for the next position in the list.

Characteristics of Selection Sort:

• Time Complexity:
  • Best Case: O(n²)
  • Average Case: O(n²)
  • Worst Case: O(n²)
  • Selection Sort performs poorly on large lists because of its O(n²) time complexity. It makes n(n-1)/2 comparisons in the worst case.
• Space Complexity:
  • Selection Sort is an in-place sorting algorithm, meaning it requires only a constant amount O(1) of additional memory space.
• Stability:
  • Selection Sort is not a stable sort. Stability refers to preserving the relative order of records with equal keys (i.e., values). If stability is needed, a modified version of the algorithm can be used.

Code Example

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Assume the minimum is the first element
        min_idx = i
        # Traverse the array to find the actual minimum element in the remaining unsorted array
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # Swap the found minimum element with the first element
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# Example usage
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Sorted array is:", sorted_arr)

Output

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

Code Explanation

Function Definition

def selection_sort(arr):

• The function selection_sort is defined to take a single list arr as its parameter.

Length of Array

    n = len(arr)

• The variable n stores the length of the input list arr.

Outer Loop

    for i in range(n):

• The outer loop iterates over each element of the array. The index i represents the current position in the sorted portion of the array.

Initialize Minimum Index

        min_idx = i

• The variable min_idx is initialized to the current index i. This variable will hold the index of the smallest element found in the unsorted portion of the array.

Inner Loop

        for j in range(i+1, n):

• The inner loop iterates over the unsorted portion of the array, starting from i + 1 to n. The index j represents the current position in the unsorted portion of the array.

Finding the Minimum Element

            if arr[j] < arr[min_idx]:
                min_idx = j

• If an element at index j is smaller than the current minimum element (found at min_idx), then min_idx is updated to j.

Swapping Elements

        arr[i], arr[min_idx] = arr[min_idx], arr[i]

• After finding the smallest element in the unsorted portion of the array, it is swapped with the element at the current position i.

Return Statement

    return arr

• The sorted array arr is returned.

Example Usage

arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Sorted array is:", sorted_arr)

• An example list arr is sorted using the selection_sort function, and the sorted list is printed.