Rate this post

Bubble sort là một thuật toán sắp xếp đơn giản, dựa trên việc so sánh và hoán đổi các phần tử trong mảng. Nó lặp qua mảng và so sánh mỗi cặp phần tử liền kề, nếu phần tử trước lớn hơn phần tử sau thì hoán đổi chúng. Quá trình này sẽ được lặp lại cho đến khi mảng sắp xếp hoàn chỉnh.

Các bài viết liên quan;

Tóm tắt nội dung

Giới thiệu về Bubble Sort

Bubble Sort là một thuật toán sắp xếp đơn giản trong lập trình, thường được sử dụng để sắp xếp một danh sách các phần tử theo thứ tự tăng dần hoặc giảm dần. Thuật toán này là một ví dụ điển hình của sắp xếp “so sánh và hoán đổi” (comparison-based sorting algorithm).

Cách thức hoạt động của Bubble Sort rất đơn giản. Thuật toán duyệt qua danh sách các phần tử lần lượt, so sánh hai phần tử liền kề và hoán đổi chúng nếu chúng không ở đúng thứ tự mong muốn. Quá trình này được lặp lại cho đến khi danh sách được sắp xếp hoàn toàn.

Mặc dù Bubble Sort là một thuật toán đơn giản và dễ hiểu, nhưng nó không phải là một thuật toán hiệu quả trong trường hợp danh sách có kích thước lớn. Độ phức tạp thời gian của Bubble Sort là O(n^2), nghĩa là thời gian thực thi tăng theo bình phương của số phần tử trong danh sách. Vì vậy, nếu danh sách có kích thước lớn, sẽ có những thuật toán sắp xếp khác hiệu quả hơn mà bạn có thể sử dụng.

Mặc dù Bubble Sort ít được sử dụng trong các ứng dụng thực tế, nó vẫn có ý nghĩa giảng dạy và học tập, giúp người mới học lập trình hiểu rõ về cách hoạt động của thuật toán sắp xếp và khám phá cách thức tối ưu hóa thuật toán sắp xếp.

Xem thêm Các thuật toán sắp xếp(sort)

Cách hoạt động của Bubble Sort

Bubble Sort hoạt động bằng cách so sánh và hoán đổi các phần tử liền kề trong danh sách cho đến khi danh sách được sắp xếp theo thứ tự mong muốn. Dưới đây là cách hoạt động chi tiết của Bubble Sort:

Duyệt qua từng phần tử trong danh sách, bắt đầu từ phần tử đầu tiên.
So sánh phần tử hiện tại với phần tử liền kề phía sau.
Nếu phần tử hiện tại lớn hơn phần tử liền kề, thực hiện hoán đổi hai phần tử đó.
Tiếp tục di chuyển tới phần tử tiếp theo và lặp lại quá trình so sánh và hoán đổi cho đến khi đến cuối danh sách.
Sau mỗi lần duyệt qua toàn bộ danh sách, phần tử lớn nhất trong danh sách sẽ được đưa vào vị trí cuối cùng.
Lặp lại các bước 2-5 cho đến khi danh sách được sắp xếp hoàn toàn.

Với mỗi lần lặp, Bubble Sort đẩy phần tử lớn nhất trong danh sách từ đầu đến cuối, tạo ra một “bong bóng” lớn di chuyển từ trên xuống dưới. Quá trình này tiếp tục cho đến khi không còn bất kỳ hoán đổi nào xảy ra, tức là danh sách đã được sắp xếp hoàn toàn.

Tuy Bubble Sort đơn giản, nhưng nó có độ phức tạp thời gian là O(n^2), trong đó n là số phần tử trong danh sách. Điều này làm cho Bubble Sort không hiệu quả trong trường hợp danh sách có kích thước lớn.

Phân tích độ phức tạp của Bubble Sort

Độ phức tạp của Bubble Sort có thể được phân tích như sau:

