Home | Projects | Notes > Data Structures & Algorithms > Selection Sort: T = O(n²) , S = O(1)

Selection Sort: T = O(n²) , S = O(1)

Selection Sort

• A sorting algorithm that iteratively selects the smallest (or largest) element from an unsorted portion of the list and places it at the beginning (or end) of the sorted portion. This process is repeated until the entire list is sorted.

• Selection sort has a time complexity of O(n²), making it inefficient for large lists.

• Selection sort has a space complexity of O(1). It sorts the array in place, that is, It does not create additional copies of the array.

Algorithm

1. Input: An array of elements to be sorted.

2. Loop: Start a loop that iterates from the second element to the last element of the array.

3. Current Element: For the current iteration, store the value of the element to be inserted into the sorted portion.

4. Inner Loop: Within the loop, iterate from the current element's position back to the beginning of the array (or until a smaller element is found).

5. Shift and Insert: While iterating in the inner loop, if the current element is smaller than the element being compared, shift the compared element to the right to make space for the current element.

6. Insert Current Element: Once a suitable position is found in the inner loop, insert the current element into that position.

7. Repeat: Continue this process for each element in the array until the entire array is sorted.

Pseudo-code

xxxxxxxxxx
9
1
SelectionSort(arr):
2
    n = length(arr)
3
    for i from 1 to n - 1:
4
        current = arr[i]
5
        j = i - 1
6
        while j >= 0 and arr[j] > current:
7
            arr[j + 1] = arr[j]
8
            j = j - 1
9
        arr[j + 1] = current

Code

xxxxxxxxxx
37
1
#include <iostream>
2

3
using namespace std;
4

5
void selectionSort(int arr[], int size)
6
{
7
    for (int i = 0; i < size; i++)
8
    {
9
        int minIndex = i;
10
        for (int j = i + 1; j < size; j++)
11
        {
12
            if (arr[j] < arr[minIndex])
13
                minIndex = j;
14
        }
15
        if (minIndex != i)
16
        {
17
            int temp = arr[i];
18
            arr[i] = arr[minIndex];
19
            arr[minIndex] = temp;
20
        }
21
    }
22
}
23

24
int main(void)
25
{
26
    int arr[] = {6, 4, 2, 1, 5, 3};
27
    int size = sizeof(arr) / sizeof(arr[0]);
28
    
29
    selectionSort(arr, size);
30
    
31
    for (auto val : arr)
32
        cout << val << " ";
33
    
34
    cout << endl;
35
    
36
    return 0;
37
}

xxxxxxxxxx
1
1
1 2 3 4 5 6