Thuật Toán Sắp Xếp Nổi Bọt Bubble Sort

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án
• 2. Code C/C++ thuật toán Bubble sort
• 3. Độ phức tạp của thuật toán

1. Ý tưởng thuật toán

Giố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ế:

• Tiến hành sét 2 phần tử đứng cạnh nhau, nếu phần từ sau nhỏ hơn phần tử đứng trước thì tiến hành đổi chỗ chúng. Phần tử nhỏ sẽ nổi dần lên trên.
• Lập lại hành động cho tới khi không có cặp nào thỏa mãn. Tối đa là N-1 lần (N là số phần tử của mảng). Tức là cho 2 vòng lặp lồng nhau, xíu nữa xem code là hiểu nhé

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:

• Thuật toán sắp xếp nhanh – Quich sortThuật toán sắp xếp chèn – Insert sort
• Thuật toán sắp xếp trộn – Merge sort

2. Code C/C++ thuật toán Bubble sort

Hầ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án

Thuậ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:

• Đơn giản, dễ hiểu
• Tiết kiệm bộ nhớ

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.

Bài của mình đến đây là hết, cảm ơn bạn đã ghé thăm website!