Sắp xếp mảng một chiều tăng dần, giảm dần trong C/C++

Cách sắp xếp dãy số nguyên, mảng một chiều theo thứ tự tăng dần, giảm dần trong C / C++. Cách sắp xếp dãy số thực char, mảng số nguyên n nhập vào từ bàn phím.

1. Giới thiệu bài toán sắp xếp

Bài toán sắp xếp là bài toán cơ bản và cực kì quan trọng, nó là một giải thuật cơ bản mà bất kì lập trình viên nào cũng cần phải biết, cùng tìm hiểu bài toán này nhé!

Dạng đề bài cho bài toán này chúng ta sẽ thường xuyên gặp phải. Các giải thuật để giái quyết bài toán có thể sử dụng ở cả hiện tại và sau này, chình vì vậy người ta mới nói đây là một bài toán quan trọng.

Khi nhắc đến sắp xếp dãy số, bạn liền phải nghĩ đó là cấu trúc mảng. Các dạng đề như sắp xếp dãy số nguyên, mảng số thực theo chiều tăng/ giảm đều là biến thể của bài toán này.

Đối với bài tập nhập môn thường sẽ là: Nhập một dãy số có N phần từ, N nhập vào từ bàn phím. Sắp xếp dãy số đó . . .

Xem thêm các bài viết về cấu trúc giữ liệu và thuật toán.

2. Cách sắp xếp dãy số

Chính vì bài toán sắp xếp là dạng bài kinh điển nên có rất nhiều thuật toán sắp xếp khác nhau như:

• Sắp xếp chọn – selection sort
• Sắp xếp nổi bọt – bubble sort
• Sắp xếp chèn – insert sort
• Sắp xếp nhanh – quick sort
• Sắp xếp vun đống – heap sort
• Sắp xếp trộn – merge sort
• . . . .

Thuật toán thường được nhiều người, thầy cô sử dụng nhất khi mới học đó chính là sắp xếp chọn.
Sắp xếp chọn lấy ý tưởng đó là: Sau mỗi lần lặp ta sẽ tìm được một phần tử đúng vị trí. Bạn có thể xem hình minh họa dưới:

Trong bài viết này mình sẽ sử dụng luôn thuật toán này.

2.1 Hàm sắp xếp dãy số tăng dần C/C++

Nếu bạn đang tìm cách sắp xếp các kí tự kiểu char, bạn cũng có thể sử dụng các này nhé!

Ở đây mình sẽ viết thành hàm cho dễ sử dụng nhé. hàm swap do mình viết ra có tác dụng đổi chỗ hai phần tử cho nhau.

// Ham doi vi tri hai phan tu
void swap(int &a, int &b){
	int temp =a;
	a=b;
	b=temp;
}

// Ham sap xep tang
void sortArrTang(int a[], int n){
	for(int i=0;i<n-1;i++)
		for(int j=i+1;j<n;j++){
			if(a[i]>a[j]){
				swap(a[i], a[j]);
			}
		}
}

Giải thích: Nếu cần sắp xếp mảng có n phần tử. Ta chỉ cần thực hiện n-1 lần chọn, bởi vì phần tử cuối cùng đã tự đúng vị trí nên trong vòng lặp for đầu tiên i<n-1.

Trong vòng lặp thứ 2: Ta sẽ chạy từ vị trí j = i+1 đến cuối mảng, tức là từ sau i đến hết mảng. Nếu có phần từ nào nhỏ hơn a[i] thì ta đổi chỗ. Như vậy sau vòng lặp đầu tiên ta sẽ tìm được phần từ nhỏ nhất của mảng. Cứ như vậy

2.2 Hàm sắp xếp giảm

Sắp xếp giảm cơ bản giống với phần trên. Chỉ cần thay đổi điều kiện là nếu a[i]<a[j] thì đổi chỗ. Sau vòng lặp đầu tiên, vị trí a[0] sẽ là phần tử lớn nhất.

// Ham sap xep giam
void sortArrGiam(int a[], int n){
	for(int i=0;i<n-1;i++)
		for(int j=i;j<n;j++){
			if(a[i]<a[j]){
                         // doi cho hai phan tu khong dung ham swap()
			        int temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
		}
}

3. Sắp xếp dãy số nguyên có N phần tử

Phần này mình sẽ viết full code về sắp xếp một dãy số nguyên có n phần tử theo chiều tăng dần, giảm dần, n nhập vào từ bàn phím. Mời bạn tham khảo:

/* Code by duongdinh24.com
   Github: https://github.com/duongdinh24/
*/
#include<iostream>
using namespace std;

// Ham doi vi tri hai phan tu
void swap(int &a, int &b){
	int temp =a;
	a=b;
	b=temp;
}

// Ham sap xep tang
void sortArrTang(int a[], int n){
	for(int i=0;i<n-1;i++)
		for(int j=i;j<n;j++){
			if(a[i]>a[j]){
				swap(a[i], a[j]);
			}
		}
}

// Ham sap xep giam
void sortArrGiam(int a[], int n){
	for(int i=0;i<n-1;i++)
		for(int j=i;j<n;j++){
			if(a[i]<a[j]){
				int temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
		}
}

// Ham nhap mang
void inputArr(int a[], int n){
	for(int i=0;i<n;i++)
		cin>>a[i];
}

// Ham xuat mang
void printArr(int a[], int n){
	for(int i=0;i<n;i++)
		cout<<" "<<a[i];
}

int main(){
	int n;
	// Nhap so luong phan tu mang
	do{
		cout<<"Nhap n: ";
		cin>>n;
	}
	while(n<=0);  // Neu n<=0 thi nhap lai

	int a[n];  // khai bao mang a co n phan tu
	inputArr(a,n); // Goi ham nhap mang
	sortArrTang(a, n); // Goi ham sap xep
	cout<<"Mang sau khi sap xep tang dan: "<<endl;
	printArr(a, n);
	return 0;
}

Ví dụ sắp xếp theo thứ tự tăng dần:

Ví dụ hàm sắp xếp giảm:

Bài viết của mình đến đây là hết. Bạn đọc có ý kiến đóng góp hay thắc mắc gì nhớ để lại comment phía dưới nhé!

Like và chia sẻ chúng cho bạn bè nếu bạn thấy bài viết hữu ích!
Cảm ơn bạn ghé thăm blog duongdinh24.com
Chúc bạn thành công !