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.
DANH SÁCH BÀI VIẾT Thuật toán sắp xếp nhanh (Quick Sort) Thuật toán sắp xếp trộn (Merge Sort) Thuật toán sắp xếp đổi chỗ trực tiếp (Interchange Sort) Thuật toán sắp xếp nổi bọt (Bubble Sort) Thuật toán sắp xếp chọn(Selection Sort) Thuật toán sắp xếp chèn (Insertion sort)
Ý tưởng của thuật toán Bubble sort
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.
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
Đá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é.
