Trong ngôn ngữ lập trình C, sắp xếp bong bóng là kỹ thuật sắp xếp đơn giản nhất và còn được gọi là sắp xếp trao đổi.
Quy trình sắp xếp bong bóng
-
So sánh phần tử đầu tiên với các phần tử còn lại trong danh sách và trao đổi (hoán đổi) chúng, nếu chúng không theo thứ tự.
-
Lặp lại tương tự cho các phần tử khác trong danh sách cho đến khi tất cả các phần tử được sắp xếp.
Thuật toán
Dưới đây là một thuật toán để sắp xếp một danh sách các số nhất định theo thứ tự tăng dần bằng cách sử dụng kỹ thuật sắp xếp bong bóng -
Bước 1 - Bắt đầu
Bước 2 - Lấy danh sách (mảng), num
Bước 3 - danh sách đọc (list, num)
Bước 4 - danh sách in (danh sách, số)
Bước 5 - bub_sort (danh sách, số)
Bước 6 - danh sách in (danh sách, số)
readlist (list, num)
Bước 7 - dừng lại
1. for j = 0 to num 2. read list[j].
danh sách in (list, num)
1. for j =0 to num 2. write list[j].
bub_sort (danh sách, num)
1. for i = 0 to num 2. for j =0 to (num – i) 3. if( list[j] > list[j+1]) 4. swapList( address of list[j], address of list[j+1])
swapList (địa chỉ của danh sách [j], địa chỉ của danh sách [j + 1])
1. temp = value at list[j] 2. value at list[j] = value at list[j+1] 3. value at list[j+1] = temp
Ví dụ
Sau đây là chương trình C để sắp xếp một danh sách các số nhất định theo thứ tự tăng dần bằng cách sử dụng kỹ thuật sắp xếp bong bóng -
#include <stdio.h>
#define MAX 10
void swapList(int *m,int *n){
int temp;
temp = *m;
*m = *n;
*n = temp;
}
/* Function for Bubble Sort */
void bub_sort(int list[], int n){
int i,j;
for(i=0;i<(n-1);i++)
for(j=0;j<(n-(i+1));j++)
if(list[j] > list[j+1])
swapList(&list[j],&list[j+1]);
}
void readlist(int list[],int n){
int j;
printf("\nEnter the elements: \n");
for(j=0;j<n;j++)
scanf("%d",&list[j]);
}
/* Showing the contents of the list */
void printlist(int list[],int n){
int j;
for(j=0;j<n;j++)
printf("%d\t",list[j]);
}
void main(){
int list[MAX], num;
printf(" Enter the number of elements \n");
scanf("%d",&num);
readlist(list,num);
printf("\n\nElements in the list before sorting are:\n");
printlist(list,num);
bub_sort(list,num);
printf("\n\nElements in the list after sorting are:\n");
printlist(list,num);
}
Đầu ra
Khi chương trình trên được thực thi, nó tạo ra kết quả sau -
Enter the number of elements 10 Enter the elements: 11 23 45 1 3 6 35 69 10 22 Elements in the list before sorting are: 11 23 45 1 3 6 35 69 10 22 Elements in the list after sorting are: 1 3 6 10 11 22 23 35 45 69