C++ Program For Selection Sort Using Function

Sorting is a fundamental operation in computer science, crucial for organizing data efficiently. In this article, you will learn how to implement the Selection Sort algorithm in C++ using a dedicated function, providing a clear and structured approach to array sorting.

Problem Statement

Efficiently organizing data is crucial for many applications. The problem Selection Sort addresses is arranging elements of an array in ascending (or descending) order, which streamlines data retrieval, analysis, and other data processing tasks. For instance, imagine a list of student scores that needs to be ordered from lowest to highest; Selection Sort provides a straightforward method to achieve this.

Example

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

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

Background & Knowledge Prerequisites

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

• C++ Basics: Variables, data types, operators.
• Arrays: Declaring, initializing, and accessing elements.
• Loops: for loops for iteration.
• Functions: Defining and calling functions, passing arrays to functions.
• Basic Algorithm Concepts: Understanding the idea of sorting and comparisons.

Use Cases or Case Studies

Selection Sort, while not the most efficient for large datasets, has practical applications in several scenarios:

• Educational Purposes: It is an excellent algorithm for illustrating fundamental sorting concepts due to its simplicity.
• Small Data Sets: For arrays with a small number of elements, its performance overhead is negligible, and its simple implementation can be advantageous.
• Memory-Constrained Environments: When memory writes are costly, Selection Sort performs the minimum number of swaps (at most n-1 swaps), which can be beneficial.
• When Stability is Not Required: Unlike some other sorts, Selection Sort is not a stable algorithm (it might change the relative order of equal elements), but this is not an issue in many practical scenarios.

Solution Approaches

Selection Sort works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning. This process continues until the entire array is sorted.

Implementing Selection Sort with a Function

The core idea is to divide the array into a sorted and an unsorted part. We repeatedly pick the smallest element from the unsorted part and place it in the sorted part.

// Selection Sort using Function
#include <iostream> // For input/output operations
#include <algorithm> // For std::swap

// Function to swap two elements
void swap(int* xp, int* yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = 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;
}

// Function to perform Selection Sort on an array
void selectionSort(int arr[], int n) {
    int i, j, min_idx;

    // One by one move boundary of unsorted subarray
    for (i = 0; i < n - 1; i++) {
        // Find the minimum element in unsorted array
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }

        // Swap the found minimum element with the first element of the unsorted part
        // std::swap(arr[min_idx], arr[i]); // Can use std::swap from <algorithm>
        swap(&arr[min_idx], &arr[i]); // Using custom swap function
    }
}

int main() {
    // Step 1: Initialize an unsorted array
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    // Step 2: Call the selectionSort function to sort the array
    selectionSort(arr, n);

    std::cout << "Sorted array: ";
    // Step 3: Print the 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. selectionSort(int arr[], int n) function: This function takes an integer array arr and its size n as input.
2. Outer Loop (for (i = 0; i < n - 1; i++)): This loop iterates from the first element up to the second-to-last element. In each iteration i, it aims to place the correct (smallest) element at index i.

• min_idx = i;: Initially, we assume the element at the current position i is the minimum in the unsorted part.

1. Inner Loop (for (j = i + 1; j < n; j++)): This loop searches for the actual minimum element in the remaining unsorted part of the array, which starts from i + 1 to n - 1.

• if (arr[j] < arr[min_idx]): If an element arr[j] is found that is smaller than the current min_idx element, min_idx is updated to j.

1. Swap Operation (swap(&arr[min_idx], &arr[i]);): After the inner loop completes, min_idx holds the index of the smallest element in the unsorted subarray. This smallest element is then swapped with the element at the current position i. This effectively places the minimum element in its correct sorted position.
2. Repeat: The outer loop continues, shrinking the unsorted part of the array by one element in each iteration until the entire array is sorted.
3. Helper Functions:

• swap(int* xp, int* yp): A utility function to exchange the values of two integer pointers.
• printArray(int arr[], int size): A utility function to display the contents of the array.

1. main() function: This function initializes an array, prints its original state, calls selectionSort to sort it, and then prints the sorted array.

Conclusion

Selection Sort is a simple comparison-based sorting algorithm that, despite its O(n^2) time complexity, offers clarity in its approach. It efficiently places the smallest element at its correct position in each pass, making it a good choice for understanding fundamental sorting principles and for very small datasets where simplicity outweighs performance needs.

Summary

• Algorithm Principle: Finds the minimum element from the unsorted part and swaps it with the element at the current position, progressively building a sorted array.
• Time Complexity: O(n^2) in all cases (best, average, worst), making it less suitable for large datasets.
• Space Complexity: O(1) as it sorts the array in-place without requiring extra memory.
• Stability: Not a stable sorting algorithm.
• Swaps: Performs a minimum number of swaps, at most n-1 swaps.
• Use Cases: Primarily for educational purposes, small arrays, or when the number of swaps needs to be minimized.