Please use C++ to write this program We would like to do a quick sort on the fol
ID: 3598077 • Letter: P
Question
Please use C++ to write this program
We would like to do a quick sort on the following values. Given the following numbers show the pivot and mark the two arrays that will result after the partition. For each new array show the pivot and the new partitions that will result. Assume ascending sort.
12 10 8 16 25 20 2 4 17 6
First partition and circle pivot (show two arrays after it is partitioned) – Call the left partition array1 and the right partition array2. Show your work!
What is the Pivot and partitions for array1:
What is the Pivot and partitions for array2:
Write the mergesort program and test it on the array values given above.
Explanation / Answer
#include <iostream>
using namespace std;
// Merging 2 subarrays of arr[].
// First subarray is array1=arr[l..m]
// Second subarray is array2=arr[m+1..r]
void merge(int array[], int left, int mid, int right)
{
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
/* create temp arrays */
int LeftSubArray[n1], RightSubArray[n2];
/* Copy data to temp arrays LeftSubArray[] and RightSubArray[] */
for (i = 0; i < n1; i++)
LeftSubArray[i] = array[left + i];
for (j = 0; j < n2; j++)
RightSubArray[j] = array[mid + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = left; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (LeftSubArray[i] <= RightSubArray[j])
{
array[k] = LeftSubArray[i];
i++;
}
else
{
array[k] = RightSubArray[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
array[k] = LeftSubArray[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
array[k] = RightSubArray[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf(" ");
}
/* Driver program to test above functions */
int main()
{
int array[] = {12,10,8,16,25,20,2,4,17,6};
int array_size = sizeof(array)/sizeof(array[0]);
cout<<"Given array is ";
printArray(array, array_size);
mergeSort(array, 0, array_size - 1);
cout<<" Sorted array is ";
printArray(array, array_size);
return 0;
}
/* output:-
*/