C++ Program For Selection Sort In Ascending Order

Sorting is a fundamental operation in computer science, crucial for organizing data efficiently. It enables faster searching, merging, and more effective data analysis across various applications.

In this article, you will learn how to implement the Selection Sort algorithm in C++ to arrange elements in ascending order, understand its mechanism, and explore its practical applications.

Problem Statement

The challenge is to efficiently arrange a given list of unsorted elements into ascending order. For instance, if you have a list of student scores, you might need to sort them from lowest to highest to identify top performers or to process data in a structured manner. An effective sorting algorithm ensures that this rearrangement is done reliably and predictably.

Example

Consider an unsorted array of integers: [64, 25, 12, 22, 11]. After applying selection sort in ascending order, the array will become: [11, 12, 22, 25, 64].

Background & Knowledge Prerequisites

To understand and implement selection sort in C++, familiarity with the following basic concepts is helpful:

• C++ Basics: Fundamental syntax, variable declaration, and data types.
• Arrays: How to declare, initialize, and access elements in a one-dimensional array.
• Loops: for loops for iterating through arrays and controlling program flow.
• Conditional Statements: if statements for comparing values.
• Function Calls: Basic understanding of how functions work.

Use Cases or Case Studies

Sorting algorithms, including selection sort, are integral to many computing tasks:

• Database Management Systems: Organizing records by ID, name, or date for quicker retrieval.
• Search Algorithms: Many efficient search algorithms, like binary search, require data to be sorted.
• Graphical Applications: Arranging objects by depth for rendering or prioritizing UI elements.
• Data Analysis: Preparing datasets for statistical analysis by ordering values.
• Scheduling: Ordering tasks or processes by priority or deadline in operating systems.

Solution Approaches

Selection Sort is a straightforward, in-place comparison sorting algorithm. It repeatedly finds the minimum element from the unsorted part of the array and puts it at the beginning of the sorted part.

Standard Iterative Selection Sort

This approach systematically scans the unsorted portion of the array, identifies the smallest element, and swaps it with the element at the current position in the sorted portion.

// Selection Sort in Ascending Order
#include <iostream>
#include <vector> // Using vector for dynamic array, can also use fixed-size array
#include <algorithm> // For std::swap

void selectionSort(std::vector<int>& arr) {
    int n = arr.size();

    // Step 1: Iterate through the array
    for (int i = 0; i < n - 1; ++i) {
        // Step 2: Find the minimum element in the unsorted part of the array
        int min_idx = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }

        // Step 3: Swap the found minimum element with the first element of the unsorted part
        // This places the smallest element at its correct sorted position
        if (min_idx != i) { // Only swap if min_idx is not already the current position
            std::swap(arr[i], arr[min_idx]);
        }
    }
}

void printArray(const std::vector<int>& arr) {
    for (int i = 0; i < arr.size(); ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    // Step 1: Define an unsorted array
    std::vector<int> arr = {64, 25, 12, 22, 11};
    std::cout << "Original array: ";
    printArray(arr);

    // Step 2: Apply selection sort
    selectionSort(arr);

    // Step 3: Print the sorted array
    std::cout << "Sorted array (ascending): ";
    printArray(arr);

    // Additional test case
    std::vector<int> arr2 = {5, 1, 4, 2, 8};
    std::cout << "Original array 2: ";
    printArray(arr2);
    selectionSort(arr2);
    std::cout << "Sorted array 2 (ascending): ";
    printArray(arr2);

    return 0;
}

Run

Sample Output

Original array: 64 25 12 22 11 
Sorted array (ascending): 11 12 22 25 64 
Original array 2: 5 1 4 2 8 
Sorted array 2 (ascending): 1 2 4 5 8

Stepwise Explanation

1. Outer Loop (for (int i = 0; i < n - 1; ++i)): This loop iterates from the first element up to the second-to-last element of the array. Each iteration i represents the position where the smallest element found in the unsorted sub-array will be placed. After each pass, the element at index i is sorted.
2. Inner Loop (for (int j = i + 1; j < n; ++j)): For each i, this loop scans the *remaining unsorted portion* of the array (from i+1 to n-1) to find the index of the minimum element. min_idx stores the index of this smallest element found so far.
3. Finding Minimum Element (if (arr[j] < arr[min_idx])): Inside the inner loop, elements are compared. If an element at index j is smaller than the current minimum element (at min_idx), then min_idx is updated to j.
4. Swapping (std::swap(arr[i], arr[min_idx])): After the inner loop completes, min_idx holds the index of the smallest element in the unsorted part. This smallest element is then swapped with the element at position i. This places the smallest element correctly at the beginning of the unsorted segment, effectively moving it to the sorted segment. The if (min_idx != i) condition prevents unnecessary swaps if the element at i is already the smallest.

This process continues until the entire array is sorted.

Conclusion

Selection sort is a simple and intuitive sorting algorithm. It is an in-place comparison sort, meaning it does not require additional memory beyond the input array. While it has a time complexity of O(n^2) in all cases (best, average, and worst), making it inefficient for large datasets, its simplicity makes it a good choice for small lists or as a teaching tool for understanding basic sorting principles.

Summary

• Algorithm: Selection sort identifies the minimum element in the unsorted part and swaps it with the element at the current position.
• Process: It builds the sorted array one element at a time from the beginning.
• Time Complexity: O(n^2) for best, average, and worst-case scenarios.
• Space Complexity: O(1) as it sorts in-place.
• Suitability: Best for small lists or educational purposes due to its simplicity.