Sắp xếp nổi bọt (Bubble Sort) trong Java: Hướng dẫn chi tiết

Cách viết thuật toán Sắp xếp nổi bọt trong Java

Khi lập trình viên nói về bubble sort, họ không nói về bong bóng nước mà bạn có thể đã thổi tại một thời điểm nào đó. Họ nói về thuật toán sắp xếp dùng để sắp xếp danh sách các mục.

Trong hướng dẫn này, chúng ta sẽ nói về bubble sort và cách nó hoạt động. Chúng ta sẽ triển khai bubble sort dùng Java để bạn hiểu thuật toán này chuyển thành mã như thế nào. Không nói thêm nữa, hãy đi sâu vào bubble sort Java!

Bubble Sort trong Java là gì?

Bubble sort là thuật toán sắp xếp giá trị bằng cách so sánh các phần tử liền kề và hoán đổi chúng nếu chúng xuất hiện theo thứ tự sai.

Quá trình này lặp lại cho đến khi mọi mục trong danh sách được sắp xếp đúng. Bubble sort có thể dùng để sắp xếp danh sách theo thứ tự tăng dần hoặc giảm dần.

Bubble sort là thuật toán sắp xếp đầu tiên được dạy trong các lớp thuật toán. Điều này là vì chúng dễ hiểu hơn các thuật toán khác như insertion sort hay selection sort, và cung cấp giới thiệu tốt cho thuật toán sắp xếp.

Bubble sort hiệu quả nhất khi dữ liệu đã gần như được sắp xếp. Tuy nhiên, nếu dữ liệu hoàn toàn chưa sắp xếp, loại sắp xếp khác có thể hiệu quả hơn. 

Bubble Sort hoạt động như thế nào?

Trước khi viết mã cho bubble sort Java, trước hết chúng ta phải hiểu thuật toán này được triển khai thực tế như thế nào.

Xem danh sách sau:

Bubble sort bắt đầu bằng so sánh phần tử đầu và thứ hai trong danh sách.

Nếu phần tử đầu lớn hơn phần tử thứ hai, hai phần tử này hoán đổi vị trí. Trong trường hợp này, 5 không lớn hơn 9, nên các phần tử giữ nguyên vị trí.

Sau đó, thuật toán sẽ so sánh hai mục tiếp theo. 9 lớn hơn 2, nên hai số này hoán đổi:

Quá trình này lặp lại cho đến khi mọi mục trong danh sách đã được so sánh. Trong trường hợp này, còn một so sánh nữa: 9 có lớn hơn 7 không? 9 lớn hơn 7, nên hai số này hoán đổi:

Danh sách gần như đã được sắp xếp. Khi mọi mục đã được so sánh, bubble sort sẽ bắt đầu lại cho đến khi mọi phần tử được sắp xếp.

5 lớn hơn 2, nên hai số này hoán đổi.

Danh sách giờ đã được sắp xếp đúng. Bubble sort sẽ tiếp tục so sánh số cho đến khi đến cuối danh sách, rồi dừng lại. Đó là tất cả về bubble sort. Đây chắc chắn là thuật toán dễ dùng khi bạn nắm được cách hoạt động.

Cách viết Bubble Sort trong Java

Biết lý thuyết là một chuyện nhưng bạn đến đây để học về bubble sort Java. Chúng ta hãy thảo luận cách triển khai bubble sort trong Java.

Có hai loại bubble sort:

• Bubble sort tiêu chuẩn (Standard bubble sort)
• Bubble sort tối ưu (Optimized bubble sort)

Bubble sort tiêu chuẩn thực hiện tất cả so sánh có thể có ngay cả khi mảng đã được sắp xếp. Điều này làm tăng thời gian thực thi. Điều này làm cho thuật toán kém hiệu quả hơn.

Bubble sort tối ưu theo dõi xem danh sách đã được sắp xếp chưa bằng cách dùng biến bổ sung. Điều này cho phép dừng sắp xếp ngay khi danh sách đã được sắp xếp. 

Hãy bắt đầu viết bubble sort tiêu chuẩn.

Bubble Sort tiêu chuẩn

Đầu tiên, chúng ta sẽ import thư viện Arrays vào mã. Chúng ta sẽ dùng này sau để in danh sách số đã sắp xếp ra console:

import java.util.Arrays;

Bây giờ đã xong phần đó, chúng ta có thể bắt đầu viết thuật toán.

Chúng ta sẽ bắt đầu bằng định nghĩa lớp BubbleSort chứa mã cho chương trình Java, và hàm thực hiện sắp xếp:

class BubbleSort { void sortNumbers(int array[]) { int size = array.length; for (int item = 0; item < size - 1; item++) { for (int j = 0; j < size - item - 1; j++) { if (array[j] > array[j + 1]) { int temporary = array[j]; array[j] = array[j + 1]; array[j + 1] = temporary; } } } } }

