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ị cũng phải mang giá trị âm, nếu ví trị 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 6

    2 -1 3 0 -4 6

    Với a = [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.
       
  • Test mẫu 2:
     
    Input Output

    4
    0 7 0 5

    0 5 0 7

    Với a = [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);
}