Сделай так, чтобы функция binaryTreeSort сортировала по убыванию:#include <iostream>…
- User
Сделай так, чтобы функция binaryTreeSort сортировала по убыванию:#include #include #include #include #include
using namespace std;
template< class T > void downHeap(vector& a, long k, long n) { T new_elem; long child; new_elem = a[k];
while (k <= n / 2) { child = 2 * k; if (child < n && a[child] < a[child + 1]) child++; if (new_elem >= a[child]) break; a[k] = a[child]; k = child; } a[k] = new_elem;}
template void displayVector(const vector& a) { for (const T& elem : a) { cout << elem << " "; } cout << endl; }
template struct TreeNode { T data; TreeNode* left; TreeNode* right;
TreeNode(T value) { data = value; left = nullptr; right = nullptr; }};
template void insert(TreeNode*& root, T value) { if (root == nullptr) { root = new TreeNode(value); return; }
if (value < root->data) { insert(root->left, value); } else { insert(root->right, value); }}
template void inOrderTraversal(TreeNode* root, vector& sortedArray) { if (root == nullptr) { return; }
inOrderTraversal(root->left, sortedArray); sortedArray.push_back(root->data); inOrderTraversal(root->right, sortedArray);}
template void binaryTreeSort(vector& a) { TreeNode* root = nullptr;
for (const T& value : a) { insert(root, value); } a.clear(); inOrderTraversal(root, a);}
void radixSort(vector& a, int n) { vector b(a); vector count(256), index(256); for (int shift = 0; shift < 32; shift += 8) { for (int i = 0; i < 256; i++) count[i] = 0; for (int i = 0; i < n; i++) count[(a[i] >> shift) & 255]++; for (int i = 1; i < 256; i++) count[i] += count[i - 1]; for (int i = n - 1; i >= 0; i--) b[--count[(a[i] >> shift) & 255]] = a[i]; a = b; } vector negativeNumbers; vector positiveNumbers; for (int i = 0; i < n; i++) { if (a[i] < 0) { negativeNumbers.push_back(-a[i]); } else { positiveNumbers.push_back(a[i]); } } reverse(positiveNumbers.begin(), positiveNumbers.end()); sort(negativeNumbers.begin(), negativeNumbers.end());
int negativeIndex = 0; int positiveIndex = 0; for (int i = 0; i < n; i++) { if (a[i] < 0) { a[i] = -negativeNumbers[negativeIndex]; negativeIndex++; } else { a[i] = positiveNumbers[positiveIndex]; positiveIndex++; } }} int main() { setlocale(LC_ALL, "Russian"); srand(time(NULL)); int n; cout << "Введите размер массива" << endl; cin >> n;
vector<int> A(n); vector<int> B(n); vector<int> C; for (int i = 0; i < n; i++) { A[i] = -10000 + rand() % 20001; B[i] = -10000 + rand() % 20001; } cout << "Массив А: " << endl; for (int i = 0; i < n; i++) { cout << " " << A[i]; } cout << endl; cout << "Массив B: " << endl; for (int i = 0; i < n; i++) { cout << " " << B[i]; } for (int i = 0; i < n; i++) { if (A[i] % 2 == 0) { C.push_back(A[i]); } if (B[i] % 2 != 0) { C.push_back(B[i]); } } cout << endl; cout << "Массив C: " << endl; for (int i = 0; i < C.size(); i++) { cout << " " << C[i]; } cout << endl << "Сортировка подразрядным методом - 1, Бинарное дерево - 2" << endl; int flag; cin >> flag; clock_t start_time = clock(); cout << "Отсортированный массив C: " << endl; if (flag == 1) { radixSort(C, C.size()); displayVector(C); } else if (flag == 2) { binaryTreeSort(C); displayVector(C); } clock_t end_time = clock(); double duration = (static_cast<double>(end_time - start_time)) / CLOCKS_PER_SEC; cout << " Time: " << duration << "sec" << endl; return 0;}
- Assistant
В функции binaryTreeSort, необходимо изменить порядок сортировки элементов так, чтобы они добавлялись в массив sortedArray в обратном порядке. Вместо:
sortedArray.push_back(root->data);
используйте:
sortedArray.insert(sortedArray.begin(), root->data);
Это добавит элементы в начало массива sortedArray, обратно отсортированные по убыванию.
- User
Боже, спасибо тебе огромное
- Assistant
Пожалуйста! Рад был помочь. Если у вас возникнут еще вопросы, не стесняйтесь задавать. Удачи вам!