Code: Selection Sort | Basics of C++ - Software Development PDF Download

Introduction

Sorting is a fundamental operation in computer science and programming. One popular sorting algorithm is the Selection Sort, known for its simplicity and ease of implementation. In this article, we will explore the Selection Sort algorithm in C++. We will provide multiple examples and code explanations to help beginners understand and implement this sorting technique.

What is Selection Sort?

Selection Sort is an in-place comparison-based sorting algorithm. It works by dividing the input array into two parts: the sorted and unsorted portions. The algorithm repeatedly selects the smallest (or largest) element from the unsorted part and swaps it with the first element of the unsorted part. This process continues until the entire array is sorted.

Code Implementation

Let's dive into the code implementation of the Selection Sort algorithm in C++. We'll start with a simple example and gradually expand our understanding.

Example 1: Sorting an Array of Integers

#include <iostream>

void selectionSort(int arr[], int size) {

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

        int minIndex = i;

        for (int j = i + 1; j < size; ++j) {

            if (arr[j] < arr[minIndex]) {

                minIndex = j;

            }

        }

        std::swap(arr[i], arr[minIndex]);

    }

}

int main() {

    int arr[] = {64, 25, 12, 22, 11};

    int size = sizeof(arr) / sizeof(arr[0]);

    

    std::cout << "Original Array: ";

    for (int i = 0; i < size; ++i) {

        std::cout << arr[i] << " ";

    }

    

    selectionSort(arr, size);

    

    std::cout << "\nSorted Array: ";

    for (int i = 0; i < size; ++i) {

        std::cout << arr[i] << " ";

    }

    

    return 0;

}

Output

Original Array: 64 25 12 22 11 

Sorted Array: 11 12 22 25 64

Code Explanation

• The selectionSort function takes an integer array arr and its size size as parameters.
• It iterates through the array from index 0 to size - 2 (the last index).
• Inside the outer loop, we initialize minIndex to i, assuming the current element is the smallest.
• The inner loop starts from i + 1 and searches for the actual minimum element by comparing each element with the current minimum (arr[minIndex]).
• If we find a smaller element, we update minIndex accordingly.
• After the inner loop finishes, we swap the current element with the smallest element found (arr[i] with arr[minIndex]).
• This process continues until the array is sorted.
• In the main function, we initialize an integer array arr and its size size.
• We display the original array, call the selectionSort function to sort the array, and display the sorted array.

Example 2: Sorting a Vector of Strings

#include <iostream>

#include <vector>

#include <algorithm>

void selectionSort(std::vector<std::string>& vec) {

    for (std::size_t i = 0; i < vec.size() - 1; ++i) {

        std::size_t minIndex = i;

        for (std::size_t j = i + 1; j < vec.size(); ++j) {

            if (vec[j] < vec[minIndex]) {

                minIndex = j;

            }

        }

        std::swap(vec[i], vec[minIndex]);

    }

}

int main() {

    std::vector<std::string> names = {"Alice", "John", "David", "Bob", "Eve"};

    

    std::cout << "Original Vector: ";

    for (const auto& name : names) {

        std::cout << name << " ";

    }

    

    selectionSort(names);

    

    std::cout << "\nSorted Vector: ";

    for (const auto& name : names) {

        std::cout << name << " ";

    }

    

    return 0;

}

Output

Original Vector: Alice John David Bob Eve 

Sorted Vector: Alice Bob David Eve John

Code Explanation

• Here, we use the Standard Template Library (STL) vector and sort a vector of strings.
• The 'selectionSort' function takes a reference to a vector of strings 'vec' as a parameter.
• It performs a similar selection sort algorithm as before, but this time using vector elements and the 'std::size_t' type for indices.
• We utilize the 'std::swap' function from the '<algorithm>' library to swap the elements.
• In the 'main' function, we create a vector of strings called 'names' and populate it with some names.
• We display the original vector, call the 'selectionSort' function to sort the vector, and display the sorted vector.

Sample Problems

1. Write a C++ program to sort an array of integers in descending order using the Selection Sort algorithm.

#include <iostream>

void selectionSortDescending(int arr[], int size) {

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

        int maxIndex = i;

        for (int j = i + 1; j < size; ++j) {

            if (arr[j] > arr[maxIndex]) {

                maxIndex = j;

            }

        }

        std::swap(arr[i], arr[maxIndex]);

    }

}

int main() {

    int arr[] = {64, 25, 12, 22, 11};

    int size = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Original Array: ";

    for (int i = 0; i < size; ++i) {

        std::cout << arr[i] << " ";

    }

    selectionSortDescending(arr, size);

    std::cout << "\nSorted Array (Descending): ";

    for (int i = 0; i < size; ++i) {

        std::cout << arr[i] << " ";

    }

    return 0;

}

Output

Original Array: 64 25 12 22 11 

Sorted Array (Descending): 64 25 22 12 11

2. Write a C++ program to sort a vector of floating-point numbers using the Selection Sort algorithm.

#include <iostream>

#include <vector>

#include <algorithm>

void selectionSort(std::vector<double>& vec) {

    for (std::size_t i = 0; i < vec.size() - 1; ++i) {

        std::size_t minIndex = i;

        for (std::size_t j = i + 1; j < vec.size(); ++j) {

            if (vec[j] < vec[minIndex]) {

                minIndex = j;

            }

        }

        std::swap(vec[i], vec[minIndex]);

    }

}

int main() {

    std::vector<double> numbers = {3.14, 1.23, 2.71, 0.99, 1.88};

    std::cout << "Original Vector: ";

    for (const auto& number : numbers) {

        std::cout << number << " ";

    }

    selectionSort(numbers);

    std::cout << "\nSorted Vector: ";

    for (const auto& number : numbers) {

        std::cout << number << " ";

    }

    return 0;

}

Output

Original Vector: 3.14 1.23 2.71 0.99 1.88 

Sorted Vector: 0.99 1.23 1.88 2.71 3.14

By understanding and implementing the Selection Sort algorithm in C++, you can easily sort arrays or vectors in ascending or descending order. It's a great starting point for learning about sorting algorithms and lays the foundation for more advanced techniques.
Remember, practice is key to mastering any algorithm. Try solving additional problems and explore other sorting algorithms to deepen your understanding of sorting in C++. Happy coding!