Code: Insertion sort | Basics of C++ - Software Development PDF Download

Introduction

Sorting is a fundamental operation in computer science and is essential for organizing data efficiently. Insertion sort is a simple sorting algorithm that builds the final sorted array one element at a time. It is often used for small datasets or as a part of more complex sorting algorithms. In this article, we will explore how insertion sort works and implement it in C++.

How Insertion Sort Works

Insertion sort works by dividing the input array into two sections: the sorted section and the unsorted section. Initially, the sorted section consists of only the first element, and the rest of the array is considered unsorted. The algorithm iterates through the unsorted section, takes each element, and inserts it into its correct position in the sorted section. This process continues until the entire array is sorted.

The key steps of the insertion sort algorithm are as follows:

• Start with the first element as the sorted section.
• Pick the next unsorted element and compare it with the elements in the sorted section.
• Shift the elements in the sorted section that are larger than the unsorted element to the right.
• Insert the unsorted element into its correct position in the sorted section.
• Repeat steps 2-4 until all elements are in the sorted section.

Implementation in C++

Let's see how we can implement the insertion sort algorithm in C++. We'll start by writing a function called 'insertionSort' that takes an array of integers and sorts it using insertion sort.

#include <iostream>

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

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

        int key = arr[i];

        int j = i - 1;

        // Shift elements in the sorted section

        // that are larger than the key to the right

        while (j >= 0 && arr[j] > key) {

            arr[j + 1] = arr[j];

            j--;

        }

        // Insert the key into its correct position

        arr[j + 1] = key;

    }

}

In the code above, we start iterating from the second element ('i = 1') and compare it with the elements in the sorted section (j = i - 1'). We shift the elements in the sorted section that are larger than the key to the right until we find the correct position for the key. Finally, we insert the key into its correct position.

Example Usage

Now let's see how we can use the 'insertionSort' function to sort an array of integers.

int main() {

    int arr[] = {4, 2, 9, 1, 6};

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

    std::cout << "Original array: ";

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

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

    }

    std::cout << std::endl;

    insertionSort(arr, size);

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

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

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

    }

    std::cout << std::endl;

    return 0;

}

Output

Original array: 4 2 9 1 6

Sorted array: 1 2 4 6 9

In the example above, we initialize an array 'arr' with some random integers. We calculate the size of the array and then call the 'insertionSort' function to sort the array. Finally, we print the original and sorted arrays to verify the correctness of the algorithm.

Time Complexity

The time complexity of insertion sort is O(n^2) in the worst and average cases. This is because, in the worst case, each element needs to be compared with all the elements in the sorted section, resulting in nested loops. However, in the best case scenario where the input array is already sorted, the time complexity reduces to O(n) since no element needs to be shifted.

Sample Problems

1. Write a program to sort an array of strings using insertion sort.

#include <iostream>

#include <string>

void insertionSort(std::string arr[], int size) {

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

        std::string key = arr[i];

        int j = i - 1;

        while (j >= 0 && arr[j] > key) {

            arr[j + 1] = arr[j];

            j--;

        }

        arr[j + 1] = key;

    }

}

int main() {

    std::string arr[] = {"apple", "banana", "orange", "grape", "cherry"};

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

    std::cout << "Original array: ";

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

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

    }

    std::cout << std::endl;

    insertionSort(arr, size);

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

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

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

    }

    std::cout << std::endl;

    return 0;

}

Output

Original array: apple banana orange grape cherry

Sorted array: apple banana cherry grape orange

2. Implement a modified version of insertion sort that sorts an array in descending order.

#include <iostream>

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

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

        int key = arr[i];

        int j = i - 1;

        while (j >= 0 && arr[j] < key) {

            arr[j + 1] = arr[j];

            j--;

        }

        arr[j + 1] = key;

    }

}

int main() {

    int arr[] = {4, 2, 9, 1, 6};

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

    std::cout << "Original array: ";

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

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

    }

    std::cout << std::endl;

    insertionSortDescending(arr, size);

    std::cout << "Sorted array (descending): ";

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

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

    }

    std::cout << std::endl;

    return 0;

}

Output

Original array: 4 2 9 1 6

Sorted array (descending): 9 6 4 2 1

In this modified version, we simply change the comparison condition in the while loop from arr[j] > key to 'arr[j] < key' to 'sort' the array in descending order.

Conclusion

Insertion sort is a simple yet effective sorting algorithm that is easy to understand and implement. It works well for small datasets or as a part of more complex sorting algorithms. By following the steps outlined in this article, you should now have a good understanding of how insertion sort works and how to implement it in C++. So go ahead and try it out in your own programs!