Question

(C++)Heapsort: Write C++ codes for heapsort. The input array is a random permutation of A={1,

2, 3, …, 99, 100}. You should write codes to generate and print the random permutation first.

Answer 1

// c++ program for heapsort
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

  

void countSort(vector<int>& arr)
{

int max = *max_element(arr.begin(), arr.end());

int min = *min_element(arr.begin(), arr.end());

int range = max - min + 1;

  

vector<int> count(range), output(arr.size());

for (int i = 0; i < arr.size(); i++)

count[arr[i] - min]++;

  

for (int i = 1; i < count.size(); i++)

count[i] += count[i - 1];

  

for (int i = arr.size() - 1; i >= 0; i--) {

output[count[arr[i] - min] - 1] = arr[i];

count[arr[i] - min]--;

}

  

for (int i = 0; i < arr.size(); i++)

arr[i] = output[i];
}

  

void printArray(vector<int>& arr)
{

for (int i = 0; i < arr.size(); i++)

cout << arr[i] << " ";

cout << "\n";
}

  

int main()
{

vector<int> arr = { 1, 2, 3, ..........., 99,100,};

countSort(arr);

printArray(arr);

return 0;
}