Sắp xếp dãy số hay trong lập trình chính là sắp xếp mảng 1 chiều theo chiều tăng dần hoặc giảm dần. Đây là 1 bài toán sắp xếp đơn giản và rất cơ bản đối với bất cứ ai khi học lập trình. Bài toán sắp xếp dãy số là bài tập điển hình trong phần kiến thức về mảng 1 chiều và là một trong những bài toán nền tảng để nắm rõ hơn về kiến thức cơ bản nhất trong lập trình.
Trong bài viết này, blog Tui có cách sẽ cùng các bạn giải quyết bài toán sắp xếp mảng 1 chiều theo thứ tự giảm dần.
Đọc thêm: Sắp xếp mảng 1 chiều theo thứ tự tăng dần trong lập trình C/C++
Tóm Tắt
Sắp xếp mảng 1 chiều theo thứ tự tăng dần
Vì trong phạm vi bài viết này sẽ hướng tới những bạn mới bắt đầu làm quen tới lập trình, vì vậy thuật toán sắp xếp hôm nay mình sử dụng sẽ là thuật toán Sắp xếp đổi chỗ trực tiếp(Interchange Sort). Đây là một thuật toán sắp xếp đơn giản nhất và dễ hiểu nhất.
Ý tưởng để sắp xếp mảng 1 chiều theo chiều giảm dần: Ban đầu lấy ra phần tử đầu tiên(A0), so sánh phần tử đó lần lượt với các phần tử còn lại(duyệt các phần tử từ đầu mảng tới cuối mảng), gặp phần tử nào có giá trị lớn hơn giá trị ban đầu(A0), khi đó ta hoán đổi vị trí của A0 với phần tử có giá trị bé hơn đó, thực hiện cho tới cuối mảng thì lúc này phần tử đầu tiên chính là phần tử lớn nhất trong mảng. Tiếp tục chuyển qua phần tử thứ 2 rồi thực hiện lặp lại, thực hiện lặp lại tất cả các phần tử.
Chương trình sắp xếp mảng 1 chiều giảm dần với C
Chương trình sắp xếp mảng 1 chiều theo chiều giảm dần với code thuần C ta sẽ viết như bên dưới:
#include <stdio.h>
//Hàm nhập mảng
void input(int a[], int *n){ //*n là truyền vào tham trỏ(Tham chiếu trong c++) với mục đích n sau khi thoát khỏi hàm vẫn giữ được giá trị khi bị thay đổi trong hàm
printf("Nhap n: ");
scanf("%d", n); //Vì n là 1 con trỏ nên ta không cần &n
printf("\n---NHAP MANG----\n");
int i;
for(i = 0; i< *n;i++){
printf("a[%d] = ", i);
scanf("%d", &a[i]);
}
}
//Hàm sắp xếp mảng
void InterchangeSort(int a[], int n){
int i, j;
for (i = 0; i < n - 1; i++)
{
//j sẽ được duyệt từ vị trí của phân tử chưa sắp xếp tới cuối mảng
for (j = i + 1; j < n; j++)
{
//Nếu phần tử đang kiểm tra(a[i]) bé hơn phần tử khi ta duyệt mảng để kiểm tra(a[j])
if(a[i] < a[j])
{
//Ta đảo vị trí của 2 phần tử
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
//Hàm in ra mảng
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[1000]; //Khai mảng gồm tối đa 1000 phần tử
int n; //Khai bao n
input(arr, &n);
InterchangeSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Kết quả khi chạy chương trình
Chương trình sắp xếp mảng 1 chiều giảm dần với C++
Chương trình với code C++ ta chỉ sửa đổi lại một chút phần nhập xuất.
#include <iostream>
using namespace std;
//Hàm nhập mảng
void input(int a[], int &n){
cout<<"Nhap n: ";
cin>>n;
cout<<"\n-----NHAP MANG---\n";
for(int i= 0; i<n;i++){
cout<<"a["<<i<<"] = ";
cin>>a[i];
}
}
//Hàm sắp xếp mảng 1 chiều giảm dần
void InterchangeSort(int a[], int n){
for (int i = 0; i < n - 1; i++)
{
//j sẽ được duyệt từ vị trí của phân tử chưa sắp xếp tới cuối mảng
for (int j = i + 1; j < n; j++)
{
//Nếu phần tử đang kiểm tra(a[i]) bé hơn phần tử khi ta duyệt mảng để kiểm tra(a[j])
if(a[i] < a[j])
{
//Hoán đổi vị trí 2 phần tử
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
//Hàm xuất mảng
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
cout<< arr[i] <<" ";
cout<<"\n";
}
int main()
{
int arr[1000];//Khai báo mảng gồm tối da 1000 phần tử
int n;//Khai bao n
input(arr, n);
InterchangeSort(arr, n);
cout<<"Sorted array: ";
printArray(arr, n);
return 0;
}
[XEM TẤT CẢ BÀI VIẾT CHỦ ĐỀ VỀ C/C++ TẠI ĐÂY]
0
0
Phiếu bình chọn
