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.
Algorithm
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.
Pseudocode
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 Complexity
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 Complexity
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++ Example
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;
}