Question

DIRECTIONS: IMPLEMENT QuickSort and MergeSort. You have been provided: 1. Functions to perform Merge (for MergeSort) and Partition (for QuickSort). 2. In class we discussed the body of the recursive functions, the "brakes" needed to stop the recursion. You are expected to develop 2 RECURSIVE programs: 1. Complete the bodies of the sort functions, MergeSort and QuickSort. 2. Complate the main that tests each function. - program should not read inputs - stock the program with multiple arrays (test cases) with different characteristics to demonstratrate the sort works for empty array, 1 element, 2 elements, all values same, already-sorted (ascending/descending). Note: No need to go beyond 16 elements, 3. Your main should clearly identify what the characteristics being tested, the array BEFORE sorting, the array AFTER sorting.

**************************************
MergeSort
**************************************

#include <iostream>
#include <iomanip>
using namespace std;
// ------------------------------------------------------------------
// Function: Complete the following function to merge two sorted arrays
// into a third, merged array.
//
// Example: A={2,4,8}, B={1,3,5,7} ==> Merged = {1,2,3,4,5,7,8}
// A={2,4,8}, B={} ==> Merged = {2,4,8}
// A={}, B={2,8,8} ==> Merged = {2,8,8}
// ------------------------------------------------------------------
void Merge(int A[], int nA, int B[], int nB, int Merged[], int & nMerged)
{
int kA=0, kB=0;
nMerged = 0;

while (kA<nA && kB<nB)
{
if (A[kA] <= B[kB])
Merged[nMerged++] = A[kA++];
else
Merged[nMerged++] = B[kB++];
}

while (kA<nA)
Merged[nMerged++] = A[kA++];

while (kB<nB)
Merged[nMerged++] = B[kB++];

}//Merge

void Merge(int A[], int Asize, int lLO, int lHI, int rLO, int rHI)
{
int Temp[Asize+1]; // Temp array to hold the merge.
   int tnext = lLO; // Cursor for temp array, filled left to right.
  
   int left = lLO, right = rLO;

while (left<=lHI && right <= rHI)
{
if (A[left] <= A[right])
Temp[tnext++] = A[left++];
else
Temp[tnext++] = A[right++];
}

   //-| Copy remaining elements from A[lLO:lHI] (A[rLO:rHI]).
while (left <= lHI)
Temp[tnext++] = A[left++];
  
while (right <= rHI)
Temp[tnext++] = A[right++];

   //-| Copy the Temp sub-array back into array A[lLO:rHI].
   for (int k=lLO; k<=rHI; k++)
A[k] = Temp[k];

}//Merge

/*
void Show(string Label, int X[], int Xsize)
{
cout << endl << Label;
   for (int k=0; k<Xsize; k++)
       cout << X[k] << ' ';
cout << "END" << endl;
}

//#include "mainptalgm9600merge.cpp"
int main()
{
int A1[15] = {5,10,15,20,25,30,35,40,45,50}, N1;
int A2[15] = {2,4,6,8,10,12,14,16,18,20,22}, N2;
int A1A2[30], N12=0;

int B[8] = {3,6,9,10,2,5,10, 12};
  
cout << "Enter N1 N2: ";
cin >> N1 >> N2;

Show("A1: ", A1, N1);
Show("A2: ", A2, N2);
  
Merge(A1,N1,A2,N2, A1A2, N12);

  
Show("Merged A1A2: ", A1A2, N12);

Show ("array B (pre): ", B, 8);
Merge (B,8,0,3,4,7);
Show ("array B (post): ", B, 8);

return 0; // DO NOT DELETE.
}
*/

*****************************************
QuickSort
****************************************

#include <iostream>
#include <cstdlib>
#include <iomanip>
using namespace std;
// ------------------------------------------------------------------
// Function: Partition array around pivot value:
//
// [values < pivotVak] [pivotVal] [vals >= pivotVal]
//
// ------------------------------------------------------------------

