Bubble Sort là thuật toán sắp xếp đơn giản nhất hoạt động bằng cách hoán đổi nhiều lần các phần tử liền kề nếu chúng không đúng thứ tự.
Sắp xếp nổi bọt là phương pháp sắp xếp đơn giản thường được sử dụng như ví dụ minh họa trong các giáo trình nhập môn lập trình. Bắt đầu từ đầu dãy, thuật toán tiến hành so sánh mỗi phần tử với phần tử đi sau nó và thực hiện đổi chỗ nếu chúng không theo đúng thứ tự. Quá trình này sẽ được lặp lại cho đến khi gặp lần duyệt từ đầu dãy đến cuối dãy mà không phải thực hiện đổi chỗ (tức là tất cả các phần tử đã đứng đúng vị trí).
Cách làm này đã đẩy phần tử lớn nhất xuống cuối dãy, trong khi đó những phần tử có giá trị nhỏ hơn được dịch chuyển về đầu dãy.
Mặc dù thuật toán này đơn giản, nhưng nó lại là thuật toán kém hiệu quả nhất trong ba thuật toán cơ bản trình bày trong mục này. Vì thế, ngoài mục đích giảng dạy, sắp xếp nổi bọt rất ít khi được sử dụng. Giáo sư Owen Astrachan (Bộ môn Khoa học máy tính, Đại học Duke) còn đề nghị không nên giảng dạy thuật toán này.
Ví dụ:
First Pass:
( 5 1 4 2 8) -> ( 1 5 4 2 8), Ở đây, thuật toán so sánh hai phần tử đầu tiên và hoán đổi vì 5> 1
(1 5 4 2 8) -> (1 4 5 2 8), Hoán đổi vì 5> 4
(1 4 5 2 8) -> (1 4 2 5 8), Hoán đổi từ 5> 2
(1 4 2 5 8 ) -> (1 4 2 5 8 ), Bây giờ , vì các phần tử này đã có thứ tự (8> 5), thuật toán không hoán đổi chúng.
Lượt đi thứ hai:
( 1 4 2 5 8) -> ( 1 4 2 5 8)
(1 4 2 5 8) -> (1 2 4 5 8), Hoán đổi vì 4> 2
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8 ) -> (1 2 4 5 8 )
Bây giờ, mảng đã được sắp xếp, nhưng thuật toán của chúng tôi không biết liệu nó đã hoàn thành hay chưa. Thuật toán cần một lần chuyển toàn bộ mà không có bất kỳ hoán đổi nào để biết nó được sắp xếp.
Lượt đi thứ ba:
( 1 2 4 5 8) -> ( 1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8) )
(1 2 4 5 8 ) -> (1 2 4 5 8 )
Ví dụ về hàm sắp xếp nổi bọt
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = (n-1); i > 0; i--)
// Last i elements are already in place
for (j = 0; j < i; j++)
if (arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
Phân tích thuật toán đổi chỗ:
- Best case: 0 đổi chỗ, 
/2 so sánh.
- Worst case: 
/2 đổi chỗ và so sánh.
- Average case: 
/4 đổi chỗ và 
/2 so sánh.
Tổng kết ba thuật toán sắp xếp cơ bản
Sau đây là các triển khai của Bubble Sort.
إرسال تعليق