C++ Program to Implement Insertion Sort

1. Introduction

Selection Sort is another fundamental sorting algorithm that is known for its simplicity. The main idea behind this algorithm is to divide the input list into two parts: a sorted section and an unsorted section. With each iteration, the smallest (or largest, depending on the sorting order) element from the unsorted section is selected and swapped with the first unsorted element, thereby extending the sorted section.

2. Program Overview

Before writing the program, let's take a look into the steps:

1. Prompt the user to input the number of elements in the array.

2. Accept the individual elements of the array from the user.

3. Begin the sorting process by treating the first element of the array as the minimum.

4. Traverse the remaining part of the unsorted array. For each element:

• Compare the element with the current minimum.
• If a smaller element is found, update the minimum.

5. After identifying the smallest element in the unsorted portion, swap this element with the first element in the unsorted part.

6. The boundary of the sorted and unsorted portion is then moved one element to the right.

7. Continue the process by considering the next element as the minimum and repeating the above steps until the entire array is sorted.

8. Display the sorted array to the user.

3. Code Program

#include <iostream>
using namespace std;

// Selection Sort function to sort an array
void selectionSort(int arr[], int n) {
    // Traverse through all array elements
    for (int i = 0; i < n-1; i++) {
        // Find the minimum element's index in unsorted part of array
        int minIdx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIdx])
                minIdx = j;
        }

        // Swap the found minimum element with the first element
        swap(arr[i], arr[minIdx]);
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;

    int arr[n];

    // Accepting the elements of the array from the user
    cout << "Enter the elements of the array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // Sorting the array using the selection sort method
    selectionSort(arr, n);

    // Displaying the sorted array
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

Output:

Enter the number of elements: 5
Enter the elements of the array: 2 1 6 5 4
Sorted array: 1 2 4 5 6 

4. Step By Step Explanation

1. selectionSort Function: This function sorts an array using the Selection Sort technique.

2. MinIdx Element: For each iteration, the function picks the minimum from the unsorted section.

3. Main Function: Initializes an array, sorts it using selectionSort, and then prints the sorted array.

While selection sort is intuitive and easy to implement, it is inefficient on larger lists with a worst-case time complexity of O(n^2). Its main advantage lies in the number of swaps it makes: O(n), making it useful in scenarios where write operation is costly.