Principles of Selection Sort

Selection Sort is based on the simple principle of repeatedly selecting the smallest (or largest) element from the unsorted portion of the array and placing it at the beginning (or end) of the sorted portion. This process is repeated until the entire array is sorted.

Algorithm

1. Start with the unsorted portion of the array.
2. Iterate through the unsorted portion to find the minimum (or maximum) element.
3. Swap the minimum (or maximum) element with the first (or last) element of the unsorted portion, effectively expanding the sorted portion.
4. Repeat steps 2 and 3 for the remaining unsorted portion until the entire array is sorted.

Code

#include <iostream>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // Swap arr[i] with the minimum element
        std::swap(arr[i], arr[minIndex]);
    }
}

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

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::cout << "Original array: ";
    printArray(arr, n);

    selectionSort(arr, n);

    std::cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Complexity Analysis

• Time Complexity: O(n ^ 2), where n is the number of elements in the array.
  • Because for each element in the array. we iterate through the remaining elements to find the minimum (or maximum) element.
• Space Complexity: O(1)
  • It doesn't require additional space proportional to the input size.