Thứ Tư, 28 Tháng Chín 2022
Trang chủLập trìnhCTDL & Thuật toánThuật toán sắp xếp nổi bọt (Bubble Sort)

Thuật toán sắp xếp nổi bọt (Bubble Sort)

Trong bài viết này Blog tuicocach.com sẽ giới thiệu tới các bạn thuật toán sắp xếp nổi bọt. Đây là một trong các thuật toán sắp xếp căn bản thường dùng.

Ý tưởng của thuật toán Bubble sort

Minhh họa thuật toán sắp xếp nổi bọt
Minhh họa thuật toán sắp xếp nổi bọt

Thuật toán sắp xếp bubble sort thực hiện sắp xếp dãy số bằng cách lặp lại công việc đổi chỗ 2 số liên tiếp nhau nếu chúng đứng sai thứ tự cho đến khi dãy số được sắp xếp.

XÊM THÊM
Thuật toán sắp xếp chọn(Selection Sort)
Thuật toán sắp xếp chèn (Insertion sort)

Ví dụ sử dụng thuật toán BubbleSort sắp xếp dãy {3,4,1,2} theo thứ tự tăng dần ta sẽ thấy các bước thực hiện như sau.

Ví dụ: Sử dụng thuật toán BubbleSort sắp xếp dãy {3,2,6,9,1,4,7,10,8,5} theo thứ tự tăng dần ta sẽ thấy các bước thực hiện như sau.

Các bước thực hiện sắp xếp dãy số từ 1 tới 10

Hàng đầu tiên mô phỏng trạng thái ban đầu của mảng(dãy số chưa sắp xếp). Ở lần lặp đầu tiên chúng ta duyệt từ đầu mảng tới cuối mảng 2 phần tử cạnh nhau (2 ô màu vàng ảnh trên)có thứ tự sai sẽ đổi chỗ cho nhau, sau lần lặp phần tử lớn nhất sẽ bị đẩy về ô cuối cùng của mảng. Các lần lặp tiếp theo thực hiện tương tự cho đến khi mảng được sắp xếp.

Cài đặt thuật toán trên ngôn ngữ C/C++

#include <stdio.h>
//Hàm đổi chỗ 2 số nguyên a, b
void swap(int &a, int &b)
{
	int temp = a;
	a=b;
	b=temp;
}

void bubbleSort(int arr[], int n)
{
    bool haveSwap = false;
    for (int i = 0; i < n-1; i++){
        haveSwap = false;
        for (int j = 0; j < n-i-1; j++){
            if (arr[j] > arr[j+1]){
                swap(arr[j], arr[j+1]);
                haveSwap = true;//Kiểm tra có sự hoán đổi
            }
        }
 // Nếu không có hoán đổi nào sảy ra => mảng đã sắp xếp.
        if(haveSwap == false){
            break;
        }
    }
}
//Hàm xuất mảng
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main()
{
	int arr[] = {3,2,6,9,1,4,7,10,8,5};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Kết quả chạy chương trình trên

Kết quả thực hiện chương trình

Đánh giá thuật toán sắp xếp bubble sort

Độ  phức tạp thuật toán

  • Trường hợp tốt: O(n) (Chỉ xảy ra khi mảng ban đầu đã là 1 mảng sắp xếp).
  • Trung bình: O(n^2)
  • Trường hợp xấu: O(n^2)

Cảm ơn đã theo dõi bài viết, nếu có bất kỳ thắc mắc hay góp ý comment bên dưới nhé.

0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x