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

Selection sort scans the unsorted portion of an array exactly once per pass, picks the minimum element, and swaps it into its correct position. The algorithm completes in N-1 passes and always runs O(N²) comparisons regardless of input order.

This article covers the algorithm logic, a step-by-step trace on a five-element array, working code in C, C++, and Java, a full complexity analysis, and a direct comparison with bubble sort.

How Selection Sort Works

Selection sort divides the array into two logical regions: a growing sorted left partition and a shrinking unsorted right partition. At each outer-loop iteration, the algorithm scans the entire unsorted region to find its minimum element, then swaps that minimum with the first element of the unsorted region. The sorted partition grows by one position with each pass.

The NIST Dictionary of Algorithms and Data Structures classifies selection sort as a comparison-based, in-place algorithm. In-place means no auxiliary array is allocated. The only storage beyond the input array is a small set of integer variables: an outer loop index, a minimum-tracking index, and a temporary swap buffer.

The algorithm terminates in exactly N-1 outer-loop passes for an N-element array. During each pass, the inner loop scans every remaining unsorted element. This inner scan always runs to completion. There is no early-exit condition to detect a sorted subarray.

Pseudocode

• For i from 0 to N-2 (outer loop, one pass per element position):
  • Set min_index = i
  • For j from i+1 to N-1 (inner scan for the minimum):
    • If arr[j] < arr[min_index], update min_index = j
  • If min_index != i, swap arr[i] and arr[min_index]

The conditional swap on the last step avoids an unnecessary write when the minimum is already in the correct position. It reduces writes, not comparisons.

Step-by-Step Example: Sorting [14, 16, 3, 6, 50]

Trace the algorithm on the array [14, 16, 3, 6, 50] to see how each pass builds the sorted partition:

Pass	Unsorted Region	Minimum Found	Array After Pass
1	[14, 16, 3, 6, 50]	3 at index 2	[3, 16, 14, 6, 50]
2	[16, 14, 6, 50]	6 at index 3	[3, 6, 14, 16, 50]
3	[14, 16, 50]	14 — already at front	[3, 6, 14, 16, 50]
4	[16, 50]	16 — already at front	[3, 6, 14, 16, 50]

The sorted result is [3, 6, 14, 16, 50]. Key observations from this trace:

• Pass 1 swaps 3 (original index 2) with 14 (index 0). The first element is placed correctly.
• Pass 2 swaps 6 (original index 3) with 16 (index 1). Two elements are now in sorted position.
• Pass 3 and Pass 4 each find the minimum already at the front of the unsorted region. The swap is a no-op, but the inner scan still runs in full.
• Total swap count for this example: 2. The worst-case maximum for a 5-element array is N-1 = 4.

Selection Sort in C, C++, and Java

All three implementations use the same algorithm: an outer loop that sets the starting position, an inner scan that finds the minimum index, and a conditional swap. The C++ version calls std::swap from <algorithm> for clarity; the arithmetic is identical to the manual three-variable swap used in C and Java.

C

#include <stdio.h>

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

int main(void) {
    int arr[] = {14, 16, 3, 6, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}
/* Output: 3 6 14 16 50 */

C++

#include <iostream>
#include <algorithm>
using namespace std;

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

int main() {
    int arr[] = {14, 16, 3, 6, 50};
    int n = 5;
    selectionSort(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}
// Output: 3 6 14 16 50

Java

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

    public static void main(String[] args) {
        int[] arr = {14, 16, 3, 6, 50};
        selectionSort(arr);
        for (int x : arr)
            System.out.print(x + " ");
    }
}
// Output: 3 6 14 16 50

Time Complexity and Practical Limits

As Wikipedia’s entry on selection sort documents, the algorithm’s comparison count is fixed regardless of whether the input is random, sorted, or reverse-sorted.

The outer loop runs N-1 times. The inner loop runs N-1 times on the first pass, then N-2 times on the second, down to 1 comparison on the final pass. The total comparison count is always (N-1) + (N-2) + … + 1 = N(N-1)/2, which is O(N²).

Case	Comparisons	Swaps
Best case (already sorted)	O(N²)	0
Average case (random input)	O(N²)	O(N)
Worst case (reverse sorted)	O(N²)	O(N), at most N-1

Space Complexity

O(1). Selection sort is entirely in-place. The outer loop index, the min_index variable, and the swap buffer each hold a single integer. Total auxiliary storage does not grow with the size of the input.

Stability

Selection sort is not stable. When the algorithm swaps the minimum from inside the unsorted region to the front, it can move past equal-valued elements, changing their relative order. If preserving the original sequence of equal records matters, use merge sort or insertion sort instead.

In campus placement aptitude rounds at Tier-2 and Tier-3 engineering colleges across India, stability is a recurring MCQ topic. CoCubes assessments and similar platforms regularly ask: “Which of the following algorithms is not stable?” Selection sort and quick sort are the standard answers. Knowing the property is more useful than memorising the code.

The campus placement evaluation test guide covers the full scope of what these aptitude rounds test, including algorithm-complexity questions and data structure topics.

Selection Sort vs. Bubble Sort

Both algorithms run O(N²) comparisons in the worst and average cases, but they differ on two properties that matter in practice.

Property	Selection Sort	Bubble Sort
Time complexity (worst, average)	O(N²)	O(N²)
Time complexity (best case)	O(N²)	O(N)
Maximum swaps	N-1	O(N²)
In-place	Yes	Yes
Stable	No	Yes

The most significant practical difference is the swap count. Selection sort places each element permanently in exactly one swap per pass, so it never performs more than N-1 swaps across any input. Bubble sort moves adjacent pairs repeatedly, which can produce O(N²) writes when the array is heavily unsorted.

For environments where memory writes carry a higher cost than reads (small arrays on flash storage with limited write endurance, or EEPROM on embedded systems), selection sort’s bounded write count is a real advantage. For general-purpose sorting of large arrays, both algorithms are far slower than merge sort or quick sort.

Bubble sort has one capability selection sort lacks: early termination. A standard bubble sort implementation that tracks whether any swap occurred during a pass can detect a sorted array in a single pass and exit at O(N) comparisons in the best case. Selection sort always runs all N-1 outer-loop passes, even on already-sorted input. This is why the two algorithms share the same worst-case complexity but differ in best-case complexity.

Quantitative aptitude questions on time and work and sorting-algorithm MCQs both appear in aptitude sections of campus placement tests. Students who know the properties, not just the pseudocode, answer comparison questions faster because they do not need to trace the algorithm mentally.

For firms like D.E. Shaw that test algorithmic depth at every interview stage, see the D.E. Shaw campus recruitment process guide.

The O(N) swap bound that makes selection sort the right call in write-constrained environments is the same kind of asymptotic cost-benefit reasoning that shows up in AI system design discussions. TinkerLLM (₹299 to start) provides an LLM-guided environment to run sorting experiments and connect the O(N²) complexity tables in this article to actual measured output before your placement window arrives.