CTDL và giải thuật - Bài toán hay về sắp xếp
Hải có một dãy số gồm n
số nguyên, Hải muốn sắp xếp các phần tử của dãy đó với các yêu cầu sau:
- Từ trái qua phải:
- Các số nguyên dương xuất hiện theo giá trị tăng dần.
- Các số nguyên âm xuất hiện theo giá trị giảm dần.
- Không thay đổi vị trí của phần tử mang giá trị
0
. - Không thay đổi tính chất ở mỗi vị trí (Nghĩa là nếu trước khi sắp xếp vị trí
i
có giá trị nguyên âm thì sau khi sắp xếp vị trịi
cũng phải mang giá trị âm, nếu ví trịi
mang giá trị dương cũng tương tự).
Cho trước dãy a
. Hãy sắp xếp theo cách của Hải. In kết quả ra màn hình, sau mỗi phần tử có đúng một khoảng trắng.
Ví dụ:
- Test mẫu 1:
Input Output 6
3 -1 2 0 -4 62 -1 3 0 -4 6
Vớia = [3, -1, 2, 0, -4, 6]
thì kết quả mong muốn là"2 -1 3 0 -4 6 ".
Giải thích:- Các số nguyên dương xuất hiện theo thứ tự tăng dần
2, 3, 6.
- Các số nguyên dương xuất hiện theo thứ tự giảm dần
-1, -4.
- Các số nguyên dương xuất hiện theo thứ tự tăng dần
- Test mẫu 2:
Input Output 4
0 7 0 50 5 0 7
Vớia = [0, 7, 0, 5]
, thì kết quả mong muốn là"0 5 0 7 ".
Hướng dẫn bài tập.
Với bài này đừng suy nghĩ quá phức tạp, hãy dùng một dãy b
dùng để lưu những phần từ khác 0
ở trang dãy a
. Sắp xếp dãy b sau đó đưa ngược lại vào trong dãy a
như sau:
k = 0;
for (int i = n-1; i >= 0; i--){
if (a[i] < 0){
a[i] = b[k];
k = k + 1;
}
}
for (int i = 0; i < n; i++){
if (a[i] > 0){
a[i] = b[k];
k = k + 1;
}
}
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
using namespace std;
void quickSort(int a[], int l, int r){
int p = a[(l+r)/2];
int i = l, j = r;
while (i < j){
while (a[i] < p){
i++;
}
while (a[j] > p){
j--;
}
if (i <= j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
if (i < r){
quickSort(a, i, r);
}
if (l < j){
quickSort(a, l, j);
}
}
void printArray(int a[], int n){
for (int i = 0; i < n; i++){
cout << a[i] << " ";
}
}
int a[100001], b[100001];
int main(){
int n;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
int k = 0;
for (int i = 0; i < n; i++){
if (a[i] != 0){
b[k] = a[i];
k = k + 1;
}
}
quickSort(b, 0, k-1);
k = 0;
for (int i = n-1; i >= 0; i--){
if (a[i] < 0){
a[i] = b[k];
k = k + 1;
}
}
for (int i = 0; i < n; i++){
if (a[i] > 0){
a[i] = b[k];
k = k + 1;
}
}
printArray(a, n);
}