Sắp xếp bong bóng là một thuật toán sắp xếp so sánh hai phần tử liền kề và hoán đổi chúng cho đến khi chúng theo thứ tự dự định Giống như sự chuyển động của bong bóng khí trong nước nổi lên mặt nước, mỗi phần tử của mảng sẽ di chuyển đến cuối mỗi lần lặp. Do đó, nó được gọi là sắp xếp bong bóng
Hoạt động của Sắp xếp bong bóngGiả sử chúng ta đang cố sắp xếp các phần tử theo thứ tự tăng dần 1. Lần lặp đầu tiên (So sánh và Hoán đổi) - Bắt đầu từ chỉ mục đầu tiên, so sánh các yếu tố đầu tiên và thứ hai
- Nếu phần tử đầu tiên lớn hơn phần tử thứ hai, chúng được đổi chỗ
- Bây giờ, so sánh các yếu tố thứ hai và thứ ba. Trao đổi chúng nếu chúng không theo thứ tự
- Quá trình trên cứ tiếp tục cho đến phần tử cuối cùng. So sánh các phần tử liền kề
2. Vòng lặp còn lại Quá trình tương tự diễn ra cho các lần lặp còn lại Sau mỗi lần lặp, phần tử lớn nhất trong số các phần tử chưa sắp xếp được đặt ở cuối Đặt phần tử lớn nhất ở cuốiTrong mỗi lần lặp, việc so sánh diễn ra cho đến phần tử chưa sắp xếp cuối cùng So sánh các phần tử liền kềMảng được sắp xếp khi tất cả các phần tử chưa sắp xếp được đặt vào đúng vị trí của chúng Mảng được sắp xếp nếu tất cả các phần tử được giữ đúng thứ tự
Thuật toán sắp xếp bong bóngbubbleSort(array)
for i <- 1 to indexOfLastUnsortedElement-1
if leftElement > rightElement
swap leftElement and rightElement
end bubbleSort
Mã sắp xếp bong bóng trong Python, Java và C/C++# Bubble sort in Python
def bubbleSort(array):
# loop to access each array element
for i in range(len(array)):
# loop to compare array elements
for j in range(0, len(array) - i - 1):
# compare two adjacent elements
# change > to < to sort in descending order
if array[j] > array[j + 1]:
# swapping elements if elements
# are not in the intended order
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
data = [-2, 45, 0, 11, -9]
bubbleSort(data)
print('Sorted Array in Ascending Order:')
print(data)
// Bubble sort in Java
import java.util.Arrays;
class Main {
// perform the bubble sort
static void bubbleSort(int array[]) {
int size = array.length;
// loop to access each array element
for (int i = 0; i < size - 1; i++)
// loop to compare array elements
for (int j = 0; j < size - i - 1; j++)
// compare two adjacent elements
// change > to < to sort in descending order
if (array[j] > array[j + 1]) {
// swapping occurs if elements
// are not in the intended order
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
public static void main(String args[]) {
int[] data = { -2, 45, 0, 11, -9 };
// call method using class name
Main.bubbleSort(data);
System.out.println("Sorted Array in Ascending Order:");
System.out.println(Arrays.toString(data));
}
}
// Bubble sort in C
#include
// perform the bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < size - 1; ++step) {
// loop to compare array elements
for (int i = 0; i < size - step - 1; ++i) {
// compare two adjacent elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping occurs if elements
// are not in the intended order
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}
// print array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
int main() {
int data[] = {-2, 45, 0, 11, -9};
// find the array's length
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
printf("Sorted Array in Ascending Order:\n");
printArray(data, size);
}
// Bubble sort in C++
#include
using namespace std;
// perform bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < size; ++step) {
// loop to compare array elements
for (int i = 0; i < size - step; ++i) {
// compare two adjacent elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping elements if elements
// are not in the intended order
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}
// print array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
cout << " " << array[i];
}
cout << "\n";
}
int main() {
int data[] = {-2, 45, 0, 11, -9};
// find array's length
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
cout << "Sorted Array in Ascending Order:\n";
printArray(data, size);
}
Thuật toán sắp xếp bong bóng được tối ưu hóaTrong thuật toán trên, tất cả các so sánh được thực hiện ngay cả khi mảng đã được sắp xếp Điều này làm tăng thời gian thực hiện Để giải quyết vấn đề này, chúng ta có thể giới thiệu một biến bổ sung được hoán đổi. Giá trị của hoán đổi được đặt thành true nếu xảy ra hoán đổi các phần tử. Mặt khác, nó được đặt sai Sau một lần lặp, nếu không có hoán đổi, giá trị của hoán đổi sẽ là sai. Điều này có nghĩa là các phần tử đã được sắp xếp và không cần thực hiện thêm bước lặp nào nữa
Len() có thể được sử dụng cho danh sách Python không?
Hàm len() là một trong những hàm có sẵn của Python. Nó trả về chiều dài của một đối tượng. Ví dụ: nó có thể trả về số lượng mục trong danh sách . Bạn có thể sử dụng hàm với nhiều kiểu dữ liệu khác nhau.
Danh sách () trong Python là gì?
Hàm list() tạo đối tượng danh sách . Một đối tượng danh sách là một bộ sưu tập được sắp xếp và thay đổi. Đọc thêm về danh sách trong chương. Danh sách Python. |