Question

The program defined in insertionSort.cpp gets a list of numbers as input from the user and calls the insertion sort algorithm to sort them. It also displays the list before and after the sorting.

The insertion sort algorithm should be defined in the InsertionSort.h file, but this definition has been omitted and it is your task to provide it. The appropriate insertion sort function is to be defined in the InsertionSort.h file.

The InsertionSort.h file performs an include of Swap.h, where a swap function is defined. It accepts an array of integers, a starting index and a destination index, and it swaps the values found in the two specified indices in the list.

You must use this swap function to perform swap operations in your implementation of insertion sort. Do not define a different swap function in InsertionSort.h, and do not perform the swapping manually in place. You have to call the function we are providing for you.

To test your code, run it with inputs of the following structure:

The first line contains an integer N, which specifies the size of the list to be sorted

The next N lines contain a single integer on each line, representing the list we are sorting.
#1fndef #de fine Swap-h Swap-h void swap(int list[, int src, int dest)f temp1ist[src]; list[src] - list[dest] list[dest] -temp; #endif

Answer 1

//Before executing this code, save code in three seprate file: Swap.h, InsertionSort.h, main.cpp

//Swap.h

#ifndef Swap_h

#define Swap_h

//Function to perform swap operation

void swap(int list[], int src, int dest) {

                int temp = list[src];

                list[src] = list[dest];

                list[dest] = temp;

}

#endif

----------------------------------------------------------------------------------------------------------------------------------

//InsertionSort.h

#ifndef InserationSort_h

#define InserationSort_h

#include "Swap.h"

void insertion_sort(int list[], const int size)

{

    int i, j;

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

        j = i;

        // Insert list[i] into list 0..i-1

        while (j > 0 && list[j] < list[j-1]) {

             // Calling swap() function to swap list[j] and list[j-1]

            swap(list, j, j-1);

            // Decrement j by 1

            j--;

        }

    }

}

#endif

----------------------------------------------------------------------------------------------------------------------------

//Driver program main.cpp

#include <iostream>

#include "InsertionSort.h"

using namespace std;

//Function to display the elements of list

void display(int list[], int size, string message) {

                cout << message << endl;

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

                                cout << list[i] << " ";

                }

                cout << endl;

}

int main(int argc, const char * argv[]) {

                int size;

                cout<<"Enter the size of list: ";

                cin >> size;

                const int len = size;

                int numbers[len];

               

                //Taking input from user & storing it into array

                cout<<"Enter the elements for list of size "<<len<<endl;

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

                                int curr;

                                cin>> curr;

                                numbers[i] = curr;

                }

                display(numbers, len, "Before:");     //Calling function to display the insorted list

                insertion_sort(numbers, len);         //Calling function to sort the list

                display(numbers, len, "After:");                //Calling function to display the sorted list

               

                return 0;

}