What is a selection sort in C++ and how is it implemented?

Table of Contents

• Introduction
• How Selection Sort Works
  • Algorithm Overview
  • Steps of the Selection Sort Algorithm:
  • Time Complexity
  • Space Complexity
• Selection Sort Implementation in C++
  • Code Example:
  • Explanation of the Code
  • Output:
• Practical Examples of Selection Sort
  • Example 1: Sorting a List of Grades
  • Example 2: Sorting a List of Names by Their ASCII Values
• Conclusion

Introduction

Selection sort is a simple comparison-based sorting algorithm. It works by repeatedly finding the minimum (or maximum) element from the unsorted portion of an array and placing it at the beginning (or end). Although it is not the most efficient sorting algorithm for large datasets, selection sort is easy to understand and implement, making it ideal for educational purposes and small datasets.

In this guide, we will cover the selection sort algorithm in detail and show how to implement it in C++.

How Selection Sort Works

Algorithm Overview

Selection sort divides the array into two parts:

1. A sorted subarray that grows from left to right.
2. An unsorted subarray where elements are yet to be sorted.

The algorithm iterates through the array and repeatedly selects the smallest (or largest) element from the unsorted part and swaps it with the leftmost unsorted element, gradually building a sorted subarray.

Steps of the Selection Sort Algorithm:

1. Find the minimum element in the unsorted portion of the array.
2. Swap this minimum element with the first unsorted element.
3. Move the boundary between sorted and unsorted portions to the right by one.
4. Repeat the process until the array is sorted.

Time Complexity

• Worst-case: O(n²) (when the array is in reverse order)
• Best-case: O(n²) (even if the array is already sorted, it will still scan all elements)
• Average-case: O(n²)

Selection sort performs well on small datasets but becomes inefficient for larger ones due to its quadratic time complexity.

Space Complexity

• Space complexity: O(1), as it only uses a constant amount of extra memory.

Selection Sort Implementation in C++

Code Example:

Explanation of the Code

1. selectionSort Function:
   • The outer loop iterates through each element of the array, treating it as the boundary between the sorted and unsorted parts.
   • The inner loop looks for the minimum element in the unsorted portion and swaps it with the first unsorted element.
   • After each pass, the sorted portion of the array grows by one element.
2. printArray Function:
   • This function simply prints out the elements of the array.

Output:

Practical Examples of Selection Sort

Example 1: Sorting a List of Grades

You might use selection sort to arrange student grades in ascending order.

Output:

Example 2: Sorting a List of Names by Their ASCII Values

If you have a list of characters and want to sort them by their ASCII values, selection sort can be applied:

Output:

Conclusion

Selection sort is a straightforward sorting algorithm that is easy to implement and understand. While it has a time complexity of O(n²), making it less suitable for large datasets, its simplicity makes it ideal for educational purposes and small arrays. In C++, selection sort can be efficiently implemented with a few loops and conditional statements.