Sắp xếp mảng theo thứ tự tăng dần trong C/C++

0
376
sap xep mang theo thu tu tang dan trong C 1

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 &amp;n){
	do{
		printf("Nhap n: ");
		scanf("%d",&amp;n);
	}
	while(n<2||n>99);
	
	for(int i=0; i<n; i++){
		printf("a[%d]: ",i);
		scanf("%d",&amp;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 &amp;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:

sap xep mang theo thu tu tang dan trong C 2

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

LEAVE A REPLY

Please enter your comment!
Please enter your name here