My question is with the counting. In my problem the number of the operations after sorting is not giving the same amount as it should. I am using the general logic for the selection sort, insertion sort and merge sort but it is giving in the wrong operations number.
The expected output should look like this:
Enter the number of integer elements: 5
Enter the elements: 4 78 9 35 29
SelectionSort results: 4 9 29 35 78
Required number of operations: 14
InsertionSort results: 4 9 29 35 78
Required number of operations: 12
MergeSort results: 4 9 29 35 78
Required number of operations: 12
But my output is looking like this:
Enter the number of integer elements: 5
Enter the elements: 4 78 9 35 29
SelectionSort results: 4 9 29 35 78
Required number of operations: 10
InsertionSort results: 4 9 29 35 78
Required number of operations: 0
MergeSort results: 4 9 29 35 78
Required number of operations: 7
My code is given below:
#include <iostream>
using namespace std;
// Function to perform Selection Sort
int selectionSort(int arr[], int n)
{
int operations = 0;
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;
}
operations++; // Counting the number of comparisons
}
swap(arr[i], arr[minIndex]);
}
return operations;
}
// Function to perform Insertion Sort
int insertionSort(int arr[], int n)
{
int operations = 0;
for (int i = 1; i < n; ++i)
{
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
operations++; // Counting the number of comparisons and shifts
}
arr[j + 1] = key;
}
return operations;
}
// Function to merge two sorted subarrays in Merge Sort
void merge(int arr[], int left, int mid, int right, int &operations)
{
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
operations++; // Counting the number of comparisons
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Function to perform Merge Sort
void mergeSortHelper(int arr[], int left, int right, int &operations)
{
if (left < right)
{
int mid = left + (right - left) / 2;
mergeSortHelper(arr, left, mid, operations);
mergeSortHelper(arr, mid + 1, right, operations);
merge(arr, left, mid, right, operations);
}
}
int mergeSort(int arr[], int n)
{
int operations = 0;
mergeSortHelper(arr, 0, n - 1, operations);
return operations;
}
int main()
{
int n;
cout << "Enter the number of integer elements: ";
cin >> n;
int arr[n];
cout << "Enter the elements: ";
for (int i = 0; i < n; ++i)
{
cin >> arr[i];
}
int operationsSelection = selectionSort(arr, n);
cout << "SelectionSort results:";
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
cout << "\nRequired number of operations: " << operationsSelection << endl;
int operationsInsertion = insertionSort(arr, n);
cout << "InsertionSort results:";
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
cout << "\nRequired number of operations: " << operationsInsertion << endl;
int operationsMerge = mergeSort(arr, n);
cout << "MergeSort results:";
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
cout << "\nRequired number of operations: " << operationsMerge << endl;
return 0;
}`
