Selection Sort Algorithm (C++)

[qingquan-li]

Selection Sort Algorithm (C++)

1. What is Selection Sort Algorithm

Selection sort is a simple comparison-based sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the array and swapping it with the first unsorted element.

The main steps of the selection sort algorithm are:

1. Start with the first element in the array as the current minimum (or maximum) and its index as the current minimum (or maximum) index.
2. Iterate through the unsorted portion of the array (starting from the second element) to find the smallest (or largest) element and its index.
3. If a new minimum (or maximum) is found, update the current minimum (or maximum) and its index.
4. After completing the iteration, swap the first unsorted element with the current minimum (or maximum) element.
5. Move to the next element in the array and repeat steps 1-4 for the remaining unsorted portion of the array.

The time complexity of the selection sort algorithm is O(n²) in the best, worst, and average cases, making it inefficient for large datasets. However, it can be helpful for sorting small datasets or in cases where swapping elements is much more expensive than comparing them. This is because selection sort does fewer swaps compared to other similar (quadratic) algorithms, such as bubble sort and insertion sort.

2. How it Works

Example: Sort the array "5,2,6,3,1,4" in ascending order using selection sort.

5	2	6	3	1	4
1 |	2	6	3	5	4
1	2 |	6	3	5	4
1	2	3 |	6	5	4
1	2	3	4 |	5	6
1	2	3	4	5	6

3. C++ Code for the Selection Sort Algorithm

#include <iostream>

// Function prototypes
void selectionSort(int[], int);
void swap(int&, int&);

int main() {
    const int SIZE = 6;
    // Array of unsorted values
    int values[SIZE] = { 5, 2, 6, 3, 1, 4 };

    // Sort the array.
    selectionSort(values, SIZE);
    for (auto element : values)
        std::cout << element << " ";
    return 0;
}

/**
 * The selectionSort function sorts an int array in ascending order.
 * @param array The array to sort
 * @param size  The size of the array
*/
void selectionSort(int array[], int size) {
    int minIndex, minValue;
    for (int start = 0; start < size - 1; start++) {
        minIndex = start;
        minValue = array[start];
        for (int index = start + 1; index < size; index++) {
            if (array[index] < minValue) {
                minValue = array[index];
                minIndex = index;
            }
        }
        swap(array[minIndex], array[start]);
    }
}

/**
 * The swap function swaps a and b in memory.
 * Reference variables allow a function to access the parameter's original argument.
 * @param a
 * @param b
 */
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

4. Time Complexity

Example: Given array: [5, 4, 3, 2, 1]

					Comparisons and Swaps
5	4	3	2	1	4: (5, 4), (5, 3), (5, 2), (5, 1). swap(5, 1)
1 |	4	3	2	5	3: (4, 3), (4, 2), (4, 5). swap(4, 2)
1	2 |	3	4	5	2: (3, 4), (3, 5). No swap.
1	2	3 |	4	5	1: (4, 5). No swap.
1	2	3	4	5

Comparisions are made in this case is 4 + 3 + 2 + 1 =10.

Comparisions are made in the selection sort is: (n - 1) + (n - 2) + (n - 3) + ... + 1. (n is the number of array elements.)

As we know, 1 + 2 + 3 + ... + n = n * (n+1) / 2. So, the formula for the number of comparisons in the selection sort is: (n - 1) * ( n - 1 + 1) / 2 = (n - 1) * n / 2

Using Big-O notation, the time complexity of selection sort is:

lim n -> ∞ (n - 1) * n / 2 = lim n -> ∞ (n² -n) / 2 = n²

O(n²)