[Data Structure] Introduction of Selection Sort

Last Updated on 2022-07-20 by Clay

Selection sort is one of the most well-known sorting algorithms, like Bubble sort, is a stable sorting method. Whether it is the best case, the average case or the worst case, the time complexity is O(n^2).

---

Principle of Selection Sort

In terms of ascending sorting, it usually starts from the initial index in the list, finds the smallest number in one round of iteration, and exchanges the smallest number with the value at the beginning.

In the second round of sorting, ignore the value at the beginning (because it is already the minimum value), start with the second value to find the minimum value for the iteration again... and so on until only the last value is left.

The last number must be the maximum value of the list, so no additional traversal is required.

As with the Bubble sort, the following list is used as an example:

[4, 5, 3, 1, 2, 7, 6]

• First, we record the first number 4 as the current minimum value, and then start to compare the other numbers in the list in order
• Finally, we find that 1 is the smallest value in the list, so we swap the position of 1 and 4

[1, 5, 3, 4, 2, 7, 6]

• Then for the second iteration, we record the starting number 5 as the current minimum value (this round start at the second value)

Finally, we get the following sorted list:

[1, 2, 3, 4, 5, 6, 7]

It is also a very simple and intuitive sorting method. The following is sample code.

---

Selection Sort Sample Code

Complexity

It is a method with relatively stable complexity, and the additional space required is only O(1), but it may not be suitable to use the sorting method with such as high time complexity in a longer array.

Time Complexity	O(n^2)
Space Complexity	O(1)

C++ Sample Code

#include <iostream>
using namespace std;


void swap(int* n1, int* n2) {
    int temp = *n1;
    *n1 = *n2;
    *n2 = temp;
}


void printArr(int arr[], int size) {
    for (int i=0; i<size; ++i) {
        cout << arr[i] << " ";
    }

    cout << endl;
}


void selectionSort(int arr[], int size) {
    // Sort
    for (int i=0; i<size-1; ++i) {
        // Init
        int minIndex = i;

        for (int j=i+1; j<size; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Swap
        swap(&arr[i], &arr[minIndex]);

        // Print progress
        cout << i+1 << ": ";
        printArr(arr, size);
    }
}


int main() {
    int arr[] = {4, 5, 3, 1, 2, 7, 6};
    int size = sizeof(arr) / sizeof(arr[0]); 
    selectionSort(arr, size);

    return 0;
}

Output:

1: 1 5 3 4 2 7 6 
2: 1 2 3 4 5 7 6 
3: 1 2 3 4 5 7 6 
4: 1 2 3 4 5 7 6 
5: 1 2 3 4 5 7 6 
6: 1 2 3 4 5 6 7 

Python Sample Code

# coding: utf-8


def bubbleSort(arr, size):
    for i in range(size-1):
        # Init
        minIndex = i

        for j in range(i+1, size):
            if (arr[j] < arr[minIndex]):
                minIndex = j
        
        # Swap
        arr[i], arr[minIndex] = arr[minIndex], arr[i]

        # Print progress
        print("{}: {}".format(i+1, arr))


def main():
    # Init
    arr = [4, 5, 3, 1, 2, 7, 6]
    size = len(arr)

    # Sort
    bubbleSort(arr, size)


if __name__ == "__main__":
    main()

Output:

1: [1, 5, 3, 4, 2, 7, 6]
2: [1, 2, 3, 4, 5, 7, 6]
3: [1, 2, 3, 4, 5, 7, 6]
4: [1, 2, 3, 4, 5, 7, 6]
5: [1, 2, 3, 4, 5, 7, 6]
6: [1, 2, 3, 4, 5, 6, 7]

---

References

• https://www.programiz.com/dsa/selection-sort
• https://www.geeksforgeeks.org/selection-sort/
• https://en.wikipedia.org/wiki/Selection_sort

---

Read More