Cho mảng nguyên dương arr[]. Nhiệm vụ: sắp xếp mảng sao cho phần tử ở chỉ số lẻ (1,3,5...) lớn hơn phần tử ở chỉ số chẵn ngay trước nó (0,2,4...).
Các trường hợp đầu vào/đầu ra
Đầu vào - int arr[] = {2, 1, 5, 4, 3, 7, 8}
Đầu ra - Mảng trước: 2 1 5 4 3 7 8. Sắp xếp chỉ số lẻ > trước: 1 4 2 5 3 8 7
Giải thích - Mảng size 7. Hoán đổi cặp (0,1), (2,3), (4,5) nếu vi phạm, sau đó kiểm tra cặp (6,5) nếu size lẻ: 1 4 2 5 3 8 7.
Đầu vào - int arr[] = {3, 2, 6, 9}
Đầu ra - Mảng trước: 3 2 6 9. Sắp xếp chỉ số lẻ > trước: 2 3 6 9
Giải thích - Mảng size 4. Hoán đổi (0,1) vì 3>2 → 2 3 6 9. Không cần thêm hoán đổi.
Phương pháp sử dụng trong chương trình dưới đây
Nhập mảng, tính size. In mảng trước.
Gọi Rearrangement(arr, size).
Trong Rearrangement:
ptr = size-1.
For i=0; i
Nếu size lẻ (size&1): for i=ptr; i>0; i-=2: nếu arr[i] > arr[i-1] → swap(arr[i], arr[i-1]).
In mảng sau sắp xếp.
Ví dụ mã
#include <iostream> using namespace std; void Rearrangement(int arr[], int size){ int ptr = size - 1; for(int i = 0; i < ptr; i = i+2){ if(arr[i] > arr[i+1]){ swap(arr[i], arr[i+1]); } } if(size & 1){ for(int i = ptr; i > 0; i = i-2){ if(arr[i] > arr[i-1]){ swap(arr[i], arr[i-1]); } } } } int main(){ int arr[] = {2, 1, 5, 4, 3, 7, 8}; int size = sizeof(arr) / sizeof(arr[0]); cout<<"Mảng trước: "; for (int i = 0; i < size; i++){ cout << arr[i] << " "; } Rearrangement(arr, size); cout<<"\nSắp xếp chỉ số lẻ lớn hơn trước: "; 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 5 4 3 7 8 Sắp xếp chỉ số lẻ lớn hơn trước: 1 4 2 5 3 8 7