Cho mảng nguyên arr[] chứa số dương và âm. Nhiệm vụ: sắp xếp mảng sao cho số dương và âm xen kẽ nhau, phần dư đẩy về cuối mảng.
Các trường hợp đầu vào/đầu ra
Đầu vào - int arr[] = {4, 2, -1, -1, 6, -3}
Đầu ra - Sắp xếp xen kẽ O(n) O(1): 2 -1 6 -1 4 -3
Giải thích - Mảng size 6. Số dương và âm xen kẽ: 2 -1 6 -1 4 -3.
Đầu vào - int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}
Đầu ra - Sắp xếp xen kẽ O(n) O(1): 2 -2 3 -5 5 -3 5 -1 1 3 1 1
Giải thích - Mảng size 12. Kết quả: 2 -2 3 -5 5 -3 5 -1 1 3 1 1.
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:
temp=-1, positive=temp+1, negative=0.
For i=0..size-1: nếu arr[i]<0 → temp++, swap(arr[temp], arr[i]) (đưa âm về đầu).
positive = temp+1 (vị trí đầu tiên của dương).
While positive
In kết quả.
Ví dụ mã
#include <bits/stdc++.h> using namespace std; void Rearrangement(int arr[], int size){ int temp = -1; for(int i = 0; i < size; i++){ if (arr[i] < 0){ temp++; swap(arr[temp], arr[i]); } } int positive = temp + 1; int negative = 0; while(positive < size && negative < positive && arr[negative] < 0){ swap(arr[negative], arr[positive]); positive++; negative = negative + 2; } } int main(){ int arr[] = {4, 2, -1, -1, 6, -3}; int size = sizeof(arr)/sizeof(arr[0]); Rearrangement(arr, size); cout<<"Sắp xếp xen kẽ O(n) O(1): "; 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ả:
Sắp xếp xen kẽ O(n) O(1): 2 -1 6 -1 4 -3