2 different C++ programs to implement selection sort

Implement selection sort in C++:

In this post, we will learn the algorithm of selection sort and how to implement it in C++.

How selection sort works:

The selection sort is a sorting algorithm that sorts a list of values with in-place comparison.

It builds the sorted list from left to right. The original list is divided into two parts, a sublist of sorted items that are built up from the left of the list and another sublist of the remaining items.

On each step, the algorithm finds the smallest element of the unsorted sublist. It swaps this with the first element of the unsorted sublist. This will put that element in the sorted sublist and the length of the unsorted sublist is reduced by one.

Let’s take a look at the below example:

• [2, 30, 1, 28, 7] is the given list.
• On each step, it finds the smallest value in the unsorted sublist, swaps it with the first element, and moves the sorted sublist boundary one element to right.
• It stops once the unsorted sublist becomes empty.

The above example sorts the list in ascending order. Instead of finding the smallest value, we can also find the largest element to sort the list in descending order.

Example 1: C++ program to implement selection sort in ascending order:

Below is the complete C++ program that sorts an array in ascending order using selection sort:

#include <iostream>
using namespace std;

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

void swap(int *first, int *second)
{
    int t = *first;
    *first = *second;
    *second = t;
}

void selectionSort(int arr[], int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        int min = i;

        for (int j = i + 1; j < size; j++)
        {
            if (arr[j] < arr[min])
            {
                min = j;
            }
        }

        swap(&arr[min], &arr[i]);
    }
}

int main()
{
    int givenArray[] = {2, 8, 1, 5, 30, 21};
    int size = sizeof(givenArray) / sizeof(givenArray[0]);

    cout << "Given Array: ";
    printArray(givenArray, size);

    selectionSort(givenArray, size);

    cout << "Sorted Array: ";
    printArray(givenArray, size);
}

Here,

• The printArray method prints the content of an array. It takes the array and its size as its parameters and prints its content by using a for loop.
• The swap method swaps two values. It takes the addresses of the two values and swaps the values of these addresses.
• The selectionSort method is used to sort an array in ascending order by using selection sort. It takes the array and the size of the array as its parameters.
  • The outer for loop is used to iterate over the unsorted sublist.
  • It assigns the start index of the unsorted sublist to the min variable. This variable holds the index of the smallest variable of the unsorted sublist. The inner for loop finds the smallest variable from the unsorted sublist and updates the value of min.
  • Once the inner for loop ends, it swaps the smallest value of the unsorted sublist with the first element of the unsorted sublist.
• Inside the main method, it is printing the content of the array before and after it is sorted.

If you run the above program, it will print:

Given Array: 2 8 1 5 30 21
Sorted Array: 1 2 5 8 21 30

Example 2: C++ program to implement selection sort in descending order:

With one small change, we can change the above program to sort the array in descending order instead of ascending.

We have to change the comparison of the elements inside the if block: change if (arr[j] < arr[min]) to if (arr[j] > arr[min]). That’s all. It will find the index of the largest element of the unsorted subarray on each iteration.

Below is the complete program:

#include <iostream>
using namespace std;

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

void swap(int *first, int *second)
{
    int t = *first;
    *first = *second;
    *second = t;
}

void selectionSort(int arr[], int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        int max = i;

        for (int j = i + 1; j < size; j++)
        {
            if (arr[j] > arr[max])
            {
                max = j;
            }
        }

        swap(&arr[max], &arr[i]);
    }
}

int main()
{
    int givenArray[] = {2, 8, 1, 5, 30, 21};
    int size = sizeof(givenArray) / sizeof(givenArray[0]);

    cout << "Given Array: ";
    printArray(givenArray, size);

    selectionSort(givenArray, size);

    cout << "Sorted Array: ";
    printArray(givenArray, size);
}

It will print:

Given Array: 2 8 1 5 30 21 
Sorted Array: 30 21 8 5 2 1 

The time complexity of selection sort:

Selection sort has O(n^2) time complexity. This makes it inefficient for a large array.

You might also like:

• 2 different C++ program to check if a number is spy number or not
• C++ program to insert an element to an array at any position
• C++ program to find the volume of a cylinder in 3 different ways
• C++ program to find the sum of two numbers using friend function
• C++ program to print the days of the week by using switch case
• C++ program to find the area of a rectangle
• C++ program to add the content of two arrays
• C++ program to convert pounds to kilogram
• C++ program to print a diamond shape star pattern
• 2 different C++ program to copy the content of one file to another