Chúng ta đã khai báo hàm sortNumbers chấp nhận biến như tham số. Hàm này bắt đầu bằng tính kích thước danh sách số chúng ta chỉ định.

Khi đã tính xong, vòng lặp for được khởi tạo. Vòng lặp này đi qua mọi mục trong mảng. Chúng ta khởi tạo vòng lặp for khác cho phép so sánh từng mục trong mảng.

Nếu mục bên trái danh sách lớn hơn số bên phải, các giá trị được hoán đổi. Ngược lại, không có gì xảy ra.

Chúng ta thực hiện hoán đổi bằng cách gán giá trị bên trái cho biến "temporary". Chúng ta gán giá trị bên phải giá trị đã ở bên trái của phép so sánh. Sau đó, giá trị bên trái được gán giá trị của biến temporary.

Nếu 6 và 5 đang được so sánh, chúng sẽ được hoán đổi. Vì vậy, danh sách sẽ xuất hiện như: 6, 5.

Chương trình chưa làm gì cả. Chúng ta chưa viết chương trình chính gọi hàm và cho nó danh sách để sắp xếp.

Thêm mã sau dưới hàm sortNumbers trong mã của bạn:

public static void main(String args[]) { int[] toSort = { 5, 9, 2, 7 }; BubbleSort sortingAlgorithm = new BubbleSort(); sortingAlgorithm.sortNumbers(toSort); System.out.println(Arrays.toString(toSort)); }

Chúng ta đã khai báo biến toSort lưu danh sách giá trị muốn sắp xếp. Chúng ta khởi tạo thể hiện của lớp BubbleSort tên sortingAlgorithm, dùng ở dòng mã tiếp theo để gọi hàm sortNumbers. Khi hàm này được gọi, danh sách được sắp xếp.

Cuối cùng, chúng ta dùng phương thức Arrays.toString() chuyển danh sách thành chuỗi để in ra console. Mã trả về:

[2, 5, 7, 9]

Giờ chúng ta đã có mảng đã sắp xếp!

Bubble Sort tối ưu

Có cách làm mã hiệu quả hơn. Lúc này, sắp xếp tiếp tục cho đến khi đã thực hiện tất cả so sánh có thể. Nghĩa là ngay cả khi mảng đã sắp xếp, sắp xếp vẫn tiếp tục cho đến khi so sánh hoàn tất.

Chúng ta có thể ngăn chặn hành vi này bằng cách thêm biến mới vào mã. Điều này cho phép dừng sắp xếp nếu danh sách đã được hoán đổi. Hãy thêm biến này vào hàm sortNumbers từ trước:

class BubbleSort { void sortNumbers(int array[]) { int size = array.length; for (int item = 0; item < size - 1; item++) { boolean hasSwapped = false; for (int j = 0; j < size - item - 1; j++) { if (array[j] > array[j + 1]) { int temporary = array[j]; array[j] = array[j + 1]; array[j + 1] = temporary; hasSwapped = true; } } if (hasSwapped == false) { break; } } } }

Chúng ta đã làm ba thay đổi. Bên trong vòng for đầu tiên chúng ta khai báo biến "hasSwapped". Biến này theo dõi xem có hoán đổi nào được thực hiện không. Mặc định, biến này đặt là "false". Nếu có hoán đổi, giá trị biến này đặt thành "true".

Ở cuối vòng for, chúng ta thêm câu lệnh if kiểm tra hasSwapped có bằng false không. Nếu không có hoán đổi nào, mảng đã được sắp xếp. Chúng ta dùng từ khóa "break" để dừng vòng lặp nếu hasSwapped bằng false.

Hãy chạy mã dùng chương trình chính viết trước và xem gì xảy ra:

[2, 5, 7, 9]

Danh sách đã được sắp xếp, nhưng lần này thuật toán hiệu quả hơn. Nếu dùng danh sách lớn hơn với nhiều giá trị hơn để sắp xếp, hiệu suất vượt trội của thuật toán này sẽ rõ ràng hơn. Xong, bạn đã viết bubble sort tối ưu trong Java!

Kết luận

Bubble sort dùng để sắp xếp danh sách theo thứ tự tăng dần hoặc giảm dần. Chúng hoạt động bằng cách so sánh các giá trị liền kề và hoán đổi nếu chúng ở thứ tự sai.

Có hai loại bubble sort: tiêu chuẩn và tối ưu. Bubble sort tiêu chuẩn thực hiện số lượng hoán đổi xác định trước trong khi bubble sort tối ưu chỉ tiếp tục sắp xếp cho đến khi danh sách được sắp xếp.

Bây giờ bạn đã sẵn sàng để viết bubble sort trong Java như chuyên gia!