Giải Thuật sắp xếp: Bubble sort

Hề lú everyone lại là tôi đây, 1 dev cùi bép muốn chia sẽ những gì mình tưởng mình biết nghen. Ngày hôm nay chúng ta sẽ cùng nhau tìm hiểu bubble sort, 1 thuật toán mà có lẽ ai ai là dân lập trình cũng đã đọc qua (nhỉ !?). Vậy hãy cùng nhau tìm hiểu xem "nó" là gì ?

Bubble sort là gì ?

Bubble sort là gì? là sắp xếp bong bóng chứ gì vậy mà cũng phải hỏi à? Như các bạn đã biết (hoặc không) thì khi chúng ta có thể tạo ra bong bóng từ xà phòng, còn không thì bạn là người không có tuổi thơ nhé. Mỗi lúc bạn thổi xà phòng tạo ra nhiều bong bóng to nhỏ khác nhau, chúng sẽ trôi nổi trong không trung. Bong bóng nhẹ bay sẽ có xu hướng bay lên cao hơn bong bóng nặng. Cứ thế nó sẽ tạo thành 1 chuỗi nhưng bong bóng có thứ tự to dần.

Thuật toán bubble sort cũng dựa trên hiện tượng tự nhiên ấy mà hình thành. Bubble sort là 1 thuật toán dễ hiểu, trực quan. Và nó cũng là 1 thuật toán rất ổn nếu như bạn muốn bắt đầu tìm hiểu về giải thuật.

Bubble sort hoạt động thế nào ?

Cho trước 1 array thế này:

Chúng ta sẽ cùng nhau dùng bubble sort để sắp xếp chúng theo thứ tự tăng dần.Trong bubble sort chúng ta sẽ dùng vòng lặp để đi qua array nhiều lần để sắp xếp lại từng phần tử, cho đến khi tất cả đúng thứ tự mong muốn.

Cụ thể hơn tí hen. Chúng ta sẽ lặp qua mảng, sẽ phải kiểm tra xem số hiện tại có lớn hơn so với số liền kề của nó hay không, nếu có thì sẽ hoán đổi vị trí của 2 số đó với nhau. Lưu ý hen, chúng ta sẽ đổi chỗ trực tiếp trên mảng, chứ không hề dùng 1 bộ nhớ tạm nào khác hết.

Sau khi chúng ta đã duyệt qua toàn bộ mảng 1 lần, chúng ta sẽ kiểm tra xem có sự kiện hoán đổi nào vừa xảy ra không trong lần lặp đó không. Nếu có, chúng ta sẽ lặp lại 1 lần nữa để như trên để tìm và hoán đổi thứ tự các số, tới khi nào các số đã hoàn toàn được sắp xếp theo thứ tự đúng nhất (khi không hoán đổi).Các bạn nhìn hình này để dễ hình dung hơn hen.

Đầu tiên, giá trị ban đầu của chúng ta là 6

Kiểm tra xem 6 có lớn hơn với số liền kề của nó không (số liền kề bên phải), số đó lúc này là 3. Oh yeah, 6 lớn hơn 3 (phải không nhỉ !?), đúng rồi, chúng ta sẽ hoán đổi vị trí của 6 và 3 với nhau.

Okay, số 6 hiện tại đã nằm ở ô số 1 của mảng. Và tiếp tục xem số liền kề với 6, là số 9, kiểm tra xem 6 có lớn hơn 9 không. Và lần này thì không, nghĩa là chúng ta không cần hoán đổi 2 số nữa và vị trí của số hiện tại sẽ nằm ở số lớn hơn trong 2 số, lúc này là 9.

Xem số tiếp nào, 9 và 8. Okay 9 lớn hơn, đổi chỗ nào.

9 và 4 thì sao ? đổi chỗ gấp !!!

Lại là số 6 và 9 (có tí duyên nhỉ?). Vẫn là số 9 lớn hơn, số 9 đang bất bại @@.

9 thì lớn hơn 5.

cuối cùng là 9 và 2. 9 lớn hơn nhe.

