C++ Program to Implement Selection Sort

by

Introduction

Selection sort is a simple and intuitive comparison-based sorting algorithm. Despite its simplicity, it is not suitable for large datasets as its average and worst-case time complexity is quite high. In this article, we will delve into the concept of selection sort, understand its working principle, and implement it in C++ through various examples. This hands-on approach will help solidify your understanding of selection sort and improve your overall programming skills.

Prerequisites

Before diving into the code, it’s essential to have a basic understanding of:

  1. C++ Programming Language: Familiarity with basic syntax, variables, and data types.
  2. Control Structures: Understanding of loops (for, while) and conditional statements (if-else).
  3. Arrays: Knowledge of how to declare, initialize, and manipulate arrays in C++.
  4. Functions: Understanding how to define and call functions in C++.

With these prerequisites in mind, let’s explore the implementation of selection sort in C++.

Example 1: Basic Selection Sort Implementation in C++

Code Explanation

In this example, we will implement the basic selection sort algorithm in C++.

Code

C++
#include <iostream>
using namespace std;

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;
            }
        }
        swap(arr[minIndex], arr[i]);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    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

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

Explanation

In this basic implementation, we iterate through the array and select the smallest element in each pass, swapping it with the element at the current position. The selectionSort function handles the sorting, while the printArray function is used to display the array before and after sorting.

Example 2: Selection Sort with a Function Template in C++

Code Explanation

In this example, we will use a function template to make the selection sort algorithm more versatile, allowing it to sort arrays of any data type.

Code

C++
#include <iostream>
using namespace std;

template <typename T>
void selectionSort(T 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;
            }
        }
        swap(arr[minIndex], arr[i]);
    }
}

template <typename T>
void printArray(T arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int intArr[] = {29, 10, 14, 37, 13};
    float floatArr[] = {64.5, 25.3, 12.1, 22.2, 11.4};
    int intSize = sizeof(intArr) / sizeof(intArr[0]);
    int floatSize = sizeof(floatArr) / sizeof(floatArr[0]);

    cout << "Original integer array: ";
    printArray(intArr, intSize);
    selectionSort(intArr, intSize);
    cout << "Sorted integer array: ";
    printArray(intArr, intSize);

    cout << "Original float array: ";
    printArray(floatArr, floatSize);
    selectionSort(floatArr, floatSize);
    cout << "Sorted float array: ";
    printArray(floatArr, floatSize);

    return 0;
}

Output

C++
Original integer array: 29 10 14 37 13 
Sorted integer array: 10 13 14 29 37 
Original float array: 64.5 25.3 12.1 22.2 11.4 
Sorted float array: 11.4 12.1 22.2 25.3 64.5

Explanation

In this example, we use function templates to generalize the selection sort algorithm. This allows us to sort arrays of different data types, such as integers and floats, using the same selectionSort and printArray functions.

Example 3: Selection Sort on a List of Strings in C++

Code Explanation

In this example, we will implement selection sort to sort a list of strings in alphabetical order.

Code

C++
#include <iostream>
#include <string>
using namespace std;

void selectionSort(string 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;
            }
        }
        swap(arr[minIndex], arr[i]);
    }
}

void printArray(string arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    string arr[] = {"apple", "orange", "banana", "kiwi", "grape"};
    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

C++
Original array: apple orange banana kiwi grape 
Sorted array: apple banana grape kiwi orange

Explanation

In this example, we apply the selection sort algorithm to sort an array of strings in alphabetical order. The same selection sort logic is used, but instead of comparing numeric values, we compare strings lexicographically.

Conclusion

Selection sort is a straightforward sorting algorithm suitable for small datasets and educational purposes. Through the examples provided, we’ve seen how to implement selection sort in C++, using basic arithmetic operations, function templates, and sorting different data types like integers, floats, and strings. Each approach demonstrates the flexibility and simplicity of selection sort