Sắp xếp nối bọt trong Java - Tìm hiểu về Bubble Sort trong Java
29/09/2021 01:41
Trong lập trình Java, Sorting nhìn chung là việc sắp xếp một mảng cụ thể hoặc tập hợp các phần tử thành một chuỗi cụ thể, tức là theo thứ tự tăng dần hoặc theo thứ tự giảm dần. Có nhiều loại kỹ thuật Sorting để sắp xếp một mảng số đã cho. Trong bài viết này, chúng ta sẽ học kỹ thuật sắp xếp nối bọt trong Java - Bubble Sort trong Java.
Đây là một trong những kỹ thuật sử dụng nhiều nhất trong Sorting. Chúng ta sẽ cùng tìm hiểu cách nó hoạt động và thực thi nó trong Java để sắp xếp mảng theo cả thứ tự tăng dần và giảm dần. Giờ thì không lãng phí thêm thời gian nữa, cùng tìm hiểu ngay về Bubble Sort - nối bọt trong Java thôi!
Nối bọt trong Java là gì?
Bubble Sort là một trong những kỹ thuật sắp xếp đơn giản nhất trong Java để sắp xếp các phần tử của mảng. Ý tưởng là đi qua phần tử bắt đầu đến phần tử cuối cùng 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 không theo thứ tự cụ thể. Nó được gọi là nối bọt vì, vào cuối mỗi lần lặp, số lớn nhất nằm ở dưới cùng của mảng giống như bọt nặng nhất lắng xuống trong một chiếc bình. Việc hoán đổi các phần tử tiếp tục cho đến khi mảng được sắp xếp và không cần hoán đổi nữa. Chúng ta cũng có thể sắp xếp các phần tử theo thứ tự giảm dần, trong đó phần tử nhỏ nhất sẽ ở cuối mảng trong mỗi lần lặp. Điều này chỉ có thể xảy ra nếu chúng ta nghịch đảo trọng lượng của phần tử.
Một số điểm quan trọng về Nối bọt là:
- Độ phức tạp của trường hợp tệ nhất và trung bình của Nối bọt là O (n2), trong đó n biểu thị tổng số phần tử trong mảng.
- Các không gian phụ trợ được tiêu thụ bởi các thuật toán nối bọt là O (1)
- Các loại Bubble là một loại in Place Sorting.
- Nối bóng là một thuật toán ổn định .
>>> Đọc thêm: Cấu trúc dữ liệu trong Java - Bạn đã hiểu hết về cấu trúc dữ liệu?
Làm việc với Nối bọt trong Java
Giờ chúng ta sẽ tìm hiểu cách Nối bọt trong Java hoạt động với các mảng đã cho. Chúng ta có một mảng và để sắp xếp nó, có bốn lần lặp sau đó chúng ta sẽ nhận một mảng đã được sắp xếp. Sơ đồ sau minh họa hoạt động Nối Bọt:
Chương trình nối bọt trong Java để sắp xếp một mảng nhất định theo thứ tự tăng dần
package com.techvidvan.bubblesort;
public class BubbleSortDemo {
static void bubbleAscending(int[] myarray) {
int n = myarray.length;
int temp = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < (n - i); j++) {
if (myarray[j - 1] > myarray[j]) {
//Code to swap the elements
temp = myarray[j - 1];
myarray[j - 1] = myarray[j];
myarray[j] = temp;
}
}
}
}
public static void main(String[] args) {
int myarray[] = {
4,
15,
12,
21,
2,
25,
10,
18
};
System.out.println("Array on which we apply Bubble Sort: ");
for (int i = 0; i < myarray.length; i++) {
System.out.print(myarray[i] + " ");
}
System.out.println();
bubbleAscending(myarray); //Applying Bubble sort to sort the Array
System.out.println("Array after applying Bubble Sort: ");
for (int i = 0; i < myarray.length; i++) {
System.out.print(myarray[i] + " ");
}
}
}
Output:
Array on which we apply Bubble Sort: 4, 15, 12, 21, 2, 25, 10, 18
Array after applying Bubble Sort: 2, 4, 10, 12, 15, 18, 21, 25>>> Đọc thêm: Từ khóa Synchronized trong Java -Cú pháp và ví dụ trong Java
Ví dụ Nối bóng trong Java để sắp xếp mảng nhất định theo thứ tự giảm dần
package com.techvidvan.bubblesort;
public class BubbleSortDemo {
static void bubbleDescending(int[] myarray) {
int n = myarray.length;
int temp = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < (n - i); j++) {
if (myarray[j - 1] < myarray[j]) {
//Code to swap the elements
temp = myarray[j - 1];
myarray[j - 1] = myarray[j];
myarray[j] = temp;
}
}
}
}
public static void main(String[] args) {
int myarray[] = {
4,
15,
12,
21,
2,
25,
10,
18
};
System.out.println("Array on which we apply Bubble Sort: ");
for (int i = 0; i < myarray.length; i++) {
System.out.print(myarray[i] + " ");
}
System.out.println();
bubbleDescending(myarray); //Applying Bubble sort to sort the Array
System.out.println("Array after applying Bubble Sort: ");
for (int i = 0; i < myarray.length; i++) {
System.out.print(myarray[i] + " ");
}
}
}
Output:
Array on which we apply Bubble Sort: 4, 15, 12, 21, 2, 25, 10, 18
Array after applying Bubble Sort: 25, 21, 18, 15, 12, 10, 4, 2>>> Tham khảo: Khóa học lập trình Java
Lợi ích của Nối bọt trong Java
Ưu điểm của sắp xếp bong bóng là:
- Nó rất đơn giản để viết và dễ hiểu
- Nó chỉ mất một vài dòng mã
- Sắp xếp bong bóng là một kỹ thuật sắp xếp tại chỗ, do đó dữ liệu nằm trong bộ nhớ và do đó sẽ có chi phí bộ nhớ tối thiểu.
Nhược điểm của Java Bubble Sort
Cũng có một số nhược điểm của sắp xếp bong bóng là:
- Cần nhiều thời gian hơn để sắp xếp các phần tử mảng.
- Độ phức tạp thời gian trung bình tăng lên khi số lượng phần tử của mảng tăng lên.
Kết luận:
Trong bài viết này, chúng ta đã nghiên cứu Bubble Sort trong Java là gì và cách sử dụng nó để sắp xếp các phần tử mảng theo một thứ tự cụ thể. Nó rất dễ hiểu. Nhưng chúng ta có thể kết luận rằng nó hoạt động tốt nhất với các mảng nhỏ và hiệu suất của nó giảm khi số lượng phần tử mảng tăng lên. Chúng ta cũng đã tìm hiểu cách sắp xếp một mảng theo thứ tự tăng dần cũng như giảm dần với sự trợ giúp của chương trình Java. Bài viết này chắc chắn sẽ giúp bạn trở thành một bậc thầy trong kỹ thuật Nối bọt trong Java. Tìm hiểu thêm về Java và các ngôn ngữ lập trình khác qua các khóa học lập trình tại Viện công nghệ thông tin T3H.