void Partition(int A[], int Asize, int lLO, int &lHI, int &rLO, int rHI)
{
   int pivotVal = A[lLO]; // First value used as pivot.
int Temp[rHI+1]; // Temp array to hold the partition as it's being formed..
   int tnext = lLO; // Cursor for temp array, filled left to right.
  
   //-| Fill temp from left-to-right, when val < pivot; right-to-left when >= pivot.
   int left = lLO, right = rHI;

for (int k=lLO+1; k<=rHI; k++)
{
if (A[k] <pivotVal)
Temp[left++] = A[k];
else
Temp[right--] = A[k];
}

   //-| Place pivot value at index left (should be same as right).
   Temp[right] = pivotVal;

   //-| Left partition goes from lLO to left; right from right+1 to rHI.
   lHI = left-1; rLO = right+1;

   //-| Copy the Temp sub-array back into array A[lLO:rHI].
   for (int k=lLO; k<=rHI; k++)
A[k] = Temp[k];

   cout << endl << "PARTITION [" << lLO << ":" << lHI << "] and ["
       << rLO << ":" << rHI << "] " << endl;
             
}//Partition
          

Answer 1

Part 1: Merge Sort:

c++ code:   I have implemented 2 MergeSort function. 1 MergeSort definition for each Merge definition.

Bold text code I have updated because Previous declaration was not working with my system. If previous declaration was working for your system then you can use previous decalaration.

//============================================================================

//**************************************
//MergeSort
//**************************************

#include <iostream>
#include <iomanip>
using namespace std;
// ------------------------------------------------------------------
// Function: Complete the following function to merge two sorted arrays
// into a third, merged array.
//
// Example: A={2,4,8}, B={1,3,5,7} ==> Merged = {1,2,3,4,5,7,8}
// A={2,4,8}, B={} ==> Merged = {2,4,8}
// A={}, B={2,8,8} ==> Merged = {2,8,8}
// ------------------------------------------------------------------
void Merge(int A[], int nA, int B[], int nB, int Merged[], int & nMerged)
{
   int kA = 0, kB = 0;
   nMerged = 0;

   while (kA<nA && kB<nB)
   {
       if (A[kA] <= B[kB])
           Merged[nMerged++] = A[kA++];
       else
           Merged[nMerged++] = B[kB++];
   }

   while (kA<nA)
       Merged[nMerged++] = A[kA++];

   while (kB<nB)
       Merged[nMerged++] = B[kB++];

}//Merge

void Merge(int A[], int Asize, int lLO, int lHI, int rLO, int rHI)
{
   int *Temp = new int [Asize+1]; // Temp array to hold the merge.   // updated
   int tnext = lLO; // Cursor for temp array, filled left to right.

   int left = lLO, right = rLO;

   while (left <= lHI && right <= rHI)
   {
       if (A[left] <= A[right])
           Temp[tnext++] = A[left++];
       else
           Temp[tnext++] = A[right++];
   }

   //-| Copy remaining elements from A[lLO:lHI] (A[rLO:rHI]).
   while (left <= lHI)
       Temp[tnext++] = A[left++];

   while (right <= rHI)
       Temp[tnext++] = A[right++];

   //-| Copy the Temp sub-array back into array A[lLO:rHI].
   for (int k = lLO; k <= rHI; k++)
       A[k] = Temp[k];

}//Merge

// MergeSort function using first Merge definition
void MergeSort(int A[], int LO, int HI)
{
   // this is to check array from LO to HI contain atlest 2 element
   if (LO < HI)
   {
       //calculate mid element
       int mid = LO + (HI - LO) / 2;
       // call recursion on to sort lower half array from LO to mid element
       MergeSort(A, LO, mid);
       // call recursion on to sort upper half array from mid+1 to HI
       MergeSort(A, mid + 1, HI);

       // Above to recursion call will sort lower half and upper half array seperatly
       // Merge function will now merge sorted arrays
       int merge_size;
       int *merged_array = new int[HI - LO + 1];
       Merge((A + LO), mid - LO + 1, (A + mid + 1), HI - mid, merged_array, merge_size);
       //copy merged array back to main array;
       for (int i = 0; i < merge_size; i++)
       {
           A[LO + i] = merged_array[i];
       }
   }
}//MergeSort

