Yêu cầu của bài toán là sắp xếp mảng số nguyên tăng dần bằng thuật toán sắp xếp nổi bọt (Bubble Sort) trong C. Đối với bài tập này chúng ta sẽ sử dụng các kiến thức như sau: nhập và xuất dữ liệu cơ bàn trong ngôn ngữ lập trình C, cách sử dụng mảng trong ngôn ngữ lập trinh C, cách sử dụng vòng lặp for để duyệt các phần tử trong mảng, cách dùng thuật toán sắp xếp nổi bọt trong C. 2. Lời giảiĐể thực hiện bài toán này chúng ta cần có kiến thức cơ bản về ngôn ngữ lập trình C, nhập xuất dữ liệu cơ bàn trong ngôn ngữ lập trình C, cách sử dụng mảng trong ngôn ngữ lập trinh C, cách sử dụng vòng lặp for để duyệt các phần tử trong mảng và cách dùng thuật toán sắp xếp nổi bọt trong C. Ý tưởng của thuật toán nổi bọt (Bubble Sort) như sau:
Các bước thực hiện yêu cầu của bài tập sắp xếp mảng số nguyên tăng đần bằng thuật toán sắp xếp nổi bọt (Bubble Sort) trong ngôn ngữ lập trình C như sau: Bước 1: Ta khỏi tạo hàm Nhap(int a[],int n) dùng để nhập dữ liệu cho mảng. Trong hàm ta dùng vòng lặp for bắt đầu từ int i=0, kết thúc khi i<n và mỗi lần lặp i tăng lên 1. Trong vòng lặp ta nhập dữ liệu từ bàn phím cho từng phần tử a[i]. Bước 2: Ta khỏi tạo hàm Xuat(int a[],int n) dùng để hiển thị mảng ra màn hình. Trong hàm ta dùng vòng lặp for bắt đầu từ int i=0, kết thúc khi i<n và mỗi lần lặp i tăng lên 1. Trong vòng lặp ta hiển thị từng phần tử a[i] ra màn hình. Bước 3: Ta khởi tạo hàm BubbleSort(int a[], int n) sử dụng thuật toán nổi bọt để sắp xếp mảng tăng dần. Trong hàm ta dùng vòng lặp for bắt đầu từ int i=0, kết thúc khi i<n-1 và mỗi lần lặp i tăng lên 1. Trong vòng lặp for i ta dùng vòng lặp for bắt đầu từ int j=n-1, kết thúc khi j>i và mỗi lần lặp j giảm đi 1 (duyệt từ cuối mảng về vị trí thứ i thỏa mãn j>i). Trong vòng for j ta dùng if với điều kiện nếu a[j]<a[j-1] thỏa mãn thì đổi chỗ a[j] cho a[j-1] qua biến int tg. Kết thúc lặp ta gọi hàm Xuat(a,n) để hiển thị mảng đã sắp xếp ra màn hình. Bước 4: Trong hàm main ta khởi tạo mảng tĩnh số nguyên int a[100](có tối đa 100 phần tử), int n và nhận dữ liệu cho biến int n là số phần tử của mảng. Bước 5: Gọi hàm Nhap(a,n), Xuat(a,n) và BubbleSort(a,n) để hiển thị mảng đã sắp xếp rồi chạy chương trình. Chương trình giải bài tập sắp xếp mảng số nguyên tăng đần bằng thuật toán sắp xếp nổi bọt (Bubble Sort) trong ngôn ngữ lập trình C như sau: Thuật toán sắp xếp nổi bọt – Bubble sort là loại thuật toán sắp xếp đơn giản, cơ bản nhất trong các thuật toán sắp xếp. Nó có thể minh họa bằng nhiều loại ngôn ngữ lập trình khác nhau như C, C++, Java, pascal . . . Trong bài viết này, mình sẽ tóm tắt nội dung thuật toán, ý tưởng, cách sử dụng và độ phức tạp của thuật toán này. Đây cũng coi như là tài liệu mà mình dùng để ôn luyện lại kiến thức cơ bản về lập trình. Mục lục bài viết 1. Ý tưởng thuật toánGiống với cái tên của nó: nổi bọt – Bubble sort, thuật toán này sẽ hoạt động tương tự như những bọt nước nổi dần lên. Sau qua từng vòng lặp, các phần tử nhỏ hơn sẽ “nổi” dần về đầu mảng, các phần tử lớn sẽ nằm ở cuối mảng. Ý tưởng cụ thế:
Minh họa thuật toán sắp xếp nổi bọt:  Bạn có thể xem thêm minh họa thuật toán có kèm debug tại visualgo.net Một số thuật toán sắp xếp khác:
2. Code C/C++ thuật toán Bubble sortHầu hết các bạn mới học lập trình đều dùng thuật toán này. Nó dễ nhớ và dễ dàng thực hiện. Chỉ cần hiểu được cú pháp cơ bản là có thể thực hiện được rồi: /* Code by duongdinh24.com
Github: https://github.com/duongdinh24/
Code illustration bubble sort
*/
#include <stdio.h>
// Hàm swap dùng để đổi vị trí hai phần tử
void swap(int &x, int &y){
int temp = x;
x = y;
y = temp;
}
// Hàm sắp xếp nổi bọt
void bubbleSort(int arr[], int n){
int i, j;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1]){ // Nếu phần tử sau lớn hơn thì đổi chỗ
swap(arr[j], arr[j+1]);
}
}
// Hàm xuất mảng
void printArr(int arr[], int size){
for (int i=0; i < size; i++)
printf("%5d", arr[i]);
}
int main(){
int arr[] = {90, 5, 3, 1, 8, 7, 2, 4, 10}; // Khai báo mảng
int size = sizeof(arr)/sizeof(arr[0]); // Lấy kích thước của mảng
bubbleSort(arr, size);
printf("\n\n");
printf("Sorted array: ");
printArr(arr, size);
return 0;
}Kết quả chạy chương trình minh họa trên: 3. Độ phức tạp của thuật toánThuật toán sắp xếp nổi bọt là thuật toán đơn giản, dễ hiểu. Bạn chỉ cần có chút kiến thức căn bản là có thể hiểu được. Thuật toán này có độ phức tạp: O(N^2) trong một số trường hợp có thể là O(N) Ưu điểm của thuật toán:
Nhược điểm: Thuật toán này có độ phức tạp lớn O(n^2). Chính vì thế nó không phù hợp khi thao tác với dữ liệu lớn. Rất tốn thời gian và không thật sự tốt ưu. |
