Thứ Tư, 28 Tháng Chín 2022
Trang chủLập trìnhLập trình C/C++Sắp xếp mảng 1 chiều theo thứ tự tăng dần trong lập...

Sắp xếp mảng 1 chiều theo thứ tự tăng dần trong lập trình C/C++

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ự tăng dần.

Đọc thêm: Sắp xếp mảng 1 chiều theo thứ tự giảm dần trong lập trình C/C++

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 tăng 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ị bé 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ử bé 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ử.

Bạn xem minh họa dưới đây để dễ hình dung hơn.

Minhh họa thuật toán sắp xếp đổi chỗ trực tiếp(Nguồn codelearn.io)
Minh họ thuật toán sắp xếp đổi chỗ trực tiếp(nguồn wikipedia.org)

Chương trình sắp xếp mảng 1 chiều tăng dần với C

Chương trình sắp xếp mảng 1 chiều theo chiều tăng 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]) lớn 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

Sắp xếp mảng 1 chiều theo chiều tăng dần

Chương trình sắp xếp mảng 1 chiều tăng 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 tăng 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]) lớn 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
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x