Bubble Sort (Thuật Toán Trôi nổi)

Ý tưởng chỉnh của nó là so sánh từng cặp phần tử liển kể nhau, rồi sẽ hoán đổi thứ tự của chúng để cho đúng với thứ tự, quá trình này được lặp lại nhiều lần cho đến khi mảng được sắp xếp xong.

Nguyên lý hoạt động

- So sánh hai phần tử liền kề trong mảng.

- Nếu phần tử đứng trước lớn hơn phần tử phía sau thì hoán đổi chúng.

- Lặp lại cho đến khi không còn hoán đổi nào xảy ra.

- Sau mỗi vòng lặp, phần tử lớn nhất sẽ nổi lên ở cuối mảng (điều này như cái tên của thuật toán giống như bong bóng nổi lên trên mặt nước).

Code Python

def bubble_sort(arr):
    n = len(arr)					# Lấy độ dài mảng.
    for i in range(n-1):				# Chạy duyệt các phần tử từ đầu đến cuối mảng.
    	swapped = False					# swapped dùng để kiểm tra xem mỗi vòng chạy có hoán đổi phần tử nào không.
        for j in range(n-i-1):				# n-i-1 lần lặp của j sẽ giảm dần dựa theo vòng của i.
        	if arr[j] > arr[j+1]:			# Nếu phần tử thứ j lớn hơn phần tử thứ ngay sau nó j+1
            	arr[j], arr[j+1] = arr[j+1], arr[j]	# Thì đổi chỗ hai phần tử này cho nhau.
                swapped	= True				# vòng này có hoán đổi phần tử.
        if not swapped:					# Nếu không có sự hoán đổi phần tử nào.
        	break					# Thì ngắt vòng lặp.
    return arr						# Trả về mảng đã được sắp xếp.

Giải thích

ý nghĩa của swapped:

- Ban đầu: swapped = False (tức là chưa có hoán đổi).

- Trong vòng lặp: Nếu có ít nhất một cặp phần tử bị hoán đổi thì swapped = True.

- Kết thúc vòng lặp: nếu swapped là False nghĩa là không có hoán đổi nào, vòng lặp ngừng sớm. Nếu là True nghĩa là đã có sự hoán đổi, ta sẽ tiếp tục vòng lặp tiếp theo.

Mục đích của việc này là để tổi ưu code, swapped sẽ giúp kiểm tra xem mảng đã được sắp xếp song chưa, tránh trường hợp mặc dù đã sắp xếp xong mảng, nhưng do vòng lặp i vẫn chưa duyệt hết, nó sẽ tiếp tục duyệt đến tất cả các phần tử, điều này sẽ tốn thêm một lượng thời gian không cần thiết.

tại sao lại là n-i-1

- Vòng lặp ngoài chạy i lần.

- Sau mỗi vòng lặp ngoài, phần tử lớn nhất đã nằm ở vị trí cuối cùng trong mảng.

- Do đó, số phần tử cần kiểm tra sẽ giảm đi 1 sau mỗi vòng lặp.

- Nếu không giảm, chúng ta sẽ duyệt lại các phần tử đã đúng vị trí.

Code C++

#include <iostream>
using namespace std;

void bubbleSort(int arr[],int n) {
	for (int i = 0; i < n-1; i++){
    	bood swapped = false;
        for (int j = 0; j < n-i-1; j++){
        	if (arr[j] < arr[j+1]) {
            	swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(ar[0]);	// Lấy độ dài của mảng
    bubbleSort(arr, n);
    for (int i = 0; i < n; i++) {
    	cout << arr[i] << " ";
    }
    return 0;
}

Ưu và nhược điểm

- Ưu điểm:
+ Dễ hiểu, dễ cài đặt.
+ Không cần bộ nhớ phụ ngoài mảng.
+ Có thể dừng sớm nếu mảng đã sắp xếp.

- Nhược điểm:
+ Hiệu suất thấp với dữ liệu lớn.
+ Ít được dùng trong thực tế, chủ yếu là để giảng dạy.

Ứng dụng

- Chủ yếu dùng trong giáo dục để minh họa thuật toán sắp xếp.

- Thích hợp cho mảng nhỏ hoặc khi yêu cầu thuật toán đơn giản, dễ hiểu.

- Không dùng trong hệ thống lớn vì hiệu suất kém.