Cấu trúc dữ liệu - Thuật toán sắp xếp bong bóng

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 đó từng cặp phần tử liền kề được so sánh và các phần 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ặt hàng.

Cách sắp xếp bong bóng hoạt động?

Chúng tôi lấy một mảng không được sắp xếp để làm ví dụ. Sắp xếp bong bóng mất Ο (n 2 ) thời gian nên chúng tôi đang giữ cho nó ngắn gọn và chính xác.

Sắp xếp bong bóng bắt đầu với hai phần tử đầu tiên, so sánh chúng để kiểm tra xem cái 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ó đã nằm 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 đổi chỗ cho nhau.

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 ở các vị trí đã được sắp xếp.

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

Khi đó 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 hoán đổi các giá trị này. Chúng tôi thấy rằng chúng tôi đã đến cuối mảng. Sau một lần lặp, mảng sẽ trông như thế này:

Nói một cách chính xác, chúng ta đang chỉ ra một mảng trông như thế nào sau mỗi lần lặp. Sau lần lặp thứ hai, nó sẽ giống như thế này -

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

Và khi không yêu cầu hoán đổi, sắp xếp bong bóng biết rằng một mảng được sắp xếp hoàn toàn.

Bây giờ chúng ta nên xem xét một số khía cạnh thực tế của phân loại bong bóng.

Thuật toán

Chúng tôi giả định list là một mảng của ncác yếu tố. Chúng tôi cũng giả định rằngswap hàm hoán đổi giá trị của các phần tử mảng đã cho.

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 thấy trong thuật toán 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 số vấn đề phức tạp như điều gì xảy ra 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ờ swappedđiều này sẽ giúp chúng tôi xem liệu có bất kỳ sự hoán đổi nào đã xảy ra hay không. Nếu không có hoán đổi nào xảy ra, tức là mảng không yêu cầu xử lý nữa để được sắp xếp, nó sẽ thoát 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 mà chúng tôi đã không giải quyết trong thuật toán ban đầu và mã giả ứng biến 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ì mục đích này, khi triển khai, chúng tôi hạn chế vòng lặp bên trong để tránh các giá trị đã được sắp xếp.

Để biết về cách triển khai sắp xếp bong bóng trong ngôn ngữ lập trình C, vui lòng nhấp vào đây .