Selection Sort in C, C++, and Java with Examples

Introduction

Sorting algorithms are fundamental in computer science, and Selection Sort is one of the simplest techniques. It works by repeatedly selecting the smallest (or largest) element from an unsorted list and placing it in its correct position in a sorted list.

This article covers:

• How Selection Sort Works – Step-by-step explanation
• Selection Sort Algorithm & Pseudocode
• Code Implementation in C, C++, and Java
• Time Complexity Analysis – Best, Worst, and Average Cases
• Comparison with Bubble Sort

What is Selection Sort?

Selection Sort follows a comparison-based technique where it selects the smallest (or largest) element from the unsorted portion and swaps it with the first unsorted element. This process continues until the entire array is sorted.

Key Features of Selection Sort:

• Simple and easy to implement
• In-place sorting algorithm – No extra memory required (O(1) space complexity)
• Inefficient for large datasets (O(N²) time complexity)

How Selection Sort Works – Step-by-Step Example

Let’s sort the array [14, 16, 3, 6, 50] in ascending order using Selection Sort.

Step-by-Step Execution:

Selection Sort Algorithm & Pseudocode

Here’s the basic logic behind Selection Sort:

1. Loop through the array
2. Find the smallest element in the unsorted portion
3. Swap it with the first element of the unsorted portion
4. Repeat until the entire array is sorted

Pseudocode:

plaintextCopyEditfor i = 0 to n - 1:
    min_index = i
    for j = i + 1 to n:
        if arr[j] < arr[min_index]: 
            min_index = j
    Swap arr[min_index] with arr[i]

Selection Sort Implementation in C, C++, and Java

Below are the implementations of Selection Sort in different programming languages.

Selection Sort in C:

cCopyEdit#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, min_index, temp;
    for (i = 0; i < n - 1; i++) {
        min_index = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_index])
                min_index = j;
        }
        temp = arr[min_index];
        arr[min_index] = arr[i];
        arr[i] = temp;
    }
}

Selection Sort in C++:

cppCopyEdit#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_index])
                min_index = j;
        }
        swap(arr[min_index], arr[i]);
    }
}

Selection Sort in Java:

javaCopyEditpublic class SelectionSort {
    public static void selectionSort(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int min_index = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min_index])
                    min_index = j;
            }
            int temp = arr[min_index];
            arr[min_index] = arr[i];
            arr[i] = temp;
        }
    }
}

Time Complexity Analysis of Selection Sort

• Space Complexity: O(1) since no extra memory is used.
• Stable? No, because swapping elements can change the relative order of duplicates.

Selection Sort vs. Bubble Sort

Conclusion

• Selection Sort is simple but inefficient for large datasets.
• It is better than Bubble Sort in terms of the number of swaps but still has O(N²) complexity.
• It works well for small or nearly sorted arrays but is not suitable for real-world large-scale sorting.

For more efficient sorting, check out:

• Insertion Sort
• Merge Sort
• Quick Sort
• Heap Sort