Thời gian thực thi: Trong trường hợp tốt nhất, khi danh sách đã được sắp xếp và không cần thực hiện bất kỳ hoán đổi nào, Bubble Sort chỉ mất O(n) thời gian để duyệt qua danh sách. Tuy nhiên, trong trường hợp xấu nhất và trung bình, khi danh sách cần được hoán đổi nhiều lần, Bubble Sort mất O(n^2) thời gian để hoàn thành sắp xếp. Điều này là do trong mỗi lần duyệt qua danh sách, ta cần so sánh và hoán đổi các phần tử liền kề, tổng cộng là O(n) lần, và ta cần thực hiện quá trình này n lần.
Không gian bộ nhớ: Bubble Sort chỉ yêu cầu một hằng số lượng bộ nhớ bổ sung để lưu trữ các biến tạm thời và các biến điều kiện. Do đó, không gian bộ nhớ mà Bubble Sort sử dụng là O(1), tức là không phụ thuộc vào kích thước của danh sách đầu vào.

Tổng kết, Bubble Sort có độ phức tạp thời gian là O(n^2), với n là số phần tử trong danh sách. Điều này đồng nghĩa với việc thời gian thực thi tăng theo bình phương của kích thước danh sách. Vì vậy, Bubble Sort không hiệu quả trong trường hợp danh sách có kích thước lớn.

Xem thêm OpenCV template Matching

Triển khai bubble sort trong C++:

Ví dụ về bubble sort trong C++:

