Bài tập số 12 luyện tập về sắp xếp mảng theo thứ tự giảm dần trong lập trình C/C++. Bài toán sắp xếp luôn là bài toán hay cho người mới học lập trình.
1. Giới thiệu bài toán
Tiếp tục với thuật toán sáp xếp, ở bài tập trước chúng ta đã giải quyết bài toán sắp xếp theo thứ tự tăng dần, ở bài này chúng ta sẽ sắp xếp nhưng sẽ theo thứ tự ngược lại.
Đề bài:
Viết hàm sắp xếp mảng a có n phần tử theo thứ tự giảm dần.
Đề bài ngắn gọn nhưng hay và đầy đủ ý. Bài toán sẽ giúp bạn nẵm vững hơn thuật toán sắp xếp quan trọng. Nếu có thể, hãy tự giải nó mà không cần tham khảo nhé!
2.Giải quyết bài toán
Bài toán yêu cầu người làm cần nắm tốt kiến thức về vòng lặp (for), hiểu tốt một chút về cách thức hoạt động của ngôn ngữ lập trình là có thể giải được. Đây là bài toán ở mức trung bình.
Bài toán mang lại hiệu quả tư duy cực kì tốt.
2.2 Ý tưởng giải quyết bài toán
Ý tưởng giải bài toán này gần giống với bài toán sắp xếp theo thứ tự tăng dần và có khác đôi chút về điều kiện.
Mình sẽ vẫn nhắc lại ý tưởng giải quyết:
- Sử dụng hai vòng for lồng nhau, một vòng i chạy từ 0 đến <n
- Vòng for thứ 2 j chạy từ 0 đến <=i
- So sánh a[j] với a[i]. Nếu a[j] nhỏ hơn a[i] tiến hành đổi chỗ.
Cuối cùng sẽ được mảng sắp xếp theo thứ tự giảm dần.
Thuật toán đổi chỗ:
- Có hai cách đổi chỗ, cách thứ nhất dùng biến trung gian, cách này đơn giản hơn. (cách này ứng dụng vào sắp xếp nhiều thứ khác nhau)
- Cách thứ 2 không dùng biến trung gian (cách này tối ưu hơn cách trên tuy nhiên chỉ áp dụng được với các con số)
2.2 Hàm sắp xếp các phần tử trong mảng theo thứ tự giảm dần trong C/C++
Hàm thứ nhất sử dụng biến trung gian:
//Ham sap xep thu nhat su dung bien trung gian
void SortUp(int a[], int n){
int Mid;
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++){
if(a[j]<a[i]){
Mid=a[i];
a[i]=a[j];
a[j]=Mid;
}
}
cout<<"\nMang sau khi sap xep:"<<endl;
xuat(a,n);
}
Hàm thứ 2 không sử dụng biến trung gian:
//Ham sap xep thu 2 khong dung bien trung gian
void SortUp2(int a[], int n){
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++){
if(a[j]<a[i]){
a[i]=a[i]+a[j];
a[j]=a[i]-a[j];
a[i]=a[i]-a[j];
}
}
cout<<"\nMang sau khi sap xep giam:"<<endl;
xuat(a,n);
}
Các bạn có thể xem lại Bài 11: Sắp xếp mảng theo thứ tự tăng dần, mình có nói chi tiết hơn phần đổi chỗ.
2.3 Chương trình sắp xếp mảng theo thứ tự giảm dần bằng ngôn ngữ C/C++
Chúng ta cần thêm vào các cấu trúc mặc định của một chương trình C/C++ đồng thời thêm vào hàm nhập xuất mảng để làm việc với mảng.
Code C:
#include<stdio.h>
void nhap(int a[], int &n){
do{
printf("Nhap n: ");
scanf("%d",&n);
}
while(n<2||n>99);
for(int i=0; i<n; i++){
printf("a[%d]: ",i);
scanf("%d",&a[i]);
}
}
void xuat(int a[], int n){
for(int i=0;i<n;i++){
printf("%5d",a[i]);
}
}
//Ham sap xep thu nhat su dung bien trung gian
void SortUp(int a[], int n){
int Mid;
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++){
if(a[j]<a[i]){
Mid=a[i];
a[i]=a[j];
a[j]=Mid;
}
}
printf("\nMang sau khi sap xep:\n");
xuat(a,n);
}
//Ham sap xep thu 2 khong dung bien trung gian
void SortUp2(int a[], int n){
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++){
if(a[j]<a[i]){
a[i]=a[i]+a[j];
a[j]=a[i]-a[j];
a[i]=a[i]-a[j];
}
}
printf("\nMang sau khi sap xep giam:\n");
xuat(a,n);
}
int main(){
int a[100];
int n;
nhap(a,n);
SortUp(a,n);
return 0;
}
Code C++:
#include<bits/stdc++.h>
using namespace std;
void nhap(int a[], int &n){
do{
cout<<("Nhap n: ");
cin>>n;
}
while(n<2||n>99);
for(int i=0; i<n; i++){
cout<<"a["<<i<<"]: ";
cin>>a[i];
}
}
void xuat(int a[], int n){
for(int i=0;i<n;i++){
cout<<" "<<a[i];
}
}
//Ham sap xep thu nhat su dung bien trung gian
void SortUp(int a[], int n){
int Mid;
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++){
if(a[j]<a[i]){
Mid=a[i];
a[i]=a[j];
a[j]=Mid;
}
}
cout<<"\nMang sau khi sap xep:"<<endl;
xuat(a,n);
}
//Ham sap xep thu 2 khong dung bien trung gian
void SortUp2(int a[], int n){
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++){
if(a[j]<a[i]){
a[i]=a[i]+a[j];
a[j]=a[i]-a[j];
a[i]=a[i]-a[j];
}
}
cout<<"\nMang sau khi sap xep giam:"<<endl;
xuat(a,n);
}
int main(){
int a[100];
int n;
nhap(a,n);
SortUp2(a,n);
return 0;
}
Kết quả khi bạn chạy chương trình:
Kết quả thỏa mãn yêu cầu của đề bài đưa ra.
Bài chia sẻ của mình đến đây là hết, cảm ơn bạn đã quan tâm bài viết!
Xem tiếp bài 13: In ra các số nguyên tố có trong mảng
Xem lại bài 11: Sắp xếp mảng theo thứ tự tăng dần
Tải về 67 bài tập đề cương lập trình C/C++
Mọi thắc mắc trong khi tham khảo bài viết, bạn đọc đừng ngại để lại comment xuống phía dưới nhé!
Rất mong nhận được góp ý của các bạn để bài chia sẻ của mình hoàn thiện hơn!
