Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· OpenAIAi2 WildChat-4.8M (AI2)

Сделай так, чтобы функция binaryTreeSort сортировала по убыванию:#include <iostream>…

  1. 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;
    

    }

  2. Assistant

    В функции binaryTreeSort, необходимо изменить порядок сортировки элементов так, чтобы они добавлялись в массив sortedArray в обратном порядке. Вместо:

    sortedArray.push_back(root->data);

    используйте:

    sortedArray.insert(sortedArray.begin(), root->data);

    Это добавит элементы в начало массива sortedArray, обратно отсортированные по убыванию.

  3. User

    Боже, спасибо тебе огромное

  4. Assistant

    Пожалуйста! Рад был помочь. Если у вас возникнут еще вопросы, не стесняйтесь задавать. Удачи вам!