#include <iostream>
using namespace std;

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])
            {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main()
{
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Dãy số trước khi sắp xếp: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    bubbleSort(arr, n);
    cout << "Dãy số sau khi sắp xếp: \n";
    for (int i = 0; i < n; i++)
       cout << arr[i] << " "; 
  return 0; 
}

Trong ví dụ trên, hàm `bubbleSort` được sử dụng để sắp xếp mảng số nguyên. Nó sẽ lặp qua mảng và so sánh mỗi cặp phần tử liền kề, nếu phần tử trước lớn hơn phần tử sau thì hoán đổi chúng. Quá trình này sẽ được lặp lại cho đến khi mảng sắp xếp hoàn chỉnh.

Bubble sort là một thuật toán sắp xếp rất đơn giản và dễ hiểu nhưng hiệu suất không tốt với mảng lớn vì nó phải lặp qua mảng nhiều lần và so sánh mỗi phần tử. 

Giải thích đoạn code ở trên

Trong đoạn code trên, chúng ta đang sử dụng thuật toán sắp xếp “bubble sort” để sắp xếp mảng số nguyên.

Trong hàm main(), chúng ta khai báo một mảng số nguyên và in ra mảng trước khi sắp xếp.
Sau đó, chúng ta gọi hàm bubbleSort(arr, n) để sắp xếp mảng.
Trong hàm bubbleSort, chúng ta sử dụng 2 vòng lặp for để duyệt qua từng phần tử trong mảng và so sánh với phần tử kế tiếp. Nếu phần tử trước lớn hơn phần tử sau, chúng ta sẽ hoán đổi chúng.
Cuối cùng, chúng ta in ra mảng sau khi sắp xếp.

Với thuật toán “bubble sort” sắp xếp, mảng sẽ được sắp xếp từ nhỏ đến lớn. Nếu muốn sắp xếp từ lớn đến nhỏ thì chỉ cần thay đổi dấu > thành < trong điều kiện so sánh trong hàm bubbleSort.

Xem thêm Thuật toán Shell Sort là gì ?

Ưu điểm bubble sort c++

Đơn giản: Bubble sort rất dễ hiểu và triển khai, vì nó chỉ sử dụng vòng lặp và so sánh các phần tử trong mảng.
Không cần bộ nhớ phụ: bubble sort không cần sử dụng bộ nhớ phụ nên rất tiết kiệm bộ nhớ.
Khả năng sắp xếp mảng đã sắp xếp: Nếu mảng đã sắp xếp trước đó, bubble sort sẽ dừng lại sau 1 vòng lặp do không cần thiết phải tiếp tục so sánh các phần tử.

Nhưng cũng có những nhược điểm của nó:

Hiệu suất thấp: bubble sort không tốt với mảng lớn vì nó phải lặp qua mảng nhiều lần và so sánh mỗi phần tử.
Không phù hợp với dữ liệu lớn: Vì thuật toán bubble sort phụ thuộc vào số lần so sánh và hoán đổi, nên nó không phù hợp với mảng lớn và có thể mất nhiều thời gian để sắp xếp.
Không tối ưu khi sử dụng với dữ liệu không sắp xếp hoặc ngẫu nhiên: Vì bubble sort chỉ tối ưu khi sử dụng với dữ liệu đã sắp xếp hoặc gần sắp xếp, nên nó không phù hợp với dữ liệu không sắp xếp hoặc ngẫu nhiên.
Không tối ưu với dữ liệu có thứ tự giảm dần, vì nó vẫn sẽ lặp qua hết mảng nhiều lần.

Ứng dụng của Bubble Sort

Bubble Sort được sử dụng trong các trường hợp sau:

Sắp xếp mảng nhỏ: Với các mảng nhỏ có kích thước tương đối nhỏ, Bubble Sort có thể là một giải thuật đơn giản và dễ hiểu để sắp xếp các phần tử.
Đào tạo và giảng dạy: Bubble Sort thường được sử dụng trong quá trình giảng dạy và đào tạo trong lĩnh vực khoa học máy tính để giúp sinh viên hiểu rõ về cách hoạt động của một thuật toán sắp xếp đơn giản.
Mục đích giả lập: Bubble Sort có thể được sử dụng để tạo giả lập một thuật toán sắp xếp trong các mô phỏng hoặc các bài toán thực tế.

Tuy nhiên, Bubble Sort không phải là thuật toán hiệu quả trong các trường hợp có dữ liệu lớn. Với các tập dữ liệu lớn, nên xem xét sử dụng các thuật toán sắp xếp khác như Quick Sort, Merge Sort hoặc Heap Sort, vì chúng có độ phức tạp thời gian tốt hơn.

So sánh Bubble Sort với các thuật toán sắp xếp khác

Bubble Sort là một thuật toán sắp xếp đơn giản, nhưng hiệu quả của nó không cao so với các thuật toán sắp xếp khác trong nhiều trường hợp. Dưới đây là so sánh giữa Bubble Sort và một số thuật toán sắp xếp khác:

Bubble Sort và Insertion Sort:

Độ phức tạp thời gian: Cả hai thuật toán đều có độ phức tạp thời gian là O(n^2) trong trường hợp xấu nhất. Tuy nhiên, Insertion Sort thường hiệu quả hơn Bubble Sort trong các tình huống thực tế.
So sánh: Insertion Sort có khả năng sắp xếp một phần mảng đã sắp xếp nhanh hơn, trong khi Bubble Sort vẫn phải duyệt qua toàn bộ mảng.

Bubble Sort và Quick Sort:

Độ phức tạp thời gian: Bubble Sort có độ phức tạp thời gian là O(n^2), trong khi Quick Sort có độ phức tạp trung bình là O(nlog(n)). Quick Sort nhanh hơn Bubble Sort đáng kể cho các tập dữ liệu lớn.
So sánh: Quick Sort sử dụng phương pháp chia để trị, chọn một phần tử chốt (pivot) để phân chia mảng thành các phần tử nhỏ hơn và lớn hơn pivot. Điều này giúp Quick Sort thực hiện các hoán đổi và sắp xếp một cách hiệu quả hơn so với Bubble Sort.

Bubble Sort và Merge Sort:

Độ phức tạp thời gian: Cả hai thuật toán đều có độ phức tạp thời gian là O(nlog(n)). Tuy nhiên, Merge Sort thường hiệu quả hơn Bubble Sort trong các tình huống thực tế.
So sánh: Merge Sort sử dụng phương pháp chia mảng thành các nửa và sau đó kết hợp các nửa đã sắp xếp thành một mảng mới đã sắp xếp. Với cách tiếp cận này, Merge Sort giúp tối ưu hóa quá trình sắp xếp và hoán đổi dữ liệu, cho phép nó thực hiện tốt hơn so với Bubble Sort.

Tổng quan, Bubble Sort không phải là thuật toán hiệu quả cho các tập dữ liệu lớn và thường không được sử dụng trong các ứng dụng thực tế. Các thuật toán khác như Quick Sort và Merge Sort thường được ưu tiên vì độ phức tạp thời gian tốt hơn và hiệu suất cao hơn.

Xem thêm Gnome Sort là gì ?

Algorithm, C/C++

bubble sort trong c++