Selection Sort

Selection Sort is a simple comparison-based sorting algorithm that works by repeatedly finding the minimum (or maximum) element from the unsorted part of the list and moving it to the beginning (or end) of the sorted part. It is an elementary sorting algorithm that is not suitable for large datasets due to its high time complexity.

AlgorithmEdit

The Selection Sort algorithm works as follows:

Find the minimum (or maximum) element in the unsorted part of the list and swap it with the first unsorted element.
Move the boundary between the sorted and unsorted parts of the list one element to the right.
Repeat steps 1-2 until the entire list is sorted.

PseudocodeEdit

Here is a simple pseudocode for Selection Sort:

function selectionSort(arr)
  for i = 0 to length(arr) - 1
    minIndex = i
    for j = i + 1 to length(arr) - 1
      if arr[j] < arr[minIndex]
        minIndex = j
      end if
    end for
    if minIndex != i
      swap(arr[i], arr[minIndex])
    end if
  end for
end function

Time ComplexityEdit

The time complexity of Selection Sort is O(n^2) in the worst, average, and best cases, where n is the number of elements in the list. This is because the algorithm performs n-1 comparisons for the first element, n-2 for the second, and so on, resulting in (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparisons in total.

Space ComplexityEdit

The space complexity of Selection Sort is O(1) because it is an in-place sorting algorithm, meaning it does not require additional memory for temporary storage.

C++ ExampleEdit

Here is an example implementation of Selection Sort in C++:

#include <iostream>
#include <vector>

void selectionSort(std::vector < int > & arr) {
    size_t n = arr.size();
    for (size_t i = 0; i < n - 1; ++i) {
        size_t minIndex = i;
        for (size_t j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            std::swap(arr[i], arr[minIndex]);
        }
    }
}

int main() {
    std::vector < int > arr = {
        64,
        34,
        25,
        12,
        22,
        11,
        90
    };
    selectionSort(arr);

    std::cout << "Sorted array is: ";
    for (int i: arr) {
        std::cout << i << " ";
    }

    return 0;
}