Write a program in C++ to do the following: Your program should perform the foll
ID: 3737723 • Letter: W
Question
Write a program in C++ to do the following: Your program should perform the following:
a. Randomly generate three integer arrays A1, A2, and A3 of sizes N=103 , 105 , and 107 (or 106 , if your computer cannot handle an integer array of size 107 ), in that order.
b. Run the sorting algorithm HEAP SORT on each of the three arrays A1, A2 and A3, and record the number of comparisons between array elements and actual elapsed times in appropriate time units, for instance, milliseconds.
c. Repeat b on the sorted arrays A1, A2 and A3.
d. Reverse the order of the three arrays A1, A2 and A3 and repeat b once more.
So basically im asking for 3 codes 1 with the ramdom arrays of the specific sizes (1000,10000 and 10000000) another one with the arrays already ordered (increasing 1,2,3,4,....N) and another with the arrays in decreasing order (N...4,3,2,1) for HEAP SORT this is very important because the point of the exercise is to analyze the running times on best, average and worst case for the algorithm.
Explanation / Answer
// C++ program for implementation of Heap Sort
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <time.h>
using namespace std;
int countSwap = 0;
// Utility function to heapify a subtree rooted with node c which is an index in numbers[]. len is size of heap
void utilityHeapify(int numbers[], int len, int c)
{
// Initialize largest as root
int largest = c;
// left = 2 * c + 1
int left = 2 * c + 1;
// right = 2 * c + 2
int right = 2 * c + 2;
// Checks if left child is larger than root
if (left < len && numbers[left] > numbers[largest])
largest = left;
// Checks if right child is larger than largest so far
if (right < len && numbers[right] > numbers[largest])
largest = right;
// Checks if largest is not root
if (largest != c)
{
swap(numbers[c], numbers[largest]);
countSwap++;
// Recursively calls the function heapify the affected sub-tree
utilityHeapify(numbers, len, largest);
}// End of if condition
}// End of function
// Function to do heap sort, len is the size of the array
void heapSort(int numbers[], int len)
{
// Build heap (rearrange array)
for (int c = len / 2 - 1; c >= 0; c--)
utilityHeapify(numbers, len, c);
// One by one extract an element from heap
for (int c = len - 1; c >= 0; c--)
{
// Move current root to end
swap(numbers[0], numbers[c]);
countSwap++;
// call max heapify on the reduced heap
utilityHeapify(numbers, c, 0);
}// End of for loop
}// End of function
// Function to display the array contents
void printArray(int numbers[], int len)
{
// Loops till length of the array
for (int c = 0; c < len; ++c)
cout << numbers[c] << " ";
cout << " ";
}// End of function
// Function to generate random number and store it in array
void generateRandomNumber(int numbers[], int len)
{
// Sets the max and min for random number range
int max = 10000, min = 1;
// seed the random number generator once and only once
srand(time(0));
// Loops till length of the array
for(int x = 0; x < len; x++)
// Generates random number between max and min and stores it in array
numbers[x] = rand() % (max - min) + min;
}// End of function
// Function to reverse the array contents
void reverseArray(int number[], int len)
{
// Creates a temporary array of size len
int temp[len];
// Loops reverse order or original array
for(int x = len-1, c = 0; x >= 0; x--, c++)
// Stores last last index position order of index x position value of array number
// in starting order position of index c position of array temp
temp[c] = number[x];
// Loops length of the array
for(int x = 0; x < len; x++)
// Stores each index position of temp data in original array
number[x] = temp[x];
}// End of function
// main function definition
int main()
{
// To start time and end time
clock_t startTime, stopTime;
// Declares three arrays
int arr1[103];
int arr2[105];
int arr3[107];
// Calls the function to generate random number and store it in array
generateRandomNumber(arr1, 103);
generateRandomNumber(arr3, 105);
generateRandomNumber(arr2, 107);
// Displays original array
cout<<" Original Array1 ";
printArray(arr1, 103);
// Initialize swap counter to zero
countSwap = 0;
// Stores the start time
startTime = clock();
// Calls the function to sort
heapSort(arr1, 103);
// Stores the end time
stopTime = clock();
// Displays sorted array
cout << " Sorted Array1 ";
printArray(arr1, 103);
// Displays the time taken
cout <<" Array1 Time: " << (stopTime - startTime);
// Displays number of swap required
cout<<" Array1 Number of swapping required: "<<countSwap;
cout<<" Original Array2 ";
printArray(arr2, 105);
countSwap = 0;
startTime = clock();
heapSort(arr2, 105);
stopTime = clock();
cout << " Sorted Array2 ";
printArray(arr2, 105);
cout <<" Array2 Time: " << (stopTime - startTime);
cout<<" Array2 Number of swapping required: "<<countSwap;
cout<<" Original Array3 ";
printArray(arr3, 107);
countSwap = 0;
startTime = clock();
heapSort(arr3, 107);
stopTime = clock();
cout << " Sorted Array3 ";
printArray(arr3, 107);
cout <<" Array3 Time: " << (stopTime - startTime);
cout<<" Array3 Number of swapping required: "<<countSwap;
// Operation c on sorted array
countSwap = 0;
startTime = clock();
heapSort(arr1, 103);
stopTime = clock();
cout <<" Sort Sorted Array1 ";
printArray(arr1, 103);
cout <<" Array1 Time: " << (stopTime - startTime);
cout<<" Array1 Number of swapping required: "<<countSwap;
countSwap = 0;
startTime = clock();
heapSort(arr2, 105);
stopTime = clock();
cout <<" Sort Sorted Array2 ";
printArray(arr2, 105);
cout <<" Array2 Time: " << (stopTime - startTime);
cout<<" Array2 Number of swapping required: "<<countSwap;
countSwap = 0;
startTime = clock();
heapSort(arr3, 107);
stopTime = clock();
cout << " Sort Sorted Array3 ";
printArray(arr3, 107);
cout <<" Array3 Time: " << (stopTime - startTime);
cout<<" Array3 Number of swapping required: "<<countSwap;
// Operation d
reverseArray(arr1, 103);
cout<<" Reverse Array1 ";
printArray(arr1, 103);
countSwap = 0;
startTime = clock();
heapSort(arr1, 103);
stopTime = clock();
cout << " Sort Sorted Array3 ";
printArray(arr1, 103);
cout <<" Array1 Time: " << (stopTime - startTime);
cout<<" Array1 Number of swapping required: "<<countSwap;
reverseArray(arr2, 105);
cout<<" Reverse Array1 ";
printArray(arr2, 103);
countSwap = 0;
startTime = clock();
heapSort(arr2, 105);
stopTime = clock();
cout << " Sort Sorted Array3 ";
printArray(arr2, 105);
cout <<" Array2 Time: " << (stopTime - startTime);
cout<<" Array2 Number of swapping required: "<<countSwap;
reverseArray(arr3, 107);
cout<<" Reverse Array1 ";
printArray(arr3, 107);
countSwap = 0;
startTime = clock();
heapSort(arr3, 107);
stopTime = clock();
cout << " Sort Sorted Array3 ";
printArray(arr3, 107);
cout <<" Array3 Time: " << (stopTime - startTime);
cout<<" Array3 Number of swapping required: "<<countSwap;
}
Sample Run:
Original Array1
2131 1042 3289 1237 2650 2249 598 8979 4850 9921 5718 9542 8668 394 7146 1481 3321 6561 3088 8017 5832 8702 9027 3521 5961 2579 7742 1387 2414 3331 8112 2327 281 1118 3731 4796 6743 5800 1506 8821 2949 5547 3565 3431 2221 2307 9144 7598 6489 8306 4970 686 631 6055 2963 7138 312 9969 1983 1511 3179 3073 1598 5214 1140 3024 8204 8780 9715 5507 9433 4524 5007 1301 4404 6522 3019 1779 3354 3520 3712 3632 8886 1095 7296 8064 4439 3003 1631 8704 9424 5992 6206 508 2913 5143 364 7986 3994 8441 4609 6580 5257
Sorted Array1
281 312 364 394 508 598 631 686 1042 1095 1118 1140 1237 1301 1387 1481 1506 1511 1598 1631 1779 1983 2131 2221 2249 2307 2327 2414 2579 2650 2913 2949 2963 3003 3019 3024 3073 3088 3179 3289 3321 3331 3354 3431 3520 3521 3565 3632 3712 3731 3994 4404 4439 4524 4609 4796 4850 4970 5007 5143 5214 5257 5507 5547 5718 5800 5832 5961 5992 6055 6206 6489 6522 6561 6580 6743 7138 7146 7296 7598 7742 7986 8017 8064 8112 8204 8306 8441 8668 8702 8704 8780 8821 8886 8979 9027 9144 9424 9433 9542 9715 9921 9969
Array1 Time: 0
Array1 Number of swapping required: 596
Original Array2
2131 1042 3289 1237 2650 2249 598 8979 4850 9921 5718 9542 8668 394 7146 1481 3321 6561 3088 8017 5832 8702 9027 3521 5961 2579 7742 1387 2414 3331 8112 2327 281 1118 3731 4796 6743 5800 1506 8821 2949 5547 3565 3431 2221 2307 9144 7598 6489 8306 4970 686 631 6055 2963 7138 312 9969 1983 1511 3179 3073 1598 5214 1140 3024 8204 8780 9715 5507 9433 4524 5007 1301 4404 6522 3019 1779 3354 3520 3712 3632 8886 1095 7296 8064 4439 3003 1631 8704 9424 5992 6206 508 2913 5143 364 7986 3994 8441 4609 6580 5257 5502 2659
Sorted Array2
281 312 364 394 508 598 631 686 1042 1095 1118 1140 1237 1301 1387 1481 1506 1511 1598 1631 1779 1983 2131 2221 2249 2307 2327 2414 2579 2650 2659 2913 2949 2963 3003 3019 3024 3073 3088 3179 3289 3321 3331 3354 3431 3520 3521 3565 3632 3712 3731 3994 4404 4439 4524 4609 4796 4850 4970 5007 5143 5214 5257 5502 5507 5547 5718 5800 5832 5961 5992 6055 6206 6489 6522 6561 6580 6743 7138 7146 7296 7598 7742 7986 8017 8064 8112 8204 8306 8441 8668 8702 8704 8780 8821 8886 8979 9027 9144 9424 9433 9542 9715 9921 9969
Array2 Time: 0
Array2 Number of swapping required: 625
Original Array3
3846 899 3289 1237 2650 2249 598 8979 4850 9921 5718 9542 8668 394 7146 1481 3321 6561 3088 8017 5832 8702 9027 3521 5961 2579 7742 1387 2414 3331 8112 2327 281 1118 3731 4796 6743 5800 1506 8821 2949 5547 3565 3431 2221 2307 9144 7598 6489 8306 4970 686 631 6055 2963 7138 312 9969 1983 1511 3179 3073 1598 5214 1140 3024 8204 8780 9715 5507 9433 4524 5007 1301 4404 6522 3019 1779 3354 3520 3712 3632 8886 1095 7296 8064 4439 3003 1631 8704 9424 5992 6206 508 2913 5143 364 7986 3994 8441 4609 6580 5257 5502 2659 1994421309 4312256
Sorted Array3
281 312 364 394 508 598 631 686 899 1095 1118 1140 1237 1301 1387 1481 1506 1511 1598 1631 1779 1983 2221 2249 2307 2327 2414 2579 2650 2659 2913 2949 2963 3003 3019 3024 3073 3088 3179 3289 3321 3331 3354 3431 3520 3521 3565 3632 3712 3731 3846 3994 4404 4439 4524 4609 4796 4850 4970 5007 5143 5214 5257 5502 5507 5547 5718 5800 5832 5961 5992 6055 6206 6489 6522 6561 6580 6743 7138 7146 7296 7598 7742 7986 8017 8064 8112 8204 8306 8441 8668 8702 8704 8780 8821 8886 8979 9027 9144 9424 9433 9542 9715 9921 9969 4312256 1994421309
Array3 Time: 0
Array3 Number of swapping required: 642
Sort Sorted Array1
281 312 364 394 508 598 631 686 1042 1095 1118 1140 1237 1301 1387 1481 1506 1511 1598 1631 1779 1983 2131 2221 2249 2307 2327 2414 2579 2650 2913 2949 2963 3003 3019 3024 3073 3088 3179 3289 3321 3331 3354 3431 3520 3521 3565 3632 3712 3731 3994 4404 4439 4524 4609 4796 4850 4970 5007 5143 5214 5257 5507 5547 5718 5800 5832 5961 5992 6055 6206 6489 6522 6561 6580 6743 7138 7146 7296 7598 7742 7986 8017 8064 8112 8204 8306 8441 8668 8702 8704 8780 8821 8886 8979 9027 9144 9424 9433 9542 9715 9921 9969
Array1 Time: 0
Array1 Number of swapping required: 667
Sort Sorted Array2
281 312 364 394 508 598 631 686 1042 1095 1118 1140 1237 1301 1387 1481 1506 1511 1598 1631 1779 1983 2131 2221 2249 2307 2327 2414 2579 2650 2659 2913 2949 2963 3003 3019 3024 3073 3088 3179 3289 3321 3331 3354 3431 3520 3521 3565 3632 3712 3731 3994 4404 4439 4524 4609 4796 4850 4970 5007 5143 5214 5257 5502 5507 5547 5718 5800 5832 5961 5992 6055 6206 6489 6522 6561 6580 6743 7138 7146 7296 7598 7742 7986 8017 8064 8112 8204 8306 8441 8668 8702 8704 8780 8821 8886 8979 9027 9144 9424 9433 9542 9715 9921 9969
Array2 Time: 0
Array2 Number of swapping required: 675
Sort Sorted Array3
281 312 364 394 508 598 631 686 899 1095 1118 1140 1237 1301 1387 1481 1506 1511 1598 1631 1779 1983 2221 2249 2307 2327 2414 2579 2650 2659 2913 2949 2963 3003 3019 3024 3073 3088 3179 3289 3321 3331 3354 3431 3520 3521 3565 3632 3712 3731 3846 3994 4404 4439 4524 4609 4796 4850 4970 5007 5143 5214 5257 5502 5507 5547 5718 5800 5832 5961 5992 6055 6206 6489 6522 6561 6580 6743 7138 7146 7296 7598 7742 7986 8017 8064 8112 8204 8306 8441 8668 8702 8704 8780 8821 8886 8979 9027 9144 9424 9433 9542 9715 9921 9969 4312256 1994421309
Array3 Time: 0
Array3 Number of swapping required: 699
Reverse Array1
9969 9921 9715 9542 9433 9424 9144 9027 8979 8886 8821 8780 8704 8702 8668 8441 8306 8204 8112 8064 8017 7986 7742 7598 7296 7146 7138 6743 6580 6561 6522 6489 6206 6055 5992 5961 5832 5800 5718 5547 5507 5257 5214 5143 5007 4970 4850 4796 4609 4524 4439 4404 3994 3731 3712 3632 3565 3521 3520 3431 3354 3331 3321 3289 3179 3088 3073 3024 3019 3003 2963 2949 2913 2650 2579 2414 2327 2307 2249 2221 2131 1983 1779 1631 1598 1511 1506 1481 1387 1301 1237 1140 1118 1095 1042 686 631 598 508 394 364 312 281
Sort Sorted Array3
281 312 364 394 508 598 631 686 1042 1095 1118 1140 1237 1301 1387 1481 1506 1511 1598 1631 1779 1983 2131 2221 2249 2307 2327 2414 2579 2650 2913 2949 2963 3003 3019 3024 3073 3088 3179 3289 3321 3331 3354 3431 3520 3521 3565 3632 3712 3731 3994 4404 4439 4524 4609 4796 4850 4970 5007 5143 5214 5257 5507 5547 5718 5800 5832 5961 5992 6055 6206 6489 6522 6561 6580 6743 7138 7146 7296 7598 7742 7986 8017 8064 8112 8204 8306 8441 8668 8702 8704 8780 8821 8886 8979 9027 9144 9424 9433 9542 9715 9921 9969
Array1 Time: 0
Array1 Number of swapping required: 528
Reverse Array1
9969 9921 9715 9542 9433 9424 9144 9027 8979 8886 8821 8780 8704 8702 8668 8441 8306 8204 8112 8064 8017 7986 7742 7598 7296 7146 7138 6743 6580 6561 6522 6489 6206 6055 5992 5961 5832 5800 5718 5547 5507 5502 5257 5214 5143 5007 4970 4850 4796 4609 4524 4439 4404 3994 3731 3712 3632 3565 3521 3520 3431 3354 3331 3321 3289 3179 3088 3073 3024 3019 3003 2963 2949 2913 2659 2650 2579 2414 2327 2307 2249 2221 2131 1983 1779 1631 1598 1511 1506 1481 1387 1301 1237 1140 1118 1095 1042 686 631 598 508 394 364
Sort Sorted Array3
281 312 364 394 508 598 631 686 1042 1095 1118 1140 1237 1301 1387 1481 1506 1511 1598 1631 1779 1983 2131 2221 2249 2307 2327 2414 2579 2650 2659 2913 2949 2963 3003 3019 3024 3073 3088 3179 3289 3321 3331 3354 3431 3520 3521 3565 3632 3712 3731 3994 4404 4439 4524 4609 4796 4850 4970 5007 5143 5214 5257 5502 5507 5547 5718 5800 5832 5961 5992 6055 6206 6489 6522 6561 6580 6743 7138 7146 7296 7598 7742 7986 8017 8064 8112 8204 8306 8441 8668 8702 8704 8780 8821 8886 8979 9027 9144 9424 9433 9542 9715 9921 9969
Array2 Time: 0
Array2 Number of swapping required: 549
Reverse Array1
1994421309 4312256 9969 9921 9715 9542 9433 9424 9144 9027 8979 8886 8821 8780 8704 8702 8668 8441 8306 8204 8112 8064 8017 7986 7742 7598 7296 7146 7138 6743 6580 6561 6522 6489 6206 6055 5992 5961 5832 5800 5718 5547 5507 5502 5257 5214 5143 5007 4970 4850 4796 4609 4524 4439 4404 3994 3846 3731 3712 3632 3565 3521 3520 3431 3354 3331 3321 3289 3179 3088 3073 3024 3019 3003 2963 2949 2913 2659 2650 2579 2414 2327 2307 2249 2221 1983 1779 1631 1598 1511 1506 1481 1387 1301 1237 1140 1118 1095 899 686 631 598 508 394 364 312 281
Sort Sorted Array3
281 312 364 394 508 598 631 686 899 1095 1118 1140 1237 1301 1387 1481 1506 1511 1598 1631 1779 1983 2221 2249 2307 2327 2414 2579 2650 2659 2913 2949 2963 3003 3019 3024 3073 3088 3179 3289 3321 3331 3354 3431 3520 3521 3565 3632 3712 3731 3846 3994 4404 4439 4524 4609 4796 4850 4970 5007 5143 5214 5257 5502 5507 5547 5718 5800 5832 5961 5992 6055 6206 6489 6522 6561 6580 6743 7138 7146 7296 7598 7742 7986 8017 8064 8112 8204 8306 8441 8668 8702 8704 8780 8821 8886 8979 9027 9144 9424 9433 9542 9715 9921 9969 4312256 1994421309
Array3 Time: 0
Array3 Number of swapping required: 556
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.