Trong hướng dẫn này, bạn sẽ học cách sắp xếp bong bóng hoạt động. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc về sắp xếp bong bóng trong C, C ++, Java và Python.
Sắp xếp bong bóng là một thuật toán so sánh các phần tử liền kề và hoán đổi vị trí của chúng nếu chúng không theo thứ tự đã định. Thứ tự có thể tăng dần hoặc giảm dần.
Cách sắp xếp bong bóng hoạt động?
- Bắt đầu từ chỉ mục đầu tiên, hãy so sánh phần tử đầu tiên và phần tử thứ hai. Nếu phần tử đầu tiên lớn hơn phần tử thứ hai, chúng sẽ được hoán đổi.
Bây giờ, hãy so sánh 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 yếu tố liền kề - 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 được sắp xếp được đặt ở cuối.
Trong mỗi lần lặp, so sánh diễn ra cho đến phần tử chưa được sắp xếp cuối cùng.
Mảng được sắp xếp khi tất cả các phần tử chưa được sắp xếp được đặt đúng vị trí của chúng.
So sánh các phần tử liền kề 
So sánh các phần tử liền kề 
So sánh các phần tử liền kề
Thuật toán sắp xếp bong bóng
bubbleSort (mảng) cho tôi bên phải Trao đổi bổ sung leftElement và rightElement end bubbleSort
Ví dụ về Python, Java và C / C ++
Python Java C C ++ # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data)
// Bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j to array(j + 1)) ( // swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )
// Bubble sort in C #include void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i " to " array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printArray(data, size); )
// Bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i to array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )
Sắp xếp bong bóng được tối ưu hóa
Trong đoạn mã trên, tất cả các so sánh có thể được thực hiện ngay cả khi mảng đã được sắp xếp. Nó làm tăng thời gian thực hiện.
Mã có thể được tối ưu hóa bằng cách giới thiệu một biến bổ sung được hoán đổi. Sau mỗi lần lặp, nếu không có sự hoán đổi nào diễn ra thì không cần thực hiện các vòng lặp khác.
Trong trường hợp này, biến được hoán đổi được đặt là false. Do đó, chúng ta có thể ngăn chặn sự lặp lại tiếp theo.
Thuật toán để sắp xếp bong bóng được tối ưu hóa là
bubbleSort (mảng) được hoán đổi <- false cho tôi phảiElement hoán đổi tráiElement và phảiElement hoán đổi <- true end bubbleSort
Ví dụ về sắp xếp bong bóng được tối ưu hóa
Python Java C C + # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # Swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if swapped: break data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)
// Optimized bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) ( // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j to array(j + 1)) ( // Swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; swapped = false; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; ) ) // Driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )
// Optimized bubble sort in C #include void bubbleSort(int arrayay(), int size) ( for (int step = 0; step < size - 1; ++step) ( // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i to arrayay(i + 1)) ( // Swap if greater is at the rear position int temp = arrayay(i); arrayay(i) = arrayay(i + 1); arrayay(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printarrayay(int arrayay(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", arrayay(i)); ) printf(""); ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printarrayay(data, size); )
// Optimized bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( for (int step = 0; step < size - 1; ++step) (
// Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i to array(i + 1)) ( // Swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )
Phức tạp
Bubble Sort là một trong những thuật toán sắp xếp đơn giản nhất. Hai vòng lặp được thực hiện trong thuật toán.
| Đi xe đạp | Số lượng so sánh |
|---|---|
| Ngày 1 | (n-1) |
| lần 2 | (n-2) |
| lần thứ 3 | (n-3) |
| …. | … |
| Cuối cùng | 1 |
Số phép so sánh: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 gần bằng n 2
Độ phức tạp: O (n 2 )
Ngoài ra, chúng ta có thể phân tích độ phức tạp bằng cách quan sát số vòng lặp. Có 2 vòng lặp nên độ phức tạp làn*n = n2
Thời gian phức tạp:
-
Trường hợp xấu nhất Độ phức tạp: Nếu chúng ta muốn sắp xếp theo thứ tự tăng dần và mảng theo thứ tự giảm dần thì trường hợp xấu nhất sẽ xảy ra.
O(n2) -
Độ phức tạp của trường hợp tốt nhất:
O(n)
Nếu mảng đã được sắp xếp, thì không cần sắp xếp. -
Độ phức tạp trường hợp trung bình: Nó xảy ra khi các phần tử của mảng có thứ tự lộn xộn (không tăng dần cũng không giảm dần).
O(n2)
Độ phức tạp của không gian:
Độ phức tạp của không gian là O(1)do một nhiệt độ thay đổi bổ sung được sử dụng để hoán đổi.
Trong thuật toán được tối ưu hóa, biến được hoán đổi làm tăng thêm độ phức tạp của không gian, do đó O(2).
Ứng dụng sắp xếp bong bóng
Sắp xếp bong bóng được sử dụng trong các trường hợp sau đây
- độ phức tạp của mã không quan trọng.
- một mã ngắn được ưu tiên.
