Nội dung chính
- 1. Giới thiệu bài toán
- 2.Giải quyết bài toán
- 2.2 Ý tưởng giải quyết bài toán
- 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++
- 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++
- 1.Giới thiệu bài toán sắp xếp
- 2. Giải quyết bài toán
- 2.1 Ý tưởng giải quyết bài toán
- 2.2 Hàm sắp xếp theo thứ tự tăng dần
- 2.3 Chương trình sắp xếp mảng theo thứ tự tăng dần
- Video liên quan
Run demo:
bấm vào đây
Hàm sắp xếp mảng tăng giảm dần trong lập trình C
C 2016
#include <stdio.h>
int a[100];
//Khai báo mảng array kích thước 100
int main()
//Hàm thân chạy chương trình bắt buộc có
{ int i,j,n,k;
//Khai báo biến kiểu int
printf(“Nhap so mang cua phan tu: “);
//Hiển thị màn hình
scanf(“%d”, &n);
//Nhập vào số lần lặp
for (i = 0; i < n; i++)
//vòng lặp for
{ printf(“nhap phan tu thu %d: “, i + 1); scanf(“%d”, &a[i]);
//Nhập vào mảng số i
} for (i = 0; i < n-1;i++){ for (j = i+1; j < n;j++){ if (
a[i]>a[j]
)
//Tăng dần or Giảm dần
a[i]<a[j]
{
k = a[i]; //k là biến tạm lưu giá trị a[i] = a[j]; //thực hiện đổi chỗ
lấy a[j]
a[j] = k; //thực hiện đổi chỗ
lấy a[i]
} } } printf(“mang sau khi da sap xep la:\n”); for (i = 0; i < n; i++) { printf(” %d “, a[i]);
//Mỗi lần lặp in ra mảng i
}
}
Kiến Thức Cần Có:
1. Khai báo kiểu int ?
2. Khai báo kiểu Array mảng ? Mảng 1 chiều và mảng 2 chiều là gì?
3. printf là gì?
4. scanf là gì ?
5. Vòng lặp for là gì ?
Xem thêm: Hàm đổi chỗ dùng con trỏ trong lập trình C
bấm vào đây
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.
Tóm Tắt
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!
Bài toán sắp xếp mảng theo thứ tự tăng dần là bài toán rất hay dành cho các bạn mới học lập trình C/C++ hay bất kì ngôn ngữ lập trình nào khác.
1.Giới thiệu bài toán sắp xếp
Thuật toán sắp xếp là thuật toán được sử dụng rất nhiều trong lập trình. Chính vì vậy, đây là một bài toán cơ bản và quan trọng trong việc học lập trình C/C++.
Đề bài bài tập luyện lập trình số 11:
Viết hàm sắp xếp mảng a có n phần tử theo thứ tự tăng dần.
Đề bài ngắn nhưng mà hay nhé các bạn.
Đề bài này theo mình đánh giá nó ở mức trung bình và cực kì quan trọng cho nền tảng học lập trình.
2. Giải quyết bài toán
Thuật toán đề giải bài toán sắp xếp mảng tăng dần trong C/C++ khá đơn giản tuy nhiên bạn phải nắm chắc kiến thức về vòng lặp for và các phép gán của ngôn ngữ C/C++.
2.1 Ý tưởng giải quyết bài toán
Thuật toán sắp xếp đã được rất nhiều tác giả chia sẻ, mình chia sẻ lại với văn phong của mình nhé!
Hàm sắp xếp sẽ sử dụng hai vòng lặp for lồng nhau để kiểm tra.
- Vòng for thứ nhất i chạy tử 0 đến n (duyệt toàn bộ mảng)
- Vòng for thứ 2 j chạy từ 0 tới i (mục đích là so sánh i lần lượt với các phần tử trước nó)
- Tại mỗi a[j], so sánh nó với a[i] nếu a[j]>a[i] tiến hành đổi chỗ.
khi vòng for chạy hết ta có được mảng a theo thứ tự tăng dần.
Vấn đề quan trọng thứ 2 ở đây là thuật toán đổi chỗ, đổi vị trí giữa a[j] và a[i]
Có 2 cách để đổi vị trí:
- Dùng biến trung gian (Mid)
- Không dùng biến trung gian (đương nhiên cách này tối ưu hơn nhưng hơi khó hiểu tí)
2.2 Hàm sắp xếp theo thứ tự tăng dần
2.2.1 Dùng biến trung gian
Code C/C++
//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);
}
2.2.2 Không dùng biến trung gian
Code C/C++:
//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 tang:”<<endl;
xuat(a,n);
}
Mình sẽ giải thích thêm phần không dùng biến trung gian này nhé:
Gọi a[i] là x và a[j] là y.
Dòng đầu tiên x=x+y khi đó x được gán bằng tổng của cả x và y.
y vẫn là y.
Dòng thứ 2: y= x-y khi đó giá trị của y sẽ là giá trị của x ban đầu. (lấy tổng trừ đi y còn x)
Dòng thứ 3: x=x-y lúc này, y có giá trị của x ban đầu nên x sẽ là giá trị của y ban đầu (lấy tổng trừ đi x còn y)
Phần này bạn cần để ý xíu mới hiểu nhé
2.3 Chương trình sắp xếp mảng theo thứ tự tăng dần
Để có chương trình hoàn chỉnh, bạn cần lắp hàm sắp xếp bên trên vào cấu trúc của một chương trình C/C++. Thêm hàm nhập xuất 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 tang:\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 tang:”<<endl;
xuat(a,n);
}
int main(){
int a[100];
int n;
nhap(a,n);
SortUp2(a,n);
return 0;
}
Kết quả khi chạy chương trình trên:
Bài viết 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 12: Sắp xếp mảng theo thứ tự giảm dần
Xem lại bài 10: Tìm số nhỏ nhất trong mảng
Tải về 67 bài tập đề cương lập trình
