Bubble Sort là một trong những thuật toán sắp xếp đơn giản nhất dùng để sắp xếp dữ liệu bằng cách so sánh các phần tử liền kề. Tất cả các phần tử được so sánh theo từng giai đoạn. Giai đoạn đầu đặt giá trị lớn nhất ở cuối, giai đoạn hai đặt phần tử lớn thứ hai ở vị trí倒数 thứ hai và cứ thế cho đến khi danh sách hoàn toàn được sắp xếp.
Thuật toán Bubble Sort
int arr[5]= { 5,4,2,1,3 };
int i, j ;
Duyệt từ chỉ mục i=0 đến i<kích thước mảng
Duyệt từ chỉ mục j=0 đến kích thước mảng - i - 1
Nếu arr[i]>arr[j] hoán đổi arr[i] với arr[j]
Kết thúc
Bubble Sort đệ quy
Nếu độ dài mảng là 1 thì trả về
Duyệt mảng một lần và cố định phần tử lớn nhất ở cuối
Đệ quy thực hiện bước 2 cho phần còn lại của mảng trừ phần tử cuối
Ví dụ
Đầu vào − Arr[] = { 5,7,2,3,1,4 }; length=6
Đầu ra − Mảng đã sắp xếp: 1 2 3 4 5 7
Giải thích −
Lượt 1: 5 7 2 3 1 4 → swap → 5 2 7 3 1 4 → swap → 5 2 3 7 1 4 → swap → 5 2 3 1 7 4 → swap → 5 2 3 1 4 7 Lượt 2: 5 2 3 1 4 7 → swap → 2 5 3 1 4 7 → swap → 2 3 5 1 4 7 → swap → 2 3 1 5 4 7 → swap → 2 3 1 4 5 7 Lượt 3: 2 3 1 4 5 7 → swap → 2 1 3 4 5 7 → không swap Lượt 4: 2 1 3 4 5 7 → swap → 1 2 3 4 5 7 → không swap ở các lượt tiếp theo
Đầu vào − Arr[] = { 1, 2, 3, 3, 2 };
Đầu ra − Mảng đã sắp xếp: 1 2 2 3 3
Giải thích −
Lượt 1: 1 2 3 3 2 → swap → 1 2 3 2 3 → swap → 1 2 2 3 3 → không swap ở các lượt tiếp theo Lượt 2: 1 2 2 3 3 → không swap ở các lượt tiếp theo
Cách tiếp cận trong chương trình dưới đây
Trong cách tiếp cận đệ quy của Bubble sort, trường hợp cơ sở là độ dài mảng = 1. Ngược lại duyệt mảng bằng vòng for đơn và hoán đổi phần tử cho phù hợp.
Nhập mảng Arr[] và độ dài là số phần tử trong nó.
Hàm recurbublSort(int arr[], int len) nhận mảng và độ dài, sắp xếp mảng đệ quy dùng bubble sort.
Khai báo biến temp.
Nếu độ dài mảng là 1 thì trả về void.
Ngược lại duyệt mảng bằng vòng for đơn và với mỗi phần tử arr[i]>arr[i+1], hoán đổi các phần tử đó.
Gán temp=arr[i], arr[i]=arr[i+1] và arr[i+1]=temp.
Giảm độ dài đi 1 vì vòng lặp trước đã đặt phần tử lớn nhất ở vị trí cuối.
Gọi đệ quy recurbublSort(arr,len).
Kết thúc tất cả lời gọi, khi len trở thành 1 sẽ thoát đệ quy và mảng đã được sắp xếp.
In mảng đã sắp xếp trong main.
Ví dụ
#include <stdio.h>
void recurbublSort(int arr[], int len){
int temp;
if (len == 1){
return;
}
for (int i=0; i<len-1; i++){
if (arr[i] > arr[i+1]){
temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
len=len-1;
recurbublSort(arr, len);
}
int main(){
int Arr[] = {21, 34, 20, 31, 78, 43, 66};
int length = sizeof(Arr)/sizeof(Arr[0]);
recurbublSort(Arr, length);
printf("Mảng đã sắp xếp : ");
for(int i=0;i<length;i++){
printf("%d ",Arr[i]);
}
return 0;
}
Kết quả
Nếu chạy mã trên sẽ tạo ra kết quả sau:
Mảng đã sắp xếp: 20 21 31 34 43 66 78