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

# Selection Sort

## Use Case <a href="#use-case" id="use-case"></a>

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.
* &#x20;`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._

{% hint style="warning" %}
It is not very efficient for large arrays.
{% endhint %}

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

**`Question statement::`** [https://www.codingninjas.com/studio/problems/selection-sort\_981162](https://www.codingninjas.com/studio/problems/selection-sort_981162)

**`Notes:`** [https://drive.google.com/file/d/1WtwEvIvqKOUR0Ys0S\_SLPjfWzcT-W4\_X/view](https://drive.google.com/file/d/1WtwEvIvqKOUR0Ys0S_SLPjfWzcT-W4_X/view)

```cpp
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]); 
    }
}

```

<figure><img src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2Fl4GYbdXkFd8rnt12du4r%2Fimage.png?alt=media&#x26;token=05f40df4-4e1b-4abe-9af3-20dc60a5db84" alt=""><figcaption></figcaption></figure>

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).

```cpp
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
```
