Selection Sort

This sorting algorithm works by repeatedly finding the smallest element in an array and swapping it with the first element.

Use Case

The selection sort algorithm is a simple and efficient sorting algorithm that can be used in various situations. Some of the use cases of selection sort in C++ include:

• Sorting small arrays. Selection sort is a good choice for sorting small arrays because it is relatively efficient for small inputs.

• Selection sort does not require a lot of memory, so it can be used in situations where the cost of swapping elements is high.

• Sorting arrays where the order of identical elements does not matter. Selection sort is a stable sorting algorithm, which means that it does not change the relative order of identical elements in the array.

It is not very efficient for large arrays.

Here is an example of how to implement selection sort in C++:

Question statement:: https://www.codingninjas.com/studio/problems/selection-sort_981162

Notes: https://drive.google.com/file/d/1WtwEvIvqKOUR0Ys0S_SLPjfWzcT-W4_X/view

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[minIndex] > arr[j]){ // 0 > j..., 1 > j..., 2 > j..., (n-1) > j
                minIndex = j; // minIndex value will be updated, when the value at arr[minIndex(i)] is greater than the value at arr[j] index
            }
        }
        swap(arr[i], arr[minIndex]); 
    }
}

The time complexity of the selection sort algorithm is O(n^2), where n is the number of elements in the array. This is because the algorithm has two nested loops, and each loop iterates through the entire array.

The space complexity of the selection sort algorithm is O(1) because it does not require any additional memory space apart from a temporary variable used for swapping.

Here is a breakdown of the time complexity of the code:

• The outer loop iterates through the array n-1 times.

• The inner loop iterates through the array n-i-1 times.

• The total number of comparisons is the sum of the number of comparisons made by the outer loop and the inner loop.

• The sum of the number of comparisons is n(n-1)/2.

• The time complexity of the code is O(n^2).

n = 5
a | b c d e  = 4 Comparison for a,   (n-1) = 4
a b | c d e  = 3 Comparison for b,   (n-2) = 3
a b c | d e  = 2 Comparison for c,   (n-3) = 2
a b c d | e  = 1 Comparison for d,   (n-4) = 1
1 + 2 + 3 + .... + (n - 2) + (n - 1) 
= n(n-1)/2 
= (n^2 + n)/2 
= O(n^2) // nested loops