Selection Sort Algorithm Implemented in Python, Java, and C/C++

The Selection Sort Algorithm sorts the elements of an array. In this article, we shall look at the core algorithm and how we can implement it in Python, Java, C++, and C.

The Core Algorithm

The Selection Sort Algorithm is very simple.

Set i = 0 initially, since that is the starting point.
Find the minimum element of the unsorted sub-array [i..end]
We then swap this with the element at the position a[i].
We then increment i, and repeat the above steps until i == n

In pseudo-code, we can represent it like this:

PROCEDURE SELECTION_SORT(arr):
    i = -1
    while i < size(arr):
        idx = find_min(arr[i+1..size(arr)])
        swap(i, idx)
        i++
    return arr

Showing the working of the Algorithm

Let’s now understand how this algorithm works, by applying it on an array!

Let’s consider the below array.

Initially, the unsorted array looks like this:

In the first iteration, we find the minimum element from the remaining array (from {12, 7, 6, 16, 4}), which is 4. We now swap arr[i] with 4.

In the next iteration, we find the minimum element from the subarray {7, 6, 16, 12}, which is 6. So let’s swap 6 and 7.

Now, we move to the next element of the updated array and again do the same steps.

In the previous iteration, there was no change, since 7 is the minimum element in the remaining sub-array.

Now finally, we reach the end of the array, and now the complete array is sorted!

Let’s apply the Selection Sort Algorithm to sort the above array in Python, C++, and C.

Selection Sort in Python

The below snippet shows the working of the algorithm using Python.

def find_min(arr, start, end):
    minimum = arr[start]
    min_idx = start
    for idx in range(start, end):
        if arr[idx] < minimum:
            minimum = arr[idx]
            min_idx = idx
    return min_idx

def selection_sort(arr):
    i = 0
    arr_size = len(arr)
    while i < arr_size:
        # Find minimum of remaining unsorted subarray
        min_idx = find_min(arr, i, arr_size)
        # Swap with arr[i]
        arr[min_idx], arr[i] = arr[i], arr[min_idx]
        i += 1
    return arr

a = [12, 7, 6, 16, 4]
print(selection_sort(a))

Output

[4, 6, 7, 12, 16]

Selection Sort in Java

public class SelectionSort {
    int find_min(int arr[], int start, int end) {
        int min_idx = start;
        int minimum = arr[start];
        for (int i=start; i<end; i++) {
            if (arr[i] < minimum) {
                min_idx = i;
                minimum = arr[i];
            }
        }
        return min_idx;
    }

    void selection_sort(int arr[], int arr_len) {
        // Selection Sort on an Array
        // Pass by reference 
        int start = 0;
        int min_idx;
        while (start < arr_len) {
            min_idx = find_min(arr, start, arr_len);
            // Swap arr[start] and arr[min_idx]
            int temp = arr[start];
            arr[start] = arr[min_idx];
            arr[min_idx] = temp;
            start++;
        }
    }

    public static void main(String[] args) {
        int arr[] = {12, 7, 6, 16, 4};
        SelectionSort sel_sort = new SelectionSort();
        sel_sort.selection_sort(arr, 5);
        System.out.println("Array after sorting:");
        for (int i=0; i<5; i++) {
            System.out.printf("%d ", arr[i]);
        }
        System.out.println();
    }
}

Save the above code as SelectionSort.java.

Output

Array after sorting:
4 6 7 12 16

Selection Sort in C++

Here is another implementation of the algorithm in C++

#include <iostream>

using namespace std;


int find_min(int arr[], int start, int end) {
    int min_idx = start;
    int minimum = arr[start];
    for (int i=start; i<end; i++) {
        if (arr[i] < minimum) {
            min_idx = i;
            minimum = arr[i];
        }
    }
    return min_idx;
}


void selection_sort(int arr[], int arr_len) {
    // Selection Sort on an Array
    // Pass by reference 
    int start = 0;
    int min_idx;
    while (start < arr_len) {
        min_idx = find_min(arr, start, arr_len);
        // Swap arr[start] and arr[min_idx]
        int temp = arr[start];
        arr[start] = arr[min_idx];
        arr[min_idx] = temp;
        start++;
    }
}


int main() {
    int arr[] = {12, 7, 6, 16, 4};
    selection_sort(arr, 5);
    cout << "Array after sorting:\n";
    for (int i=0; i<5; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

Output

Array after sorting:
4 6 7 12 16

Selection Sort in C

#include <stdio.h>

int find_min(int arr[], int start, int end) {
    int min_idx = start;
    int minimum = arr[start];
    for (int i=start; i<end; i++) {
        if (arr[i] < minimum) {
            min_idx = i;
            minimum = arr[i];
        }
    }
    return min_idx;
}

void selection_sort(int arr[], int arr_len) {
    // Selection Sort on an Array
    int start = 0;
    int min_idx;
    while (start < arr_len) {
        min_idx = find_min(arr, start, arr_len);
        // Swap arr[start] and arr[min_idx]
        int temp = arr[start];
        arr[start] = arr[min_idx];
        arr[min_idx] = temp;
        start++;
    }
}


int main() {
    int arr[] = {12, 7, 6, 16, 4};
    selection_sort(arr, 5);
    printf("Array after sorting:\n");
    for (int i=0; i<5; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

Output

Array after sorting:
4 6 7 12 16

Time Complexity

Since the algorithm performs 2 loops iterating over the array, it has a time complexity of O(n^2).

If that’s not clear, the total number of operations performed, if the array has n elements is:

(n + (n-1) + (n-2) + (n-3) + … + 1) = n * (n + 1)/2 = O(n^2)

So, while this is not a very good sorting algorithm, it is very easy to implement, and can be used to sort arrays with low number of elements.

Must Reads

References

Wikipedia Article on Selection Sort