Sắp xếp bong bóng là một thuật toán sắp xếp đơn giản. Thuật toán sắp xếp này là thuật toán dựa trên so sánh, trong đó mỗi cặp yếu tố liền kề được so sánh và các yếu tố được hoán đổi nếu chúng không theo thứ tự. Thuật toán này không phù hợp với các tập dữ liệu lớn vì độ phức tạp trung bình và trường hợp xấu nhất của nó là (n 2 ) trong đó n là số lượng mục.
Cách sắp xếp bong bóng hoạt động?
Chúng tôi lấy một mảng chưa sắp xếp cho ví dụ của chúng tôi. Sắp xếp bong bóng mất (n 2 ) thời gian vì vậy chúng tôi giữ cho nó ngắn và chính xác.
Sắp xếp bong bóng bắt đầu với hai yếu tố đầu tiên, so sánh chúng để kiểm tra xem yếu tố nào lớn hơn.
Trong trường hợp này, giá trị 33 lớn hơn 14, vì vậy nó đã ở trong các vị trí được sắp xếp. Tiếp theo, chúng tôi so sánh 33 với 27.
Chúng tôi thấy rằng 27 nhỏ hơn 33 và hai giá trị này phải được hoán đổi.
Mảng mới sẽ trông như thế này -
Tiếp theo, chúng tôi so sánh 33 và 35. Chúng tôi thấy rằng cả hai đều ở vị trí đã được sắp xếp.
Sau đó, chúng tôi chuyển sang hai giá trị tiếp theo, 35 và 10.
Chúng ta biết rằng 10 nhỏ hơn 35. Do đó chúng không được sắp xếp.
Chúng tôi trao đổi những giá trị này. Chúng tôi thấy rằng chúng tôi đã đạt đến cuối của mảng. Sau một lần lặp, mảng sẽ trông như thế này -
Nói chính xác, bây giờ chúng ta đang hiển thị một mảng sẽ trông như thế nào sau mỗi lần lặp. Sau lần lặp thứ hai, nó sẽ trông như thế này -
Lưu ý rằng sau mỗi lần lặp, ít nhất một giá trị sẽ di chuyển ở cuối.
Và khi không cần trao đổi, bong bóng sẽ biết rằng một mảng được sắp xếp hoàn chỉnh.
Bây giờ chúng ta nên xem xét một số khía cạnh thực tế của sắp xếp bong bóng.
Thuật toán
Chúng tôi giả sử danh sách là một mảng gồm n phần tử. Chúng tôi cũng cho rằng trao đổi chức năng hoán đổi giá trị của các phần tử mảng nhất định.
begin BubbleSort(list)
for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort
Mã giả
Chúng tôi quan sát trong thuật toán rằng Bubble Sort so sánh từng cặp phần tử mảng trừ khi toàn bộ mảng được sắp xếp hoàn toàn theo thứ tự tăng dần. Điều này có thể gây ra một vài vấn đề phức tạp như nếu mảng không cần hoán đổi nữa vì tất cả các phần tử đã tăng dần.
Để giải quyết vấn đề, chúng tôi sử dụng một biến cờ được hoán đổi sẽ giúp chúng tôi xem liệu có bất kỳ trao đổi nào đã xảy ra hay không. Nếu không có trao đổi nào xảy ra, tức là mảng không cần xử lý nữa để sắp xếp, nó sẽ ra khỏi vòng lặp.
Mã giả của thuật toán BubbleSort có thể được viết như sau -
procedure bubbleSort( list : array of items )
loop = list.count;
for i = 0 to loop-1 do:
swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */
if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if
end for
/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped) then
break
end if
end for
end procedure return list
Thực hiện
Một vấn đề nữa chúng tôi đã không giải quyết trong thuật toán ban đầu của chúng tôi và mã giả ngẫu hứng của nó, đó là, sau mỗi lần lặp, các giá trị cao nhất sẽ lắng xuống ở cuối mảng. Do đó, lần lặp tiếp theo không cần bao gồm các phần tử đã được sắp xếp. Với mục đích này, trong quá trình thực hiện, chúng tôi giới hạn vòng lặp bên trong để tránh các giá trị đã được sắp xếp.
Được cập nhật: 22 tháng 4 lúc 8:04:14 | Lượt xem: 1848