// MergeSort function using second Merge definition
void MergeSort(int A[],int Asize, int LO, int HI)
{
   // this is to check array from LO to HI contain atlest 2 element
   if (LO < HI)
   {
       //calculate mid element
       int mid = LO + (HI - LO) / 2;
       // call recursion on to sort lower half array from LO to mid element
       MergeSort(A, Asize, LO, mid);
       // call recursion on to sort upper half array from mid+1 to HI
       MergeSort(A, Asize, mid + 1, HI);

       // Above to recursion call will sort lower half and upper half array seperatly
       // Merge function will now merge sorted arrays
       Merge(A, Asize, LO, mid, mid + 1, HI);
   }
}//MergeSort

void Show(char* Label, int X[], int Xsize)
{
cout << Label;
for (int k=0; k<Xsize; k++)
cout << X[k] << ' ';
cout << endl;
}

int main()
{
int A1[11] = {5,10,15,20,25,30,35,40,45,50,55};
int A2[16] = {100,90,80,70,60,50,40,30,20,10,9,8,7,6,5,4};
int A3[10] = { 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 };
int A4[2] = { 10, 5 };
int A5[1] = { 9 };
int A6[10] = { 41, 25, 10, 78, 96, 52, 12, 34, 96, 10 };
int A7[10];
int A8[6] = { 0, 74, 23, 52, 21, 56 };

cout << "*************Merge Sort**************************" << endl;

cout << "\nEmpty Array Sorting :" << endl;
Show("Before sorting A :", A7, 0);
MergeSort(A7, 0, 0);               // sorting using first definition of merge sort
Show("After sorting A :", A7, 0);

cout << "\nOne element Array Sorting :" << endl;
Show("Before sorting A :", A5, 1);
MergeSort(A5, 0, 0);               // sorting using first definition of merge sort
Show("After sorting A :", A5, 1);

cout << "\nAlready sorted(ascending) Array Sorting :" << endl;
Show("Before sorting A :", A1, 11);
MergeSort(A1, 0, 10);               // sorting using first definition of merge sort
Show("After sorting A :", A1, 11);

cout << "\nAlready sorted(descending) Array Sorting :" << endl;
Show("Before sorting A :", A2, 16);
MergeSort(A2,16, 0, 15);           // sorting using second definition of merge sort
Show("After sorting A :", A2, 16);

cout << "\n Same element Array Sorting :" << endl;
Show("Before sorting A :", A3, 10);
MergeSort(A3, 10, 0, 9);           // sorting using second definition of merge sort
Show("After sorting A :", A3, 10);

cout << "\nTwo element Array Sorting :" << endl;
Show("Before sorting A :", A4, 2);
MergeSort(A4, 2, 0, 1);           // sorting using second definition of merge sort
Show("After sorting A :", A4, 2);

cout << "\nRandom Array Sorting :" << endl;
Show("Before sorting A :", A6, 10);
MergeSort(A6, 10, 0, 9);           // sorting using second definition of merge sort
Show("After sorting A :", A6, 10);

cout << "\nRandom Array Sorting :" << endl;
Show("Before sorting A :", A8, 6);
MergeSort(A8, 0, 5);               // sorting using first definition of merge sort
Show("After sorting A :", A8, 6);

return 0; // DO NOT DELETE.
}

//============================================================================

output :

Part 2: Quick Sort

C++ code: Bold text code I have updated because Previous declaration was not working with my system. If previous declaration was working for your system then you can use previous decalaration.

//=============================================================================

//*****************************************
//QuickSort
//****************************************

#include <iostream>
#include <cstdlib>
#include <iomanip>
using namespace std;
// ------------------------------------------------------------------
// Function: Partition array around pivot value:
//
// [values < pivotVak] [pivotVal] [vals >= pivotVal]
//
// ------------------------------------------------------------------

