Sắp xếp nổi bọt - Bubble Sort (Cấu trúc dữ liệu và giải thuật)

Sắp xếp nổi bọt là một giải thuật sắp xếp tương đối đơn giản. Giải thuật sắp xếp này được tiến hành thông qua việc so sánh các cặp phần tử liền kề nhau và tráo đổi vị trí nếu chúng không theo thứ tự.

Giải thuật này không phù hợp với việc sử dụng với những tập dữ liệu lớn khi mà độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο (n²) trong đó (n) là số phần tử.

Giải thuật sắp xếp nổi bọt là giải thuật chậm nhất trong số những giải thuật sắp xếp cơ bản. Giải thuật này còn chậm hơn cả giải thuật đổi chỗ trực tiếp trong khi số lần so sánh bằng nhau, nhưng vì đổi chỗ 2 phần tử kề nhau nên số lần đổi chỗ cũng nhiều hơn.

Cách giải thuật sắp xếp nổi bọt làm việc?

Giả sử chúng ta có một mảng không có thứ tự gồm những phần tử cho sau đây. Bây giờ chúng ta sẽ sử dụng giải thuật sắp xếp nổi bọt để sắp xếp mảng này.

Giải thuật sắp xếp nổi bọt bắt đầu với việc so sánh 2 phần tử đầu tiên, sau khi so sánh sẽ kiểm tra xem phần tử nào lớn hơn.

Trong trường hợp này, 33 lớn hơn 14 vì thế hai phần tử này đã theo thứ tự. Tiếp đó chúng ta cần so sánh 33 với 27.

Chúng ta thấy rằng 33 lớn hơn 27 vì thế cần tráo đổi thứ tự hai phần tử này.

Mảng mới thu được sẽ như hình dưới đây:

Tiếp đó chúng ta sẽ so sánh 33 và 35. Hai giá trị này đã sắp xếp theo thứ tự.

Sau đó chúng ta sẽ so sánh hai giá trị tiếp theo là 35 và 10.

Vì 10 nhỏ hơn 35 nên 2 giá trị này chưa sắp xếp theo thứ tự.

Tráo đổi thứ tự hai giá trị này. Chúng ta đã tiến tới cuối mảng. Vậy là sau khi lặp lại các thao tác, mảng sẽ trông như sau:

Để đơn giản, tiếp theo chúng ta sẽ hiển thị hình ảnh của mảng sau từng vòng lặp. Sau lần lặp thứ 2, mảng sẽ trông giống như dưới đây:

Sau mỗi vòng lặp, có ít nhất một giá trị sẽ di chuyển đến vị trí cuối. Sau vòng lặp thứ 3, mảng sẽ trông giống như hình dưới:

Và khi không cần tráo đổi thứ tự của phần tử nào nữa, giải thuật sắp xếp nổi bọt sẽ thấy rằng mảng này đã được sắp xếp xong.

Tiếp theo, chúng ta cần tìm hiểu thêm một số khía cạnh thực tế của giải thuật sắp xếp.

Giải thuật cho sắp xếp nổi bọt (Bubble Sort)

Giả sử list là một mảng có n phần tử. Tiếp đó giả sử hàm swap dùng để tráo đổi giá trị của những phần tử trong mảng (đây là giả sử, tất nhiên là các bạn có thể viết code riêng cho hàm swap này).

Bắt đầu giải thuật BubbleSort (list)
for tất cả phần tử trong list
if list [i] > list [i+1]
swap (list [i], list [i+1])
kết thúc if
kết thúc for
return list
Kết thúc BubbleSort

Giải thuật mẫu cho sắp xếp nổi bọt (Bubble Sort)

Chúng ta có thể thấy rằng giải thuật sắp xếp nổi bọt so sánh từng cặp phần tử trong mảng này trừ khi tất cả mảng đó đã hoàn toàn được sắp xếp theo thứ tự tăng dần. Điều đó có thể làm tăng độ phức tạp, tức là làm tăng các thao tác so sánh và tráo đổi không thực sự cần thiết nếu như mảng này chưa cần sự tráo đổi nào nữa khi tất cả những phần tử của mảng đã được sắp xếp theo thứ tự tăng dần rồi.

Để tránh xảy ra trường hợp này, chúng ta có thể dùng một biến swapped chẳng hạn để giúp chúng ta có thể biết rằng có cần thực hiện thao tác tráo đổi thứ tự hay không. Nếu không cần thiết thực hiện thì thoát khỏi vòng lặp.

Bạn theo dõi phần giải thuật theo mẫu minh họa dưới đây:

Bắt đầu hàm bubbleSort (list: mảng các phần tử)
loop = list. count; 
for i = 0 tới loop-1 thực hiện: 
swapped = false
for j = 0 tới loop-1 thực hiện: 
/* so sánh các phần tử đứng cạnh nhau */
if list [j] > list [j+1] then
/* tráo đổi chúng */
swap (list [j], list [j+1])
swapped = true
kết thúc if
kết thúc for
/*Nếu không cần tráo đổi các phần tử nào nữa thì
tức là mảng này đã được sắp xếp theo đúng thứ tự. Thoát khỏi vòng lặp. */
if (not swapped) then
break
kết thúc if
kết thúc for
Kết thúc hàm return list

Triển khai giải thuật sắp xếp nổi bọt trong C

Một điều nữa mà chúng ta chưa đề cập đến trong 2 phần thiết kế giải thuật đó chính là cứ sau mỗi một vòng lặp thì các giá trị lớn nhất sẽ được xếp ở vị trí cuối mảng (như trong hình minh họa: sau vòng lặp 1 là 35; sau vòng lặp 2 sẽ là 33 và 35; …). Do đó, vòng lặp tiếp theo sẽ không cần bao gồm cả những phần tử đã được sắp xếp này. Để thực hiện điều này, trong phần code chúng ta sẽ giới hạn vòng lặp lặp bên để tránh phải thực hiện lặp lại những giá trị đã qua sắp xếp này.

Bài tiếp: Sắp xếp chèn - Insertion Sort (Cấu trúc dữ liệu và giải thuật)