Selection Sort Explanation

Selection Sort is a simple comparison-based sorting algorithm. It works by repeatedly selecting the minimum (or maximum) element from the unsorted portion of the array and swapping it with the first element of the unsorted section. The algorithm divides the array into a sorted and unsorted section and systematically reduces the size of the unsorted section.

Algorithm Steps:

1. Start at the beginning of the array and find the smallest (or largest) element in the unsorted section.
2. Swap the smallest element with the first element of the unsorted section.
3. Move the boundary between the sorted and unsorted sections by one element.
4. Repeat the process until the entire array is sorted.

Advantages:

• Simple to implement and understand.
• Performs well on small arrays.
• Requires no additional memory, as it sorts in place.

Disadvantages:

• Inefficient for large datasets, with a time complexity of O(n^2).
• Poor performance compared to more efficient algorithms like Quick Sort or Merge Sort.
• The number of comparisons does not depend on the input data (always O(n^2)).

Code Examples

C++ Code:

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i; // Assume the first element is the minimum
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j; // Update the index of the minimum element
            }
        }
        // Swap the found minimum element with the first element of the unsorted part
        swap(arr[minIdx], arr[i]);
    }
}

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

Java Code:

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i; // Assume the first element is the minimum
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j; // Update the index of the minimum element
                }
            }
            // Swap the found minimum element with the first element of the unsorted part
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }

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

Python Code:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i  # Assume the first element is the minimum
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j  # Update the index of the minimum element
        # Swap the found minimum element with the first element of the unsorted part
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

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

Time Complexity:

• Best case: O(n^2)
• Average case: O(n^2)
• Worst case: O(n^2)

Selection Sort is simple but inefficient for large datasets, and its number of comparisons is fixed, regardless of the data's initial order.