void Partition(int A[], int Asize, int lLO, int &lHI, int &rLO, int rHI)
{
   int pivotVal = A[lLO]; // First value used as pivot.
   int *Temp = new int [rHI + 1]; // Temp array to hold the partition as it's being formed.. // updated
   int tnext = lLO; // Cursor for temp array, filled left to right.

   //-| Fill temp from left-to-right, when val < pivot; right-to-left when >= pivot.
   int left = lLO, right = rHI;

   for (int k = lLO + 1; k <= rHI; k++)
   {
       if (A[k] <pivotVal)
           Temp[left++] = A[k];
       else
           Temp[right--] = A[k];
   }

   //-| Place pivot value at index left (should be same as right).
   Temp[right] = pivotVal;

   //-| Left partition goes from lLO to left; right from right+1 to rHI.
   lHI = left - 1; rLO = right + 1;

   //-| Copy the Temp sub-array back into array A[lLO:rHI].
   for (int k = lLO; k <= rHI; k++)
       A[k] = Temp[k];

   //cout << endl << "PARTITION [" << lLO << ":" << lHI << "] and ["
       //<< rLO << ":" << rHI << "] " << endl;

}//Partition

//A[] - array which we want to sort
// LO - left index of array
//HI - highest index of array
// Asize - size of array;
void QuickSort(int A[], int Asize, int LO, int HI)
{
   // this is to check array from LO to HI contain atlest 2 element
   if (LO < HI)
   {
       int lHI, rLO;
       // find left partition of array and right partition of array
       // such that all elemnt in array left to pivot is smaller
       // and all element in array right to pivot is bigger
       Partition(A, Asize, LO, lHI, rLO, HI);
       // call recursion function of left side array of pivot
       QuickSort(A, Asize, LO, lHI);
       // call recursion function of right side array of pivot
       QuickSort(A, Asize, rLO, HI);
   }
} //QuickSort

// print array
void Show(char* Label, int X[], int Xsize)
{
   cout << Label;
   for (int k = 0; k<Xsize; k++)
       cout << X[k] << ' ';
   cout << endl;
}

int main()
{
   int A1[11] = { 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55 };
   int A2[16] = { 100, 90, 80, 70, 60, 50, 40, 30, 20, 10, 9, 8, 7, 6, 5, 4 };
   int A3[10] = { 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 };
   int A4[2] = { 10, 5 };
   int A5[1] = { 9 };
   int A6[10] = { 41, 25, 10, 78, 96, 52, 12, 34, 96, 10 };
   int A7[10];
   int A8[6] = { 0, 74, 23, 52, 21, 56 };

   cout << "******************QuickSort*********************" << endl;
   cout << "\nEmpty Array Sorting :" << endl;
   Show("Before sorting A :", A7, 0);
   QuickSort(A7, 0,0, 0);               // sorting using Quicksort
   Show("After sorting A :", A7, 0);

   cout << "\nOne element Array Sorting :" << endl;
   Show("Before sorting A :", A5, 1);
   QuickSort(A5,1, 0, 0);               // sorting using QuickSort
   Show("After sorting A :", A5, 1);

   cout << "\nAlready sorted(ascending) Array Sorting :" << endl;
   Show("Before sorting A :", A1, 11);
   QuickSort(A1,11, 0, 10);               // sorting using QuickSort
   Show("After sorting A :", A1, 11);

   cout << "\nAlready sorted(descending) Array Sorting :" << endl;
   Show("Before sorting A :", A2, 16);
   QuickSort(A2, 16, 0, 15);           // sorting using QuickSort
   Show("After sorting A :", A2, 16);

   cout << "\n Same element Array Sorting :" << endl;
   Show("Before sorting A :", A3, 10);
   QuickSort(A3, 10, 0, 9);           // sorting using QuickSort
   Show("After sorting A :", A3, 10);

   cout << "\nTwo element Array Sorting :" << endl;
   Show("Before sorting A :", A4, 2);
   QuickSort(A4, 2, 0, 1);           // sorting using QuickSort
   Show("After sorting A :", A4, 2);

   cout << "\nRandom Array Sorting :" << endl;
   Show("Before sorting A :", A6, 10);
   QuickSort(A6, 10, 0, 9);           // sorting using QuickSort
   Show("After sorting A :", A6, 10);

   cout << "\nRandom Array Sorting :" << endl;
   Show("Before sorting A :", A8, 6);
   QuickSort(A8,6, 0, 5);               // sorting using QuickSort
   Show("After sorting A :", A8, 6);

   return 0; // DO NOT DELETE.
}

//=============================================================================

output: