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;

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.

Ư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.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Contact Me on Zalo
Call now