Cho mảng nguyên arr[]. Nhiệm vụ: sắp xếp mảng sao cho phần tử ở vị trí chẵn (chỉ số chẵn) lớn hơn phần tử ở vị trí lẻ (chỉ số lẻ).
Các trường hợp đầu vào/đầu ra
Đầu vào - int arr[] = {2, 1, 4, 3, 6, 5, 8, 7}
Đầu ra - Mảng trước: 2 1 4 3 6 5 8 7. Sắp xếp vị trí chẵn > lẻ: 1 2 3 4 5 6 7 8
Giải thích - Mảng size 8. Sắp xếp tăng dần rồi đặt: vị trí lẻ (0,2,4,6) lấy từ đầu, vị trí chẵn (1,3,5,7) lấy từ cuối → 1 2 3 4 5 6 7 8.
Đầu vào - int arr[] = {-3, 2, -4, -1}
Đầu ra - Mảng trước: -3 2 -4 -1. Sắp xếp vị trí chẵn > lẻ: -4 -3 -1 2
Giải thích - Mảng size 4. Sắp xếp: -4 -3 -1 2. Vị trí chẵn (1,3) giá trị -3,2 lớn hơn vị trí lẻ (0,2) giá trị -4,-1.
Phương pháp sử dụng trong chương trình dưới đây
Nhập mảng, tính size. Sắp xếp mảng bằng sort STL.
Gọi Rearrangement(arr, size).
Trong Rearrangement:
Tạo mảng ptr[size].
first=0, last=size-1.
For i=0..size-1: nếu (i+1)%2==0 (vị trí chẵn 1-based) → ptr[i] = arr[last--]; else ptr[i] = arr[first++].
In kết quả.
Ví dụ mã
#include <bits/stdc++.h> using namespace std; void Rearrangement(int* arr, int size){ int ptr[size]; int first = 0; int last = size - 1; for (int i = 0; i < size; i++){ if((i + 1) % 2 == 0){ ptr[i] = arr[last--]; } else{ ptr[i] = arr[first++]; } } } int main(){ int arr[] = {2, 1, 4, 3, 6, 5, 8, 7}; int size = sizeof(arr) / sizeof(arr[0]); cout<<"Mảng trước: "; for (int i = 0; i < size; i++){ cout << arr[i] << " "; } sort(arr, arr + size); Rearrangement(arr, size); cout<<"\nSắp xếp vị trí chẵn lớn hơn lẻ: "; for(int i = 0; i < size; i++){ cout<< arr[i] << " "; } return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Mảng trước: 2 1 4 3 6 5 8 7 Sắp xếp vị trí chẵn lớn hơn lẻ: 1 2 3 4 5 6 7 8