Cho mảng nguyên arr[] chứa số dương và âm. Nhiệm vụ: sắp xếp mảng sao cho các phần tử được sắp xếp bằng hàm sort của C++ STL cũng như kỹ thuật đệ quy.
Các trường hợp đầu vào/đầu ra
Đầu vào - int arr[] = {4, 2, -1, -1, 6, -3, 0}
Đầu ra - Sắp xếp dương âm với không gian O(1): -3 -1 -1 0 6 2 4.
Giải thích - Mảng size 7. Sắp xếp trong không gian O(1) cho kết quả -3 -1 -1 0 2 4 6.
Đầu vào - int arr[] = {-9, -10, 2, 3, 10, 5, 8, 4}
Đầu ra - Sắp xếp dương âm với không gian O(1): -9 -10 2 3 10 5 8 4
Giải thích - Mảng size 8. Kết quả: -9 -10 2 3 10 5 8 4.
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 khi sắp xếp.
Gọi Rearrangement(arr, size).
Trong Rearrangement:
i=0, j=size-1.
While true: while arr[i]<0 && i
0 && j>=0 → j--. Nếu i
Ngược lại break.
In kết quả.
Ví dụ mã
#include<iostream> using namespace std; void Rearrangement(int arr[], int size){ int i = 0; int j = size - 1; while(true){ while(arr[i] < 0 && i < size){ i++; } while(arr[j] > 0 && j >= 0){ j--; } if (i < j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } else{ break; } } } int main(){ int arr[] = {4, 2, -1, -1, 6, -3, 0}; int size = sizeof(arr)/sizeof(arr[0]); Rearrangement(arr, size); cout<<"Sắp xếp dương âm với không gian 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 dương âm với không gian O(1): -3 -1 -1 0 6 2 4