Selection Sort | DSA in C++ - Software Development PDF Download

Introduction

Sorting is a fundamental operation in computer science that involves arranging elements in a specific order. One of the simplest and easiest-to-understand sorting algorithms is the Selection Sort. In this article, we will explore the Selection Sort algorithm, its implementation in C++, and provide multiple examples and explanations to help beginners understand its workings.

What is Selection Sort?

Selection Sort is an in-place comparison sorting algorithm. It works by repeatedly finding the minimum (or maximum) element from the unsorted part of the array and swapping it with the element at the beginning of the unsorted part. This process is repeated until the entire array is sorted.

Implementation in C++

Let's begin by understanding the step-by-step implementation of the Selection Sort algorithm in C++. Here's the code:

#include <iostream>

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;

            }

        }

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

    }

}

int main() {

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

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

    selectionSort(arr, n);

    std::cout << "Sorted array: ";

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

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

    }

    return 0;

}

Code Explanation

• The 'selectionSort' function takes an array 'arr[]' and its size 'n' as parameters.
• The outer loop runs from 0 to 'n - 1' to iterate through the array.
• Inside the outer loop, we assume the current element as the minimum and store its index in 'minIndex'.
• The inner loop starts from 'i + 1' and searches for the actual minimum element by comparing each element with the current minimum. If a smaller element is found, we update 'minIndex'.
• After the inner loop finishes, we swap the minimum element (found in minIndex) with the element at index 'i'.
• This process continues until the entire array is sorted.
• In the 'main' function, we create an array 'arr' and its size 'n'.
• We call the 'selectionSort' function passing the array and size as arguments.
• Finally, we print the sorted array.

Example:

Let's walk through an example to understand how the Selection Sort algorithm works. Consider the following unsorted array: '[64, 25, 12, 22, 11]'.

• Iteration 1: The minimum element is 11. Swap it with the first element. Array becomes '[11, 25, 12, 22, 64]'.
• Iteration 2: The minimum element is 12. Swap it with the second element. Array becomes '[11, 12, 25, 22, 64]'.
• Iteration 3: The minimum element is 22. Swap it with the third element. Array becomes '[11, 12, 22, 25, 64]'.
• Iteration 4: The minimum element is 25. Swap it with the fourth element. Array remains '[11, 12, 22, 25, 64]'.
• The array is now sorted.

The output of the program will be:

Sorted array: 11 12 22 25 64

Sample Problems

Here are some sample problems for you to practice:

Problem 1: Sort the given array using Selection Sort: '[7, 2, 9, 1, 5]'.

The sorted array is: '[1, 2, 5, 7, 9]'.

Problem 2: Implement a descending order selection sort algorithm in C++.

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

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

        int maxIndex = i;

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

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

                maxIndex = j;

            }

        }

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

    }

}

Problem 3: Analyze the time complexity of the Selection Sort algorithm.

The time complexity of Selection Sort is O(n^2), where n is the number of elements in the array. This is because there are two nested loops, and the inner loop runs n - 1 times in the worst case.

Conclusion

Selection Sort is a simple yet effective sorting algorithm that is easy to understand and implement. It repeatedly finds the minimum (or maximum) element and swaps it with the first unsorted element. We covered the step-by-step implementation in C++ and provided examples and explanations to help beginners grasp the concept. Practice the sample problems to reinforce your understanding and explore further.