Sắp xếp bong bóng là một loại thuật toán sắp xếp mà bạn có thể sử dụng để sắp xếp một tập hợp các giá trị theo thứ tự tăng dần. Nếu muốn, bạn cũng có thể triển khai sắp xếp bong bóng để sắp xếp các giá trị theo thứ tự giảm dần.
Một ví dụ thực tế về thuật toán sắp xếp bong bóng là cách danh sách liên hệ trên điện thoại của bạn được sắp xếp theo thứ tự bảng chữ cái. Hoặc việc sắp xếp các tệp trên điện thoại của bạn theo thời gian chúng được thêm vào.
Trong bài viết này, tôi sẽ giải thích tất cả những gì bạn cần biết về thuật toán sắp xếp bong bóng bằng một số đồ họa thông tin mà tôi đã chuẩn bị. Sau đó, tôi sẽ chỉ cho bạn mã ví dụ về thuật toán sắp xếp bong bóng trong Python, Java và C++.
Mục lục
Cách thuật toán sắp xếp bong bóng hoạt động
Để triển khai thuật toán sắp xếp bong bóng, các nhà phát triển thường viết một hàm, sau đó viết một vòng lặp trong một vòng lặp – vòng lặp bên trong và vòng lặp bên ngoài. Bạn sẽ thấy nó hoạt động khi tôi chỉ cho bạn mã bằng Python, C++ và Java.
Giả sử chúng ta muốn sắp xếp một dãy số 5, 3, 4, 1 và 2 sao cho chúng được sắp xếp theo thứ tự tăng dần…
Việc sắp xếp bắt đầu lần lặp đầu tiên bằng cách so sánh hai giá trị đầu tiên. Nếu giá trị đầu tiên lớn hơn giá trị thứ hai, thuật toán sẽ đẩy giá trị đầu tiên vào chỉ mục của giá trị thứ hai.
Lần lặp đầu tiên của Sắp xếp
Bước 1: Trong trường hợp 5, 3, 4, 1 và 2, 5 lớn hơn 3. Vì vậy, 5 chiếm vị trí của 3 và các số trở thành 3, 5, 4, 1 và 2.
Bước 2: Thuật toán hiện có 3, 5, 4, 1 và 2 để so sánh, lần này, nó so sánh hai giá trị tiếp theo là 5 và 4. 5 lớn hơn 4, vì vậy 5 lấy chỉ số của 4 và các giá trị bây giờ trở thành 3, 4, 5, 1 và 2.
Bước 3: Thuật toán hiện có 3, 4, 5, 1 và 2 để so sánh. Nó so sánh hai giá trị tiếp theo là 5 và 1. 5 lớn hơn 1, vì vậy 5 lấy chỉ số của 1 và các số trở thành 3, 4, 1, 5 và 2.
Bước 4: Thuật toán hiện có 3, 4, 1, 5 và 2 để so sánh. Nó so sánh hai giá trị tiếp theo là 5 và 2. 5 lớn hơn 2, vì vậy 5 lấy chỉ số của 2 và các số trở thành 3, 4, 1, 2 và 5.
Đó là lần lặp đầu tiên. Và các số hiện được sắp xếp thành 3, 4, 1, 2 và 5 – từ 5, 3, 4, 1 và 2 ban đầu. Như bạn có thể nhận ra, 5 sẽ là số cuối cùng nếu các số được sắp xếp tăng dần trật tự. Điều này có nghĩa là lần lặp đầu tiên đã thực sự hoàn thành.
Lần lặp lại thứ hai của Sắp xếp và phần còn lại
Thuật toán bắt đầu lần lặp thứ hai với kết quả cuối cùng là 3, 4, 1, 2 và 5. Lần này, 3 nhỏ hơn 4 nên không xảy ra hoán đổi. Điều này có nghĩa là các con số sẽ vẫn giữ nguyên.
Thuật toán tiến hành so sánh 4 và 1. 4 lớn hơn 1, vì vậy 4 được đổi chỗ cho 1 và các số trở thành 3, 1, 4, 2 và 5.
Bây giờ thuật toán tiến hành so sánh 4 và 2. 4 lớn hơn 2, vì vậy 4 được đổi chỗ cho 2 và các số trở thành 3, 1, 2, 4 và 5.
4 hiện ở đúng vị trí, vì vậy không xảy ra hoán đổi giữa 4 và 5 vì 4 nhỏ hơn 5.
Đó là cách thuật toán tiếp tục so sánh các số cho đến khi chúng được sắp xếp theo thứ tự tăng dần là 1, 2, 3, 4 và 5.
Mã Python Ví dụ về thuật toán sắp xếp bong bóng
Đây là một ví dụ mã cho thấy việc triển khai thuật toán sắp xếp bong bóng trong Python:
def bubble_sort(arr):
arr_len = len(arr)
for i in range(arr_len-1):
flag = 0
for j in range(0, arr_len-i-1):
if arr[j] > arr[j+1]:
arr[j+1], arr[j] = arr[j], arr[j+1]
flag = 1
if flag == 0:
break
return arr
arr = [5, 3, 4, 1, 2]
print("List sorted with bubble sort in ascending order: ", bubble_sort(arr))
# Output: List sorted with bubble sort in ascending order: [1, 2, 3, 4, 5]
Để sắp xếp xuất hiện theo thứ tự giảm dần, chỉ cần thay thế ký hiệu lớn hơn (>) bằng ký hiệu nhỏ hơn (<):
def bubble_sort(arr):
arr_len = len(arr)
for i in range(arr_len-1):
flag = 0
for j in range(0, arr_len-i-1):
if arr[j] < arr[j+1]:
arr[j+1], arr[j] = arr[j], arr[j+1]
flag = 1
if flag == 0:
break
return arr
arr = [5, 3, 4, 1, 2]
print("List sorted with bubble sort in descending order: ", bubble_sort(arr))
# Output: List sorted with bubble sort in descending order: [5, 4, 3, 2, 1]
Đây là phiên bản mã mà tôi đã thêm nhận xét để bạn có thể biết chuyện gì đang xảy ra:
# Define a function to create the sorting and pass in an array as the parameter
def bubble_sort(arr):
# Get the length of the array
arr_len = len(arr)
# Loop through the array to access the elements in it, including the last one - outer loop
for i in range(arr_len-1):
# declare a flag variable to check if a swap has occured - for optimization
flag = 0
# create a loop to compare each element of the array till the last one
for j in range(0, arr_len-i-1):
# compare 2 adjacent elements and sort them in ascending order
if arr[j] > arr[j+1]:
# Swap the elements if they are not in the right order
arr[j+1], arr[j] = arr[j], arr[j+1]
flag = 1
# break out of the loop at 0
if flag == 0:
break
# return value must be in the outer loop block
return arr
arr = [5, 3, 4, 1, 2]
print("List sorted with bubble sort in ascending order: ", bubble_sort(arr))
# Output: List sorted with bubble sort in ascending order: [1, 2, 3, 4, 5]
Ví dụ mã Java về thuật toán sắp xếp bong bóng
Để triển khai thuật toán sắp xếp bong bóng trong Java, bạn phải viết nhiều mã hơn so với Python.
Đó là lý do tại sao tôi đã thêm nhận xét để cho bạn biết về các bước khi chúng được thực hiện:
import java.util.Arrays;
class Main {
static void bubbleSort(int array[]) {
int size = array.length;
// loop over each element of the array to access them
for (int i = 0; i < size - 1; i++)
// compare the elements of the array with a loop
for (int j = 0; j < size - i - 1; j++)
// compare two adjacent elements in the array
if (array[j] > array[j + 1]) {
// Swap if the elements aren't in the right order
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
public static void main(String args[]) {
int[] data = { 5, 3, 4, 1, 2 };
// call the method using class name
Main.bubbleSort(data);
System.out.println("Array sorted with bubble sort: ");
System.out.println(Arrays.toString(data));
}
}
// Output: Array sorted with bubble sort: [1, 2, 3, 4, 5]
Mã C++ Ví dụ về thuật toán sắp xếp bong bóng
Giống như tôi đã làm với Java, tôi cũng đã thêm nhận xét vào việc triển khai thuật toán sắp xếp bong bóng trong C++ vì nó dài dòng hơn so với Python và Java:
#include <iostream>
using namespace std;
// create a function to execute bubble sort
void bubble_sort(int array[], int size) {
// loop over each element of the array to access them - outer loop
for (int step = 0; step < (size-1); ++step) {
// check if swapping occurs
int swapped = 0;
// loop over each element of the array to compare them - inner loop
for (int i = 0; i < (size-step-1); ++i) {
// compare 2 adjacent elements and sort them in ascending order
if (array[i] > array[i + 1]) {
//Swap the elements if they are not in the right order
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swapped = 1;
}
}
// break out of the loop if no swapping occurs anymore
if (swapped == 0)
break;
}
}
// print an array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
cout << " " << array[i];
}
cout << "\n";
}
int main() {
int data[] = {5, 3, 4, 1, 2};
// find the length of the array
int size = sizeof(data) / sizeof(data[0]);
// call the function
bubble_sort(data, size);
cout << "Array sorted with bubble sort: \n";
printArray(data, size);
}
// Output: Array sorted with bubble sort: 1 2 3 4 5
Suy nghĩ cuối cùng
Tôi sẽ không nói việc triển khai thuật toán sắp xếp bong bóng là đơn giản hay khó khăn. Đối với một lập trình viên có kinh nghiệm, điều đó không khó, nhưng đối với người mới bắt đầu, nó có thể đáng sợ lúc đầu.
Tuy nhiên, để thực sự hiểu cách thức hoạt động của thuật toán, bạn cần biết rằng:
- bạn cần viết một hàm để truyền dữ liệu [or array] vào trong
- bạn cần viết một vòng lặp bên ngoài để truy cập các phần tử
- bạn cần viết một vòng lặp bên trong để so sánh các phần tử
- bạn cần gọi hàm và truyền vào dữ liệu (mảng)
Tôi hy vọng bài viết này giúp bạn hiểu thuật toán sắp xếp bong bóng và cách thực hiện nó.
Cảm ơn bạn đã đọc.
