Cách viết Java Bubble Sort
Khi các nhà lập trình nói về các loại bong bóng, họ không nói về những bong bóng nước mà bạn có thể đã thổi vào một thời điểm nào đó trong đời. Họ đang nói về một thuật toán sắp xếp được sử dụng để sắp xếp một danh sách các mặt hàng.
Trong hướng dẫn này, chúng ta sẽ nói về các loại bong bóng và cách chúng hoạt động. Chúng tôi sẽ tiếp tục triển khai sắp xếp bong bóng bằng Java để bạn có thể hiểu cách thuật toán này chuyển sang mã. Không cần thêm lời khuyên nào nữa, hãy đi sâu vào các loại bong bóng Java!
Java Bubble Sort là gì?
Sắp xếp bong bóng là một thuật toán sắp xếp các 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 không đúng thứ tự.
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 thứ tự. Sắp xếp bong bóng có thể được sử dụng để sắp xếp danh sách theo thứ tự tăng dần hoặc giảm dần.
Sắp xếp bong bóng là kiểu đầu tiên được dạy trong các lớp thuật toán. Điều này là do chúng dễ hiểu hơn các loại khác, như sắp xếp chèn hoặc sắp xếp lựa chọn và cung cấp giới thiệu tốt về các thuật toán sắp xếp.
Sắp xếp bong bóng hiệu quả nhất khi dữ liệu đã được sắp xếp gần hết. Tuy nhiên, nếu dữ liệu của bạn hoàn toàn không được sắp xếp, thì một kiểu sắp xếp khác có thể hiệu quả hơn.
Cách sắp xếp bong bóng hoạt động?
Trước khi bắt đầu viết mã cho sắp xếp bong bóng Java, trước tiên chúng ta phải hiểu cách thực hiện thuật toán này trong thực tế.
Hãy xem xét danh sách sau:
81% người tham gia cho biết họ cảm thấy tự tin hơn về triển vọng công việc công nghệ của mình sau khi tham gia một cuộc thi đào tạo. Kết hợp với bootcamp ngay hôm nay.
Sinh viên tốt nghiệp bootcamp trung bình đã dành ít hơn sáu tháng để chuyển đổi nghề nghiệp, từ khi bắt đầu bootcamp đến khi tìm được công việc đầu tiên của họ.
| 5 | 9 | 2 | 7 |
Sắp xếp bong bóng của chúng tôi bắt đầu bằng cách so sánh phần tử đầu tiên và phần tử thứ hai trong danh sách của chúng tôi.
Nếu phần tử đầu tiên lớn hơn phần tử thứ hai, các phần tử này hoán đổi vị trí cho nhau. Trong trường hợp này, 5 không lớn hơn 9, vì vậy các phần tử vẫn ở cùng vị trí của chúng.
Sau đó, sắp xếp của chúng tôi sẽ so sánh hai mục tiếp theo trong danh sách của chúng tôi. 9 lớn hơn 2, và do đó hai số này hoán đổi với nhau:
| 5 | 2 | 9 | 7 |
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ó một phép so sánh nữa cần thực hiện:9 có lớn hơn 7 không? 9 lớn hơn 7, vì vậy những con số này hoán đổi:
| 5 | 2 | 7 | 9 |
Danh sách của chúng tôi gần như được đặt hàng. Khi mọi mục đã được so sánh, sắp xếp bong bóng 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 và do đó các số này hoán đổi với nhau.
| 2 | 5 | 7 | 9 |
Danh sách của chúng tôi bây giờ đã được sắp xếp chính xác. Sắp xếp bong bóng của chúng tôi sẽ tiếp tục so sánh các số cho đến khi nó đi đến cuối danh sách và sau đó nó sẽ dừng lại. Đó là tất cả những gì liên quan đến phân loại bong bóng. Đó chắc chắn là một thuật toán dễ sử dụng khi bạn hiểu rõ.
Cách viết Java Bubble Sort
Biết lý thuyết là một chuyện nhưng bạn đến đây để tìm hiểu về các loại bong bóng Java. Tốt nhất chúng ta nên thảo luận về cách triển khai sắp xếp bong bóng trong Java.
Có hai kiểu sắp xếp bong bóng:
- Sắp xếp bong bóng tiêu chuẩn
- Sắp xếp bong bóng được tối ưu hóa
Sắp xếp bong bóng tiêu chuẩn thực hiện tất cả các so sánh có thể có ngay cả khi một mảng được sắp xếp. Điều này làm tăng thời gian để sắp xếp bong bóng thực thi. Điều này làm cho việc sắp xếp kém hiệu quả hơn.
Sắp xếp bong bóng được tối ưu hóa theo dõi xem danh sách có được sắp xếp hay không bằng cách sử dụng một biến bổ sung. Điều này cho phép chúng tôi dừng việc sắp xếp của mình ngay khi danh sách của chúng tôi đã được sắp xếp.
Hãy bắt đầu bằng cách viết sắp xếp bong bóng tiêu chuẩn.
Sắp xếp bong bóng tiêu chuẩn
Để bắt đầu, chúng tôi sẽ nhập thư viện Mảng vào mã của chúng tôi. Chúng tôi sẽ sử dụng điều này sau trong mã của mình để in ra danh sách các số được sắp xếp của chúng tôi vào bảng điều khiển:
import java.util.Arrays;
Bây giờ không còn cách nào khác, chúng ta có thể bắt đầu viết thuật toán của mình.
Chúng ta sẽ bắt đầu bằng cách xác định một lớp được gọi là BubbleSort lưu trữ mã cho chương trình Java của chúng ta và một hàm thực hiện việc sắp xếp của chúng ta:
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 tôi đã khai báo một hàm có tên là sortNumbers chấp nhận một biến làm tham số. Hàm này bắt đầu bằng cách tính toán kích thước của danh sách các số mà chúng tôi chỉ định.
Khi điều này đã được tính toán, một 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 của chúng tôi. Chúng tôi khởi tạo một vòng lặp for khác cho phép chúng tôi so sánh từng mục trong mảng.
Nếu mục ở bên trái của danh sách lớn hơn số ở bên phải, các giá trị sẽ được hoán đổi. Nếu không, không có gì xảy ra.
Chúng tôi thực hiện hoán đổi này bằng cách gán giá trị ở bên trái cho một biến được gọi là "tạm thời". Chúng tôi gán giá trị ở bên phải cho 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 tạm thời.
Nếu 6 và 5 được so sánh, chúng sẽ được hoán đổi. Vì vậy, danh sách của chúng tôi sẽ xuất hiện dưới dạng:6, 5.
Chương trình của chúng tôi chưa thực hiện được bất cứ điều gì. Chúng tôi đã không viết một chương trình chính gọi hàm của chúng tôi và cung cấp cho nó một danh sách để sắp xếp.
Thêm mã sau vào bên dưới sortNumbers chức năng 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 tôi đã khai báo một biến có tên là toSort để lưu trữ danh sách các giá trị mà chúng tôi muốn sắp xếp. Sau đó, chúng tôi đã khai báo một phiên bản của lớp BubbleSort có tên là sortingAlgorithm, mà chúng tôi sử dụng trên dòng mã tiếp theo để gọi sortNumbers chức năng. Khi hàm này được gọi, danh sách của chúng ta sẽ được sắp xếp.
Cuối cùng, chúng tôi sử dụng Arrays.toString() để chuyển đổi danh sách của chúng tôi thành một chuỗi để chúng tôi có thể in nó ra bảng điều khiển. Mã của chúng tôi trả về:
[2, 5, 7, 9]
Bây giờ chúng ta có một mảng được sắp xếp!
Sắp xếp bong bóng được tối ưu hóa
Có một cách để làm cho mã của chúng tôi hiệu quả hơn. Ngay bây giờ, việc sắp xếp của chúng tôi vẫn tiếp tục cho đến khi thực hiện được tất cả các phép so sánh có thể. Điều này có nghĩa là ngay cả khi mảng của chúng ta được sắp xếp, thì việc sắp xếp sẽ tiếp tục cho đến khi các phép so sánh đó hoàn tất.
Chúng tôi có thể ngăn chặn hành vi này bằng cách thêm một biến mới vào mã của chúng tôi. Điều này sẽ cho phép chúng tôi dừng việc sắp xếp của mình nếu danh sách được hoán đổi. Hãy thêm biến này vào sortNumbers của chúng tôi chức năng 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 tôi đã thực hiện ba thay đổi đối với mã của mình. Bên trong vòng lặp for đầu tiên của chúng tôi, chúng tôi đã khai báo một biến có tên là “hasSwapped”. Biến này theo dõi liệu một giao dịch hoán đổi đã được thực hiện hay chưa. Theo mặc định, biến này được đặt thành "false". Nếu hoán đổi được thực hiện, giá trị của biến này được đặt thành “true”.
Ở cuối vòng lặp for, chúng tôi đã thêm câu lệnh if để kiểm tra xem hasSwapped có bằng false hay không. Nếu không có hoán đổi nào được thực hiện, mảng sẽ được sắp xếp. Chúng tôi sử dụng từ khóa "break" để ngăn vòng lặp của chúng tôi thực thi nếu hasSwapped bằng false.
Hãy chạy mã của chúng tôi bằng cách sử dụng chương trình chính mà chúng tôi đã viết trước đó và xem điều gì sẽ xảy ra:
[2, 5, 7, 9]
Danh sách của chúng tôi đã được sắp xếp, nhưng lần này thuật toán của chúng tôi hiệu quả hơn. Nếu chúng tôi sử dụng một danh sách lớn hơn với nhiều giá trị hơn để sắp xếp, thì hiệu suất vượt trội của thuật toán này sẽ rõ ràng hơn. Vậy là xong, bạn đã viết một sắp xếp bong bóng được tối ưu hóa bằng Java!
Kết luận
Sắp xếp bong bóng được sử 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 chúng nếu chúng không đúng thứ tự.
Có hai loại sắp xếp bong bóng:tiêu chuẩn và tối ưu hóa. Các loại bong bóng tiêu chuẩn thực hiện một số lượng hoán đổi được xác định trước trong khi các loại bong bóng được tối ưu hóa chỉ tiếp tục sắp xếp cho đến khi một danh sách được sắp xếp.
Bây giờ, bạn đã sẵn sàng để bắt đầu viết các loại bong bóng bằng Java như một chuyên gia!