Implementation of Selection Sort Algorithm in C++

Selection sort is a simple sorting algorithm that works by repeatedly picking the smallest element from a list and moving it to the beginning of unsorted portion of the list. In this article, we’ll explore how to implement this algorithm in the C++ programming language. We’ll start with a simple implementation and then look at some practical variations, like sorting in descending order and sorting custom objects.

Prerequisites:

Basic Selection Sort Implementation

Let’s begin with a basic version of the selection sort algorithm. This code will sort an array of numbers in ascending order. We’ll go through each step, so it’s easy to follow, even if you’re just starting out with C++.

#include <iostream>
#include <vector>

using namespace std;

void selectionSort(vector<int>& arr) {
  // `arr`: This is the vector you want to sort
  int n = arr.size();
  // `n`: This variable stores the number of items in the vector

  // We go through each item in the vector, except the last one
  // The outer loop iterates from the first element (`0`) to the second-to-last element (`n - 2`).
  for (int i = 0; i < n - 1; i++) {
    // Let's say the current item is the smallest
    // `min_index`: This will hold the index of the smallest item we find
    int minIndex = i;

    // Now, check the rest of the vector to find a smaller item
    // The inner loop iterates through the unsorted portion of the vector,
    // starting from the element next to the current one (`i + 1`) to the last element (`n - 1`).
    for (int j = i + 1; j < n; j++) {
      // If we find a smaller item
      if (arr[j] < arr[minIndex]) {
        // Update the index of the smallest item
        minIndex = j;
      }
    }

    // If the smallest item is not the current item, swap them
    if (minIndex != i) {
      swap(arr[i], arr[minIndex]);
    }
  }
  // Now the vector is sorted!
}

// Utility function to print vector
void printVector(const vector<int>& arr) {
  for (int num : arr) {
    cout << num << " ";
  }
  cout << endl;
}

int main() {
  // Let's create a vector
  vector<int> arr = {64, 25, 12, 22, 11};
  cout << "Original vector: ";
  printVector(arr);

  // Sort the vector using selection sort
  selectionSort(arr);

  // Print the sorted vector
  cout << "Sorted vector: ";
  printVector(arr);

  return 0;
}

Let’s break down this code step by step:

  1. Include Headers: We start by including <iostream> for input/output operations and <vector> to use the vector container. We also use using namespace std; to avoid writing std:: repeatedly.
  2. selectionSort function: The selectionSort function takes a vector<int> as input, which is passed by reference (&) so that the original vector is modified.
  3. Outer Loop: The outer loop for (int i = 0; i < n - 1; i++) goes through each element in the vector, except the last one. In each iteration, we assume that the current element at index i is the smallest in the unsorted part of the vector. We stop at n - 2 because the last element will automatically be in its correct position after the n - 1 element is sorted.
  4. Inner Loop: The inner loop for (int j = i + 1; j < n; j++) checks the rest of the vector to find a smaller element. If it finds one (if (arr[j] < arr[minIndex])), it updates the index of the smallest element (minIndex = j).
  5. Swapping: After the inner loop, we check if the smallest element is not the current element (if (minIndex != i)). If they are different, we swap the current element with the smallest element using the swap function. This puts the smallest element in its correct position.
  6. printVector function: A utility function to print the contents of a vector<int>.
  7. main function: The main function demonstrates how to use the selectionSort function. It creates a sample vector, prints it, sorts it using selectionSort, and then prints the sorted vector.

Sorting in Descending Order

What if we want to sort the vector in descending order (from largest to smallest)? We just need to make a small change in the comparison within the inner loop. Here’s how:

#include <iostream>
#include <vector>

using namespace std;

void selectionSortDescending(vector<int>& arr) {
  int n = arr.size();

  for (int i = 0; i < n - 1; i++) {
    int maxIndex = i;

    for (int j = i + 1; j < n; j++) {
      // If we find a larger item
      if (arr[j] > arr[maxIndex]) { // Note the change here: `>` instead of `<`
        // Update the index of the largest item
        maxIndex = j;
      }
    }

    if (maxIndex != i) {
      swap(arr[i], arr[maxIndex]);
    }
  }
}

// Utility function to print vector
void printVector(const vector<int>& arr) {
  for (int num : arr) {
    cout << num << " ";
  }
  cout << endl;
}

int main() {
  vector<int> arr = {64, 25, 12, 22, 11};
  cout << "Original vector: ";
  printVector(arr);

  selectionSortDescending(arr);

  cout << "Sorted vector (descending): ";
  printVector(arr);

  return 0;
}

The only difference is in the if condition inside the inner loop: if (arr[j] > arr[maxIndex]). This change makes the function find the largest element instead of the smallest.

Sorting Custom Objects

Selection sort isn’t just for numbers; it can also sort custom objects. Imagine you have a collection of Person objects, each with a name and an age. You might want to sort these people by their age or alphabetically by their name. Here’s how you can achieve this using C++.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Person {
public:
  string name;
  int age;

  Person(string name, int age) : name(name), age(age) {}

  // Overload the output stream operator for easy printing
  friend ostream& operator<<(ostream& os, const Person& person) {
    os << "Name: " << person.name << ", Age: " << person.age;
    return os;
  }
};

// Function to sort a vector of Person objects based on a custom comparison function
void selectionSortCustom(vector<Person>& arr, auto compare) {
  int n = arr.size();

  for (int i = 0; i < n - 1; i++) {
    int minIndex = i;

    for (int j = i + 1; j < n; j++) {
      // Use the custom comparison function
      if (compare(arr[j], arr[minIndex])) {
        minIndex = j;
      }
    }

    if (minIndex != i) {
      swap(arr[i], arr[minIndex]);
    }
  }
}

int main() {
  vector<Person> people = {
    {"Alice", 30},
    {"Bob", 25},
    {"Charlie", 35}
  };

  cout << "Original vector:\n";
  for (const auto& person : people) {
    cout << person << endl;
  }

  // Sort by age using a lambda
  selectionSortCustom(people, [](const Person& a, const Person& b) {
    return a.age < b.age;
  });

  cout << "\nSorted by age:\n";
  for (const auto& person : people) {
    cout << person << endl;
  }

  // Sort by name using a lambda
  selectionSortCustom(people, [](const Person& a, const Person& b) {
    return a.name < b.name;
  });

  cout << "\nSorted by name:\n";
  for (const auto& person : people) {
    cout << person << endl;
  }

  return 0;
}

In this example, the selectionSortCustom function takes a generic compare argument using auto. This allows us to pass a lambda function directly to the sort function, specifying how to compare the objects.

  • Person Class: A Person class is defined with name and age attributes. The friend ostream& operator<< overload allows easy printing of Person objects.
  • Lambda Functions (Comparison): Instead of separate comparison functions, we use lambda functions directly within the selectionSortCustom calls.
    • To sort by age, we use [](const Person& a, const Person& b) { return a.age < b.age; }. This creates a small, anonymous function that compares the ages of two Person objects.
    • To sort by name, we use [](const Person& a, const Person& b) { return a.name < b.name; }. This lambda compares the names of two Person objects alphabetically.
  • selectionSortCustom Function: Takes a vector<Person> and a comparison function (now a lambda) as input. It sorts the vector using selection sort, using the provided compare function (lambda) to determine the order.
  • Sorting by Age: The lambda function compare tells the function to use the age value of each Person object for comparison.
  • Sorting by Name: The lambda function compare tells the function to use the name value for comparison.

This approach offers a concise and flexible way to use selection sort with custom objects, as you can define the comparison logic directly where you call the sorting function.

What’s Next?

Now that you’ve learned how to implement selection sort in C++, you can explore further: