Bubble sort - Sắp xếp nổi bọt
1. Giới thiệu
Sắp xếp nổi bọt là một thuật toán sắp xếp đơn giản, với thao tác cơ bản là so sánh hai phần tử kề nhau, nếu chúng chưa đứng đúng thứ tự thì đổi chỗ (swap). Có thể tiến hành từ trên xuống (bên trái sang) hoặc từ dưới lên (bên phải sang).
Sắp xếp nổi bọt còn có tên gọi khác là sắp xếp bằng so sánh trực tiếp. Nó sử dụng phép so sánh các phần tử nên là một giải thuật sắp xếp kiểu so sánh.
Sắp xếp từ trên xuống
Giả sử dãy cần sắp xếp có n phần tử. Khi tiến hành từ trên xuống, ta so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử thứ hai và thứ ba và tiếp tục cho đến cuối tập hợp dữ liệu, nghĩa là so sánh (và đổi chỗ nếu cần) phần tử thứ n-1 với phần tử thứ n. Sau bước này phần tử cuối cùng chính là phần tử lớn nhất của dãy.
Sau đó, quay lại so sánh (và đổi chố nếu cần) hai phần tử đầu cho đến khi gặp phần tử thứ n-2….
Ghi chú: Nếu trong một lần duyệt, không phải đổi chỗ bất cứ cặp phần tử nào thì danh sách đã được sắp xếp xong.
Sắp xếp từ dưới lên
Sắp xếp từ dưới lên so sánh (và đổi chỗ nếu cần) bắt đầu từ việc so sánh cặp phần tử thứ n-1 và n. Tiếp theo là so sánh cặp phần tử thứ n-2 và n-1,… cho đến khi so sánh và đổi chỗ cặp phần tử thứ nhất và thứ hai. Sau bước này phần tử nhỏ nhất đã được nổi lên vị trí trên cùng (nó giống như hình ảnh của các “bọt” khí nhẹ hơn được nổi lên trên). Tiếp theo tiến hành với các phần tử từ thứ 2 đến thứ n.
Độ phức tạp của giải thuật : O($n^2$)
2. Ý tưởng và mô tả thuật toán
Ví dụ ta có một mảng các số không theo thứ tự 5 1 4 2 8 thì Bubble Sort sẽ tiến hành việc sắp xếp ra sao. Hãy xem phần mô tả thô bên dưới.
Lần lặp đầu tiên:
(5 1 4 2 8) → (1 5 4 2 8) - thuật toán so sánh hai phần tử đầu tiên và hoán đổi vì 5 > 1.
(1 5 4 2 8) → (1 4 5 2 8) - hoán đổi vì 5 > 4.
(1 4 5 2 8) → (1 4 2 5 8) - hoán đổi vì 5 > 2.
(1 4 2 5 8) → (1 4 2 5 8) - vì các phần tử này đã có thứ tự (8 > 5), nên thuật toán không hoán đổi chúng.
Lần lặp thứ 2:
(1 4 2 5 8) → (1 4 2 5 8) – không hoán đổi.
(1 4 2 5 8) → (1 2 4 5 8) - hoán đổi vì 4 > 2.
(1 2 4 5 8) → (1 2 4 5 8) – không hoán đổi.
(1 2 4 5 8) → (1 2 4 5 8) – không hoán đổi.
Bây giờ, mảng đã được sắp xếp, nhưng thuật toán của chúng ta không biết liệu nó đã hoàn thành hay chưa. Thuật toán cần một lần chuyển toàn bộ mà không có bất kỳ sự hoán đổi nào để biết nó được sắp xếp.
Lần lặp thứ ba:
(1 2 4 5 8) → (1 2 4 5 8)
(1 2 4 5 8) → (1 2 4 5 8)
(1 2 4 5 8) → (1 2 4 5 8)
(1 2 4 5 8) → (1 2 4 5 8)
3. Code demo
Lấy lại ví dụ ở mục 2, chúng ta hãy cùng nhau triển khai ý tưởng đó thành code xem như thế nào nhé.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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);
}
}
Phần code bên trên (tức hàm bubbleSort) luôn chạy O($n^2$) thời gian 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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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);
}
}
Do tính đơn giản của nó, sắp xếp nổi bọt thường được sử dụng để giới thiệu khái niệm về thuật toán sắp xếp. Mặc dù là giải thuật khá chậm trong các thuật toán sắp xếp nhưng BubbleSort vẫn luôn có chỗ đứng trong việc giải quyết các vấn đề thực tế. Chẳng hạn như việc phát hiện một lỗi rất nhỏ (như hoán đổi chỉ hai phần tử) trong các mảng gần như được sắp xếp và sửa nó chỉ với độ phức tạp tuyến tính (2n) trong đồ hoạ máy tính.
Đây là thuật toán mở đầu cho phần chia sẻ của mình trong Series này. Hy vọng nó mang đến hứng thú và hữu ích với các bạn trong quá trình tìm hiểu về thuật toán, đặc biệt là với Java.
Bài viết mang tính chất “ghi chú, lưu trữ, chia sẻ và phi lợi nhuận”.
Nếu bạn thấy hữu ích, đừng quên chia sẻ với bạn bè và đồng nghiệp của mình nhé!
Happy coding! 😎 👍🏻 🚀 🔥