Vậy là hết số để so sánh với số 9, số lớn nhất đã tự chìm xuống dưới cuối của array. Vậy là chúng ta đã xong 1 vòng lặp qua nguyên 1 array rồi, vậy nãy giờ chúng ta có dùng phép hoán đổi để đổi vị trí của chúng không? Chúng ta dùng rất nhiều nhé. Như vậy có thể hiểu là array chưa hoàn toàn sắp xếp đúng thứ tự ta muốn, ta chỉ chắc chắn 1 điều số 9 là số lớn nhất, và đã đúng vị trí ta muốn. Vậy ta sẽ quay tiếp tục vòng lặp qua array 1 lần nữa. lần này vị trị bắt đầu sẽ là số 3 (vị trí 0)

À số nào đã đúng vị trí rồi thì màu xanh nhé mọi người :D :D

Chúng ta vẫn xét như ban đầu, 3 và số liền kề bên phải của nó là 6, thấy 6 lớn hơn, không cần phải hoán đổi, và vị trí so sánh hiện tại sẽ nằm ở số lớn hơn là 6. Tiếp theo là 6 và 8, 6 bé hơn, vị trí so sánh hiện tại là 8.

Mấy bạn tự chạy tiếp nhe, chạy tới vị trí trước số 9. Vì số 9 đã đúng thứ tự rồi.

Khi xong thì xem lại chúng ta có sử dụng hoán đổi vị trí không. Câu trả lời là có. Vậy thì phải làm sao nhỉ? Lại lặp lại chứ sao !!!

Như trên thì 3 và 6 không đổi chỗ. vị trí so sánh sẽ là 6, và 6 sẽ đổi chỗ với 4 .

Và tiếp theo là 6 với 6. 6 có lớn hơn 6 không ??? KHÔNG lần này vị trí so sánh cũng sẽ nhảy về số phía sau. Là số 6 ở vị trí 3

Và cứ tiếp tục tới vì trí trước số 8.

Chúng ta sẽ xem lại lần nữa xem có sử dụng phép hoán đổi không. Có sử dụng. lại tiếp tục lặp từ số 3.

Okay, tiếp nhé.

Lần này ta tìm được vị trí của số 5. Sắp xong rồi :D

1 bước nữa thôiiii

Số 2 hết có cái gì để so sánh rồi nên thôi dừng lại thôi.

Time Complexity và Space Complexity

Ắt hẳn là bạn thấy giải thuật này đơn giản quá mức hen. Đúng rồi nó chán lắm lắm luôn. Và bởi vị nó dễ hiểu quá nên nó rất chậm. Bubble sort có Time complexity là O(n²) trong trường hợp xấu nhất. Và trong trường hợp tốt nhất chúng ta vẫn phải chạy qua 1 lần cả array để xem nó đã sắp xếp chưa, độ phúc tạp lúc này là O(n).

Như đã nói ở trên, Bubble sort thực hiện phép hoán đổi tại chính array nơi nó ở, không sử dụng thêm 1 bộ nhớ ngoài nào hết như vậy space complexity là O(1)

Code như thế nào

Hãy cùng nhay implement bằng ruby hen.

Ta có 1 function tên là bubbleSort có param truyền vào là 1 mảng và 1 biến cờ sorted là false

Giờ ta cần đi qua nguyên cả array. Và khi array chưa đc sorted thì chúng ta cần sort nó.

Chỉ lặp tới array.size vị trí kế cuối thôi nha :D :D

Chúng ta kiểm tra vị trí hiện tại có lớn hơn vì trí kế nó không? Nếu có thì hoán đổi vị trí, và sorted = false

Về cơ bản thì chỉ vậy thôi đó, nhưng nếu muốn thì chúng ta có thể chỉnh sửa 1 chút để thuật toán chạy tốt hơn.

Tại sao chúng ta thêm biên counter của nợ này? Vì chúng ta biết là những số nằm cuối khi xong 1 vòng lặp chắc chắn là vị trí đúng, nên ta không cần xét nữa.

Thiệt tình là cái này có làm nó nhanh hơn tí đó, nhưng mà time complexity vẫn là O(n²) thôi, vì sao thì các bạn có thể đọc thêm tại đây

Kết

Yo hôm nay chúng ta cùng nhau tìm hiểu bubble sort là gì nè, cách thức hoạt động nè, code như thế nào nè, blah blah. Nói chung thì mình thấy đây là 1 giải thuật dễ hiểu và dễ cho người mới nhất, nên mình viết trước zậy hoy.

Cảm ơn mọi người đã đọc nhen.