Sắp xếp mảng: arr[i] >= arr[j] nếu i chẵn, arr[i] <= arr[j] nếu i lẻ (j < i) trong C++

Cho mảng số nguyên. Nhiệm vụ: sắp xếp lại mảng sao cho tại vị trí chẵn (i%2==0) giá trị lớn hơn hoặc bằng các giá trị trước đó, tại vị trí lẻ giá trị nhỏ hơn hoặc bằng các giá trị trước đó.

Các trường hợp đầu vào/đầu ra mẫu

Đầu vào: int arr[] = {5, 9, 10, 12, 32, 35, 67, 89}

Đầu ra: 12 32 10 35 9 67 5 89

Giải thích: Sắp xếp mảng tăng: {5,9,10,12,32,35,67,89}. Gán vị trí chẵn (0,2,4,6) lấy từ giữa về đầu: 12,10,9,5. Vị trí lẻ (1,3,5,7) lấy từ giữa+1 về cuối: 32,35,67,89.

Đầu vào: int arr[] = {4, 5, 1, 2, 9, 10}

Đầu ra: 4 5 2 9 1 10

Phương pháp tiếp cận

• Sắp xếp mảng tăng dần.
• Tách mảng thành 2 nửa: nửa đầu (phần tử nhỏ) cho vị trí lẻ, nửa sau (phần tử lớn) cho vị trí chẵn.
• Điền vị trí chẵn (0,2,4...) từ giữa mảng sort về đầu (giảm dần).
• Điền vị trí lẻ (1,3,5...) từ giữa+1 về cuối (tăng dần).

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

void array_rearrange(int arr[], int size) {
    int even = size / 2;
    int odd = size - even;
    int temp = odd - 1;
    int arr_2[size];
    for (int i = 0; i < size; i++) arr_2[i] = arr[i];
    sort(arr_2, arr_2 + size);
    for (int i = 0; i < size; i += 2) {
        arr[i] = arr_2[temp];
        temp--;
    }
    temp = odd;
    for (int i = 1; i < size; i += 2) {
        arr[i] = arr_2[temp];
        temp++;
    }
    cout << "Array after rearranging: ";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
}

int main() {
    int arr[] = {5, 9, 10, 12, 32, 35, 67, 89};
    int size = sizeof(arr) / sizeof(arr[0]);
    array_rearrange(arr, size);
    return 0;
}

Đầu ra chương trình

Array after rearranging elements are: 12 32 10 35 9 67 5 89