What is Selection Sort?

Selection Sort is a simple comparison-based sorting algorithm. It works by repeatedly finding the minimum (or maximum) element from the unsorted part of the array and placing it at the beginning (or end). The algorithm maintains two parts of the array:

• A sorted part (initially empty).
• An unsorted part (initially the whole array).

How Selection Sort Works ?

Selection Sort works by dividing the input array into two parts: the sorted part (built up from left to right) and the unsorted part (which becomes progressively smaller). In each iteration, the algorithm selects the smallest (or largest, depending on sorting order) element from the unsorted part and swaps it with the leftmost unsorted element, thus expanding the sorted part by one element.

Step-by-step explanation:

1. Find the minimum element in the unsorted array.
2. Swap it with the element at the first position of the unsorted part.
3. Move the boundary between the sorted and unsorted parts one element to the right.
4. Repeat until the whole array is sorted.

Example of Selection Sort

Let’s take an example of sorting the array [64, 25, 12, 22, 11]:

1. Initial List: [64, 25, 12, 22, 11]
2. First Pass:
   • Find the minimum element in the array: 11.
   • Swap it with the first element: [11, 25, 12, 22, 64].
3. Second Pass:
   • Find the minimum element in the remaining unsorted part [25, 12, 22, 64]: 12.
   • Swap it with the second element: [11, 12, 25, 22, 64].
4. Third Pass:
   • Find the minimum element in the remaining unsorted part [25, 22, 64]: 22.
   • Swap it with the third element: [11, 12, 22, 25, 64].
5. Fourth Pass:
   • The minimum element in the remaining unsorted part [25, 64] is 25.
   • No swap needed, the array is now sorted: [11, 12, 22, 25, 64].

C++ Program to implement Selection Sort Algorithm

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        swap(arr[minIdx], arr[i]);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    cout << "Sorted array: ";
    printArray(arr, n);
    return 0;
}

Java Program to implement Selection Sort Algorithm

public class Main {
    public static void selectionSort(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIdx = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int arr[] = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("Sorted array: ");
        printArray(arr);
    }
}

Python Program to implement Selection Sort Algorithm

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]

def print_array(arr):
    print(" ".join(map(str, arr)))

if __name__ == "__main__":
    arr = [64, 25, 12, 22, 11]
    selection_sort(arr)
    print("Sorted array:")
    print_array(arr)

Properties of Selection Sort

• Time Complexity:
  • Best Case: O(n²)
  • Average Case: O(n²)
  • Worst Case: O(n²)
• Space Complexity: O(1) - Selection Sort is an in-place sorting algorithm.
• Stability: Selection Sort is not a stable sorting algorithm because it may change the relative order of equal elements.
• Adaptability: Selection Sort is not adaptive. It always performs O(n²) comparisons, even if the array is already sorted.

When to Use Selection Sort

Selection Sort is generally not preferred for large datasets due to its O(n²) time complexity. However, it can be useful in scenarios where memory usage is critical because it uses a constant amount of memory.