Cộng đồng chia sẻ tri thức Lib24.vn

Thuật toán sắp xếp bong bóng

Gửi bởi: Võ Thị Hường 13 tháng 2 2020 lúc 11:14:41


Mục lục
* * * * *

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.

Thuật toán sắp xếp bong bóng

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.

Thuật toán sắp xếp bong bóng

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.

Thuật toán sắp xếp bong bóng

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.

Thuật toán sắp xếp bong bóng

Mảng mới sẽ trông như thế này -

Thuật toán sắp xếp bong bóng

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.

Thuật toán sắp xếp bong bóng

Sau đó, chúng tôi chuyển sang hai giá trị tiếp theo, 35 và 10.

Thuật toán sắp xếp bong bóng

Chúng ta biết rằng 10 nhỏ hơn 35. Do đó chúng không được sắp xếp.

Thuật toán sắp xếp bong bóng

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 -

Thuật toán sắp xếp bong bóng

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 -

Thuật toán sắp xếp bong bóng

Lưu ý rằng sau mỗi lần lặp, ít nhất một giá trị sẽ di chuyển ở cuối.

Thuật toán sắp xếp bong bóng

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.

Thuật toán sắp xếp bong bóng

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: hôm kia lúc 7:05:47 | Lượt xem: 1834