×
Samples Blogs Make Payment About Us Reviews 4.9/5 Order Now

Create A Program to Implement Merge Sort Algorithm in C++ Assignment Solution.

July 08, 2024
Dr. Isabelle Taylor
Dr. Isabelle
🇦🇺 Australia
C++
Dr. Taylor is a seasoned researcher with a Ph.D. in Computer Engineering from the University of Melbourne. With over 600 completed orders, she specializes in operating systems and multithreading in C++, providing insightful solutions that demonstrate practical application and theoretical understanding.
Key Topics
  • Instructions
    • Objective
  • Requirements and Specifications
Tip of the day
For HTML assignments, ensure that your code is clean and properly indented. This improves readability and helps identify errors quickly. Use semantic tags (like <header>, <article>, and <footer>) to enhance accessibility.
News
In 2024, the new programming language Mojo is gaining traction among AI-focused programming students, promising Python-like simplicity with speeds closer to C++ for AI and scientific applications​.

Instructions

Objective

Write a C++ assignment program to implement merge sort algorithm.

Requirements and Specifications

You are given the C++ code for the Merge Sort algorithm. The code as such would input the array size value, then generate/print a random array of specified size with values ranging from 1 to 50 and output the sorted array.

Your task in this assignment is to modify the code for the algorithm to determine the number of inversions in an array as well as print the inverted pairs.

After the enhancement, the output of the code should be both the initial randomly generated array and the final sorted array as well as the number of inversions in the initial randomly generated array and the inverted pairs accounting for the number of inversions.

Screenshot

Program-to-implement-merge-sort-algorithm-in-C (1)

Source Code

#include #include //srand, rand #include //clock_t, clock, CLOCKS_PER_SEC #include #include #include using namespace std; void PrintArray(int* arrayPtr, int arraySize){ for (int i = 0; i < arraySize; i++) cout << arrayPtr[i] << " "; cout << endl; } long Merge(int* leftSubArrayPtr, int leftArraySize, int *rightSubArrayPtr, int rightArraySize, int *arrayPtr, int arraySize){ int leftIndex = 0; int rightIndex = 0; int arrayIndex = 0; long counter = 0; while (leftIndex < leftArraySize && rightIndex < rightArraySize){ if (leftSubArrayPtr[leftIndex] <= rightSubArrayPtr[rightIndex]){ arrayPtr[arrayIndex] = leftSubArrayPtr[leftIndex]; leftIndex++; } else{ arrayPtr[arrayIndex] = rightSubArrayPtr[rightIndex]; counter += leftArraySize - leftIndex; for(int i = leftIndex; i < leftArraySize; i++) { cout << leftSubArrayPtr[i] << " " << rightSubArrayPtr[rightIndex] << endl; } rightIndex++; } arrayIndex++; } if (leftIndex == leftArraySize){ for (; rightIndex < rightArraySize; rightIndex++){ arrayPtr[arrayIndex] = rightSubArrayPtr[rightIndex]; arrayIndex++; } } else{ for (; leftIndex < leftArraySize; leftIndex++){ arrayPtr[arrayIndex] = leftSubArrayPtr[leftIndex]; arrayIndex++; } } return counter; } long MergeSort(int* arrayPtr, int arraySize){ if (arraySize > 1) { int* leftSubArrayPtr = new int[arraySize/2]; int* rightSubArrayPtr = new int[arraySize - arraySize/2]; for (int i = 0; i < (arraySize/2); i++) leftSubArrayPtr[i] = arrayPtr[i]; for (int i = arraySize/2; i < arraySize; i++) rightSubArrayPtr[i-(arraySize/2)] = arrayPtr[i]; long leftInvs = MergeSort(leftSubArrayPtr, arraySize/2); long rightInvs = MergeSort(rightSubArrayPtr, arraySize - arraySize/2); long mergeInvs = Merge(leftSubArrayPtr, arraySize/2, rightSubArrayPtr, arraySize - arraySize/2, arrayPtr, arraySize); return leftInvs + rightInvs + mergeInvs; } else { return 0; } } int main(){ int arraySize; cout << "Enter array size: "; cin >> arraySize; int maxVal = 50; srand(time(NULL)); int* arrayPtr = new int[arraySize]; for (int i = 0; i < arraySize; i++) arrayPtr[i] = 1 + rand() % maxVal; cout << "Before sorting..." << endl; PrintArray(arrayPtr, arraySize); cout << "Inversions: " << endl; long invs = MergeSort(arrayPtr, arraySize); cout << "Number of Inversions: " << invs << endl; cout << "After sorting..." << endl; PrintArray(arrayPtr, arraySize); system("pause"); return 0; }

Similar Samples

Explore our curated selection of programming assignment samples at ProgrammingHomeworkHelp.com. Each sample exemplifies our expertise in Java, Python, C++, and more, showcasing detailed problem-solving and clear coding techniques. See how our solutions can guide you towards mastering programming concepts and achieving academic success.