Cho mảng nguyên arr[] chứa số dương và âm. Nhiệm vụ: sắp xếp mảng bằng hàm sort của C++ STL và 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 sort(): -3 -1 -1 0 2 4 6.
Giải thích - Mảng size 7. Sắp xếp: âm trước, dương sau → -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 sort(): -10 -9 2 3 4 5 8 10.
Giải thích - Mảng size 8. Kết quả: -10 -9 2 3 4 5 8 10.
Phương pháp sử dụng
1. Dùng sort()
Nhập mảng, tính size.
Gọi Rearrangement(arr, size) bên trong gọi sort(arr, arr+size).
In kết quả.
2. Dùng đệ quy
Nhập mảng, tính size. Biến temp đếm số âm.
Gọi Rearrangement(arr, 0, size-1) rồi Rotate(arr, temp, size-1).
Hàm Rearrangement(arr, first, last): nếu first==last return; đệ quy Rearrangement(arr, first+1, last); nếu arr[first]>=0 → Rotate(arr, first+1, last) và Rotate(arr, first, last).
Hàm Rotate(arr, first, last): while first
In kết quả.
Ví dụ 1: sort()
#include <bits/stdc++.h> using namespace std; void Rearrangement(int arr[], int size){ sort(arr, arr + size); } 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 sort(): "; for(int i = 0; i < size; i++){ cout<< arr[i] << " "; } return 0; }
Đầu ra
Sắp xếp dùng sort(): -3 -1 -1 0 2 4 6
Ví dụ 2: Đệ quy
#include <bits/stdc++.h> using namespace std; void Rotate(int arr[], int first, int last){ while(first < last){ int temp = arr[first]; arr[first] = arr[last]; arr[last] = temp; first++; last--; } } void Rearrangement(int arr[], int first, int last){ if(first == last){ return; } Rearrangement(arr, (first + 1), last); if(arr[first] >= 0){ Rotate(arr, (first + 1), last); Rotate(arr, first, last); } } int main(){ int arr[] = {4, 2, -1, -1, 6, -3, 0}; int size = sizeof(arr)/sizeof(arr[0]); int temp = 0; for(int i = 0; i < size; i++){ if(arr[i] < 0){ temp++; } } Rearrangement(arr, 0, (size - 1)); Rotate(arr, temp, (size - 1)); cout<<"Sắp xếp dùng đệ quy: "; for(int i = 0; i < size; i++){ cout<< arr[i] << " "; } return 0; }
Đầu ra
Sắp xếp dùng đệ quy: -1 -1 -3 4 2 6 0