Selection Sort Algorithm

Introduction to Selection Sort

Selection sort is a simple comparison-based sorting algorithm. It works by repeatedly selecting the minimum element from the unsorted portion of the array and swapping it with the first unsorted element. This process continues until the entire array is sorted. Selection sort has a time complexity of O(n^2) and is not suitable for large data sets.

---

Step-by-Step Process

Consider an array with the following elements:

[64, 25, 12, 22, 11]

To sort this array using selection sort, follow these steps:

1. Find the Minimum Element: Scan the entire array to find the minimum element.
2. Swap: Swap the minimum element with the first element of the unsorted portion of the array.
3. Move to the Next Element: Move the boundary of the unsorted portion one element to the right.
4. Repeat: Repeat the process until the entire array is sorted.

Let's apply these steps to the example array:

• Initial array: [64, 25, 12, 22, 11]
• Step 1: Find minimum element (11) and swap with 64 -> [11, 25, 12, 22, 64]
• Step 2: Find minimum element (12) and swap with 25 -> [11, 12, 25, 22, 64]
• Step 3: Find minimum element (22) and swap with 25 -> [11, 12, 22, 25, 64]
• Step 4: Find minimum element (25) and swap with 25 -> [11, 12, 22, 25, 64]
• Step 5: Array is already sorted.

---

Pseudo Code for Selection Sort

Below is the pseudo code for the selection sort algorithm:

function selectionSort(array)
    n = length(array)
    for i = 0 to n - 1 do
        minIndex = i
        for j = i + 1 to n - 1 do
            if array[j] < array[minIndex] then
                minIndex = j
            end if
        end for
        swap(array[i], array[minIndex])
    end for
end function

Explanation:

• Initialize: The selectionSort function starts by iterating through the array from the first to the last element.
• Find Minimum: For each element, it finds the minimum element in the unsorted portion of the array.
• Swap: The minimum element is swapped with the first unsorted element.
• Repeat: The process repeats until the entire array is sorted.

---

Python Program to Implement Selection Sort

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

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

This Python program defines a function to perform selection sort on an array. The function iterates through the array, finds the minimum element in the unsorted portion, swaps it with the first unsorted element, and repeats the process until the array is sorted.