Bạn đã hiểu về ý tưởng của thuật toán Bubble sort. Bây giờ, chúng ta hãy cùng nhau triển khai ý tưởng đó thành code xem như thế nào nhé.
package bubble.sort.algo;
public class BubbleSort {
// Hàm sắp xếp nổi bọt
void bubbleSort(int arr[]) {
int n = arr.length;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) {
// swap arr[j+1] và arr[i]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// In các phần tử của arr
void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[]) {
BubbleSort ob = new BubbleSort();
int arr[] = { 5, 1, 4, 2, 8 };
System.out.println("Mảng ban đầu:");
ob.printArray(arr);
ob.bubbleSort(arr);
System.out.println("Mảng sau khi sắp xếp:");
ob.printArray(arr);
}
}
Khi chạy chương trình ta có:
Mảng ban đầu:
5, 1, 4, 2, 8
Mảng sau khi sắp xếp:
1, 2 , 4, 5, 8
Phần code bên trên (tức hàm bubbleSort) luôn chạy với thời gian là O(n^2) ngay cả khi mảng được sắp xếp.
Nó có thể được tối ưu hóa bằng cách dừng thuật toán nếu vòng lặp bên trong mà không gây ra bất kỳ sự hoán đổi nào.
package bubble.sort.algo;
public class BubbleSortOptimized {
static void bubbleSort(int arr[], int n) {
int i, j, temp;
boolean swapped;
for (i = 0; i < n - 1; i++) {
swapped = false;
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// swap arr[j] và arr[j+1]
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// Nếu không có phần tử nào để hoán đổi
// bên trong vòng lặp thì Break
if (swapped == false)
break;
}
}
// In các phần tử của mảng
static void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[]) {
int arr[] = { 5, 1, 4, 2, 8 };
int n = arr.length;
System.out.println("Mảng ban đầu:");
printArray(arr, n);
bubbleSort(arr, n);
System.out.println("Mảng sau khi sắp xếp:");
printArray(arr, n);
}
}