#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
// Find minimum element in unsorted portion
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap found minimum with first element
if (minIndex != i) {
swap(arr[i], arr[minIndex]);
}
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
printArray(arr, n);
selectionSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}Output
Original array: 64 34 25 12 22 11 90 Sorted array: 11 12 22 25 34 64 90
This program teaches you how to implement the Selection Sort algorithm in C++. Selection Sort works by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning. It's simple to understand and implement, making it a good learning algorithm, though it's not efficient for large datasets.
1. What This Program Does
The program sorts an array of integers using the Selection Sort algorithm. For example:
- Input array: [64, 34, 25, 12, 22, 11, 90]
- Output array: [11, 12, 22, 25, 34, 64, 90]
Selection Sort divides the array into two parts: sorted (at the beginning) and unsorted (remaining elements). In each iteration, it finds the minimum from the unsorted part and adds it to the sorted part.
2. Header File Used
#include <iostream>
This header provides:
- cout for displaying output
- cin for taking input from the user
3. Understanding Selection Sort
Algorithm Concept:
- Maintains two subarrays: sorted and unsorted
- Finds minimum element in unsorted portion
- Swaps it with first element of unsorted portion
- Sorted portion grows, unsorted shrinks
Visual Example:
Initial: [64, 34, 25, 12, 22, 11, 90] |sorted| |------unsorted------|
Pass 1: Find min (11) → swap with 64 [11, 34, 25, 12, 22, 64, 90] |sorted| |----unsorted----|
Pass 2: Find min (12) → swap with 34 [11, 12, 25, 34, 22, 64, 90] |--sorted--| |--unsorted--|
Continue until all sorted...
4. Function: selectionSort()
void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swap(arr[i], arr[minIndex]);
}
}
}
How it works:
- Outer loop (i): iterates from 0 to n-2 (n-1 passes)
- minIndex: tracks position of minimum element
- Inner loop: finds minimum in unsorted portion (i+1 to n-1)
- Swap: places minimum at position i
5. Step-by-Step Algorithm
Pass 1 (i=0):
- Search unsorted portion [34, 25, 12, 22, 11, 90] for minimum
- Minimum: 11 at index 5
- Swap arr[0] (64) with arr[5] (11)
- Result: [11, 34, 25, 12, 22, 64, 90]
Pass 2 (i=1):
- Search unsorted portion [34, 25, 12, 22, 64, 90] for minimum
- Minimum: 12 at index 3
- Swap arr[1] (34) with arr[3] (12)
- Result: [11, 12, 25, 34, 22, 64, 90]
Continue for n-1 passes...
6. Finding Minimum Element
for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } }
How it works:
- j starts at i + 1 (first unsorted element)
- Compares each element with current minimum
- Updates minIndex when smaller element found
- After loop, minIndex points to minimum
Example (finding min in [34, 25, 12, 22, 64, 90]):
- minIndex = 0, arr[0] = 34
- j=1: 25 < 34 → minIndex = 1
- j=2: 12 < 25 → minIndex = 2
- j=3: 22 > 12 → no change
- j=4: 64 > 12 → no change
- j=5: 90 > 12 → no change
- Minimum: 12 at index 2
7. Swap Operation
if (minIndex != i) { swap(arr[i], arr[minIndex]); }
How it works:
- Only swap if minimum is not already at position i
- Places minimum at beginning of unsorted portion
- Expands sorted portion by one element
Why Check minIndex != i?:
- Avoids unnecessary swap
- If minimum is already at position i, no swap needed
- Slight optimization
8. Time and Space Complexity
Time Complexity: O(n²) in all cases
- Always performs n(n-1)/2 comparisons
- No early termination possible
- Same for best, average, and worst case
Space Complexity: O(1)
- Only uses constant extra space
- Sorts in-place (modifies original array)
Stability: Not Stable
- Swapping can change relative order of equal elements
- Example: [3₁, 3₂, 1] → [1, 3₂, 3₁] (order changed)
9. When to Use Selection Sort
Best For:
- Small datasets
- When memory writes are expensive (minimal swaps)
- Simple implementation needed
- Educational purposes
Not Recommended For:
- Large datasets (use efficient algorithms)
- When stability is required
- Performance-critical applications
- Real-world production code (usually)
10. Important Considerations
Number of Passes:
- Exactly n - 1 passes needed
- Each pass places one element correctly
- Last element is automatically in place
Comparison Count:
- Always n(n-1)/2 comparisons
- No optimization possible
- Predictable performance
Swap Count:
- Maximum n - 1 swaps
- Minimum 0 swaps (if already sorted)
- Fewer swaps than Bubble Sort
11. return 0;
This ends the program successfully.
Summary
- Selection Sort finds minimum element and places it at beginning of unsorted portion.
- Time complexity: O(n²) in all cases - always performs same number of comparisons.
- Space complexity: O(1) - sorts in-place.
- Not stable - swapping can change relative order of equal elements.
- Simple algorithm - easy to understand and implement.
- Maintains two subarrays: sorted (growing) and unsorted (shrinking).
- Best for small datasets or when minimal swaps are important.
- Understanding Selection Sort helps learn more efficient algorithms.
This program is fundamental for beginners learning sorting algorithms, understanding minimum finding, and preparing for more efficient sorting algorithms in C++ programs.