Selection Sort

Is a straightforward and intuitive sorting algorithm. It works by dividing the input list into two portions: the sorted portion and the unsorted portion. The algorithm repeatedly selects the smallest (or largest, depending on the sorting order) element from the unsorted portion and moves it to the end of the sorted portion. This process continues until the entire list is sorted.

Step-by-Step Explanation

1. Initialization: We start with the entire array considered as the unsorted part. The sorted part initially contains no elements.
2. Finding the Minimum: We iterate the unsorted part to find the minimum element. To do this, we maintain an index variable called “minIndex” and set it to the index of the first element of unsorted part. Then, we compare this element with all other elements in the unsorted part. If we find an element smaller than one at “minIndex”, we update “minIndex” to the index of that smller element.
3. Swapping: After finding the minimum element in the unsorted part, we swap it with the first element in the unsorted part. This effectively moves the minimum element to the end of the sorted part. We repeat this process for each element in the unsorted part.
4. Advancing the Boundary: We consider the boundary between the sorted and unsorted parts to have moved one step to the right. The sorted part grows, and the unsorted part shrinks.
5. Repeat: We repeat steps 2 to 4 until the entire array is sorted. This means we will have successfully moved every element from the unsorted part to the sorted part, one at a time.

Working

Lets consider the following array as an example:

arr[] = {64, 25, 12, 22, 11}

First Pass:

• For the first position in the sorted array, the whole array is traversed from index 0 to 4 sequentially. The first position where 64 is stored presently, after traversing whole array it is clear that 11 is the lowest value.
• Thus, replace 64 with 11. After one iteration 11, which happens to be the least value in the array, tends to appear in the first position  of the sorted list.
• arr = { 11, 25, 12, 22, 64}

Second Pass:

• For the second position, where 25 is present, again traverse the rest of the array in a sequential manner.
• After traversing, we found that 12 is the second lowest value in the array and it should appear at the second place in the array, thus swap these values.
• arr = { 11, 12, 25, 22, 64}

Third Pass:

• Now, for third place, where 25 is present again traverse the rest of the array and find the third least value present in the array.
• While traversing, 22 came out to be the third least value and it should appear at the third place in the array, thus swap 22 with element present at third position.
• arr = { 11, 12, 22, 25, 64}

Fourth Pass:

• Similarly, for fourth position traverse the rest of the array and find the fourth least element in the array.
• As 25 is the 4th lowest value hence, it will place at the fourth position.
• arr = { 11, 12, 22, 25, 64}

Fifth Pass:

• At last the largest value present in the array automatically get placed at the last position in the array.
• The resulted array is the sorted array.
• arr = { 11, 12, 22, 25, 64}

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 the minimum element with the first element of the unsorted part
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    std::cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}
// Output
Sorted array: 11 12 22 25 64 

Complexity

Worst Case (Reverse Order):

In the worst-case scenario, Selection Sort makes approximately n-1 comparisons for the first element, n-2 comparisons for the second element, and so on, until the last element, which makes just one comparison. This results in the sum of the first n-1 positive integers, which is (n-1) * n / 2. Since we simplify it to (n^2 - n) / 2, the time complexity is still O(n^2).

Best Case (Already Sorted):

Surprisingly, the best-case time complexity of Selection Sort is also O(n^2). This occurs because the algorithm still makes the same number of comparisons, even if the elements are already in sorted order. It simply finds the minimum (or maximum) element in each pass and swaps it with itself.

Average Case:

The average-case time complexity is also O(n^2). Even though Selection Sort makes fewer comparisons if some elements are already in their correct positions, it does not significantly affect the overall time complexity.

Space Complexity:

O(1) as the only extra memory used for temporary variables whole swapping two values in Array.

Advantages

• Simple and easy to understand.
• Works well with small datasets.

Disadvantages

• Selection sort has a time complexity of O(n^2).
• Does not work well on large datasets.
• Does not preserve the relative order of items with equal keys which means it is not stable.