C++ Program Of Simple Selection Sort Implementation Using Array Ascending Order

Sorting data is a fundamental operation in computer science, crucial for efficiently organizing information. In this article, you will learn how to implement the Selection Sort algorithm in C++ to arrange elements of an array in ascending order.

Problem Statement

The challenge is to take an unsorted array of numbers and reorder its elements so that they appear in increasing sequence. Efficiently sorting data can significantly improve the performance of search operations and data analysis in various applications.

Example

Consider the following unsorted array: [64, 25, 12, 22, 11]

After applying Selection Sort, the array will be sorted in ascending order as: [11, 12, 22, 25, 64]

Background & Knowledge Prerequisites

To understand and implement Selection Sort, readers should be familiar with:

• C++ Basics: Fundamental syntax, data types, and variable declarations.
• Arrays: How to declare, initialize, and access elements in a C++ array.
• Loops: for loops for iterating through array elements.
• Conditional Statements: if statements for comparing values.
• Swapping: The concept of exchanging the values of two variables.

Use Cases or Case Studies

Sorting algorithms like Selection Sort are vital in many computing scenarios:

• Database Management: Organizing records (e.g., by ID, name, or date) to speed up queries and reporting.
• Search Algorithms: Many efficient search algorithms (like binary search) require sorted data to function.
• Data Analysis: Arranging data helps in identifying patterns, finding minimum/maximum values, or calculating percentiles.
• Graphics and Image Processing: Sorting pixels by color intensity or depth for rendering and effects.
• Operating Systems: Scheduling processes based on priority or resource requirements, which often involves sorting queues.

Solution Approaches

Selection Sort Implementation

Selection Sort is a simple comparison-based 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.

// Selection Sort Ascending
#include <iostream> // Required for input/output operations
#include <algorithm> // Required for std::swap (or you can implement manually)

void selectionSort(int arr[], int n) {
    // Step 1: Traverse through all array elements
    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
        // std::swap(arr[min_idx], arr[i]); // Using standard library swap
        // Manual swap implementation:
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Original array: ";
    printArray(arr, n);

    selectionSort(arr, n);

    std::cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Run

Sample Output

Original array: 64 25 12 22 11 
Sorted array: 11 12 22 25 64

Stepwise Explanation

1. Outer Loop (for (int i = 0; i < n - 1; i++)): This loop iterates n-1 times, where n is the total number of elements in the array. Each iteration places one element in its correct sorted position. The loop runs up to n-2 because the last element will automatically be in its correct place after n-1 elements are sorted.
2. Initialize min_idx: Inside the outer loop, min_idx is initialized to i. This variable will store the index of the smallest element found in the unsorted part of the array starting from i.
3. Inner Loop (for (int j = i + 1; j < n; j++)): This loop scans the unsorted portion of the array (from i+1 to n-1) to find the smallest element.
4. Find Minimum Element: If arr[j] is smaller than arr[min_idx], it means we found a new minimum, so min_idx is updated to j.
5. Swap Elements: After the inner loop completes, min_idx holds the index of the smallest element in the unsorted subarray arr[i...n-1]. The element at arr[min_idx] is then swapped with the element at arr[i], effectively moving the smallest element to its correct sorted position.
6. Repeat: The outer loop continues, shrinking the unsorted portion of the array by one element from the left until the entire array is sorted.

Conclusion

Selection Sort is an intuitive sorting algorithm that efficiently places elements in their correct positions by repeatedly finding the minimum element from the unsorted segment. While not the fastest for large datasets (it has a time complexity of O(n²)), its simplicity and predictable performance make it a good educational tool and suitable for small arrays.

Summary

• Concept: Repeatedly finds the minimum element and places it at the beginning of the unsorted segment.
• Process: Divides the array into sorted and unsorted parts.
• Time Complexity: O(n²) in all cases (best, average, worst).
• Space Complexity: O(1) as it sorts in-place.
• Stability: Not a stable sorting algorithm (relative order of equal elements might change).