C++ Program For Selection Sort Algorithm In Data Structure

Sorting is a fundamental operation in computer science, essential for organizing data efficiently. It allows for quicker searching, merging, and analysis of datasets by arranging elements in a specific order.

In this article, you will learn how to implement the Selection Sort algorithm in C++ to arrange an array of elements in ascending order.

Problem Statement

Efficiently organizing data is crucial in many applications, from databases to everyday lists. The problem at hand is to take an unsorted collection of items, typically stored in an array, and rearrange them into a specific order, such as ascending or descending. Without an organized structure, tasks like finding the smallest element or performing binary searches become inefficient and time-consuming, impacting application performance.

Example

Consider an unsorted array of integers: [64, 25, 12, 22, 11]. After applying a sorting algorithm, the array should be ordered as: [11, 12, 22, 25, 64].

Background & Knowledge Prerequisites

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

• C++ Basics: Fundamental syntax, variable declaration, data types.
• Arrays: How to declare, initialize, and access elements in a C++ array.
• Loops: for loops are essential for iterating through arrays.
• Functions: Defining and calling functions in C++ for modularity.
• Conditional Statements: if statements for comparisons.

Use Cases or Case Studies

Sorting algorithms like Selection Sort, despite varying complexities, are widely applicable:

• Displaying Leaderboards: Arranging player scores in descending order in a game.
• Organizing Search Results: Presenting search query results by relevance, date, or price.
• Data Analysis: Pre-sorting data before performing statistical analysis or finding medians/modes.
• Contact Lists: Sorting names alphabetically for easy lookup in a phone directory.
• Inventory Management: Arranging products by ID, name, or quantity in stock.

Solution Approaches

Selection Sort Algorithm

Selection Sort is a simple comparison-based sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning.

// Selection Sort in C++
#include <iostream>
#include <algorithm> // Required for std::swap

// 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
void selectionSort(int arr[], int n) {
    // One by one move boundary of unsorted subarray
    for (int i = 0; i < n - 1; i++) {
        // Find the minimum element in unsorted array
        int min_idx = i;
        for (int 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 subarray
        std::swap(arr[min_idx], arr[i]);
    }
}

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

    // Step 2: Print the original array
    std::cout << "Original array: ";
    printArray(arr, n);

    // Step 3: Apply Selection Sort
    selectionSort(arr, n);

    // Step 4: Print the sorted array
    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

Let's trace the Selection Sort algorithm with the example array [64, 25, 12, 22, 11]:

1. First Pass (i = 0):

• The unsorted part is [64, 25, 12, 22, 11].
• Assume min_idx = 0 (value 64).
• Iterate from j = 1 to 4:
• arr[1] (25) < arr[0] (64)? Yes. min_idx becomes 1.
• arr[2] (12) < arr[1] (25)? Yes. min_idx becomes 2.
• arr[3] (22) < arr[2] (12)? No.
• arr[4] (11) < arr[2] (12)? Yes. min_idx becomes 4.
• After the inner loop, min_idx is 4.
• Swap arr[0] (64) with arr[4] (11).
• Array becomes: [11, 25, 12, 22, 64].

1. Second Pass (i = 1):

• The unsorted part is [25, 12, 22, 64].
• Assume min_idx = 1 (value 25).
• Iterate from j = 2 to 4:
• arr[2] (12) < arr[1] (25)? Yes. min_idx becomes 2.
• arr[3] (22) < arr[2] (12)? No.
• arr[4] (64) < arr[2] (12)? No.
• After the inner loop, min_idx is 2.
• Swap arr[1] (25) with arr[2] (12).
• Array becomes: [11, 12, 25, 22, 64].

1. Third Pass (i = 2):

• The unsorted part is [25, 22, 64].
• Assume min_idx = 2 (value 25).
• Iterate from j = 3 to 4:
• arr[3] (22) < arr[2] (25)? Yes. min_idx becomes 3.
• arr[4] (64) < arr[3] (22)? No.
• After the inner loop, min_idx is 3.
• Swap arr[2] (25) with arr[3] (22).
• Array becomes: [11, 12, 22, 25, 64].

1. Fourth Pass (i = 3):

• The unsorted part is [25, 64].
• Assume min_idx = 3 (value 25).
• Iterate from j = 4 to 4:
• arr[4] (64) < arr[3] (25)? No.
• After the inner loop, min_idx is 3.
• Swap arr[3] (25) with arr[3] (25). (No actual change).
• Array remains: [11, 12, 22, 25, 64].

The outer loop runs n-1 times because the last element will automatically be in its correct place after the first n-1 elements are sorted. The array is now fully sorted.

Conclusion

Selection Sort is a straightforward sorting algorithm that is easy to understand and implement. It performs well for small datasets but has a time complexity of O(N^2) in all cases (best, average, worst), making it less efficient for large arrays compared to more advanced algorithms like Merge Sort or Quick Sort. Its primary advantage lies in its simplicity and its property of performing a minimum number of swaps, which can be beneficial in situations where writes to memory are costly.

Summary

• Algorithm: Selection Sort works by repeatedly finding the minimum element from the unsorted portion of the array and placing it at the beginning of the sorted portion.
• Process: It divides the array into a sorted and an unsorted subarray. In each iteration, the smallest element from the unsorted subarray is picked and moved to the sorted subarray.
• Time Complexity: O(N^2) in all cases (best, average, worst).
• Space Complexity: O(1) as it only uses a few extra variables for comparisons and swaps.
• Stability: Selection Sort is generally not stable, meaning that the relative order of equal elements might not be preserved.
• Use Case: Best suited for small datasets or educational purposes due to its simplicity.