Viết chương trình nhập vào một mảng các số nguyên ngẫu nhiên (số lượng phần tử tùy ý). Sắp xếp mảng sao cho các số lẻ nằm tăng dần ở bên trái mảng, các số chẵn nằm tăng dần ở bên phải mảng. Không được sử dụng mảng trung gian.
Giải thuật của chúng ta ở đây là sẽ đưa hết các số lẻ về bên trái, các số chẵn về bên phải, ghi nhớ vị trí của biên các phần chẵn lẻ bằng 2 biến index là l (left) và r (right). Trong đó l đi từ trái qua và r đi từ phải qua. Cuối cùng, chỉ cần sắp xếp 2 phần lẻ và chẵn bằng một giải thuật tìm kiếm bất kỳ là xong. Ở đây tôi dùng Bubble Sort.
Đây là phần code chính của chúng ta:
...
int l = 0; // index ben trai
int r = n - 1; // index ben phai
cout << "\n\nPhan tach so chan va so le:";
// tach phan tu le va chan
while (l < r) {
// tim so le dau tien tu ben phai
while (laSoChan(a[r])) {
r--; // r = r - 1, r giam di 1 don vi
}
// tim so chan dau tien tu ben trai
while (!laSoChan(a[l])) {
l++; // l = l + 1
}
// in ra cac index
cout << "\nl=" << l << ",r=" << r << endl;
// hoan doi gia tri cua so chan va so le
hoandoi(a[l], a[r]);
// in ra cac phan tu trong mang
inMang(a);
}
hoandoi(a[l], a[r]);
cout << "\nl=" << l << ",r=" << r << endl;
inMang(a);
cout << "\n\nSap xep phan so le: \n";
for (int i = 0; i < l; i++) {
for (int j = i + 1; j < l; j++) {
if (a[j] < a[i]) {
hoandoi(a[i], a[j]);
}
}
}
inMang(a);
cout << "\n\nSap xep phan so chan: \n";
for (int i = r + 1; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[j] < a[i]) {
hoandoi(a[i], a[j]);
}
}
}
inMang(a);
...
Demo và mã nguồn của chương trình vui lòng tải về theo link bên dưới. Như các bạn thấy, trong hình tôi in ra mảng trước khi sắp xếp với số lẻ màu đỏ và số chẵn màu xanh, in ra mảng sau từng bước hoán đổi kèm 2 chỉ số l và r. Ở các bước gần cuối, các bạn có thể thấy các số lẻ được dồn về bên trái và số chẵn về bên phải. Cuối cùng, công việc của chúng ta trở nên rất nhẹ nhàng để sort phần số lẻ và phần số chẵn.
Loading...