Selection Sort

Selection Sort

Description: Selection sort is a simple comparison-based sorting algorithm that works by dividing the input list into two parts: a sorted part and an unsorted part. It repeatedly selects the smallest (or largest, depending on sorting order) element from the unsorted part and moves it to the end of the sorted part.

How It Works

1. Initialization: Start with the entire list as unsorted.
2. Find Minimum: Look for the smallest element in the unsorted portion of the list.
3. Swap: Swap this smallest element with the first element of the unsorted part.
4. Move Boundary: The boundary between the sorted and unsorted parts is moved one element to the right.
5. Repeat: Repeat the process until the entire list is sorted.

Time Complexity

• Worst Case: $O(n^2)$ — occurs when the array is sorted in reverse order.
• Average Case: $O(n^2)$
• Best Case: $O(n^2)$ — even if the array is already sorted, the algorithm still checks every element.

Space Complexity

• Space Complexity: $O(1)$ — selection sort is an in-place sorting algorithm, meaning it requires a constant amount of additional storage space.

Stability

• Stability: Selection sort is not a stable sort. Equal elements may not maintain their relative order after sorting.

Example Code

Here's a C++ implementation of selection sort:

#include <iostream>
using namespace std;

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

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Explanation of the Code

1. Function Definition: The selectionSort function takes an array and its size as parameters.
2. Outer Loop: Iterates through each element in the array up to the second-to-last element.
3. Inner Loop: Searches for the smallest element in the unsorted portion of the array.
4. Swap: Once the smallest element is found, it swaps this element with the current position in the outer loop.
5. Output: After sorting, the program prints the sorted array.

Conclusion

Selection sort is easy to understand and implement, making it a great educational tool. However, its $O(n^2)$ time complexity makes it inefficient for large datasets. For practical applications, more efficient algorithms like quick sort or merge sort are preferred.