Sắp xếp nổi bọt (Bubble Sort) trong C

Sắp xếp nổi bọt là một giải thuật sắp xếp đơn giản. Giải thuật sắp xếp này được tiến hành dựa trên việc so sánh cặp phần tử liền kề nhau và tráo đổi thứ tự nếu chúng không theo thứ tự.

Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi mà độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο(n²) với n là số phần tử.

Giải thuật sắp xếp nổi bọt là giải thuật chậm nhất trong số các giải thuật sắp xếp cơ bản. Giải thuật này còn chậm hơn giải thuật đổi chỗ trực tiếp mặc dù số lần so sánh bằng nhau, nhưng do đổi chỗ hai phần tử kề nhau nên số lần đổi chỗ nhiều hơn.

Chương trình minh họa sắp xếp nổi bọt (Bubble Sort) trong C

#include 
#include #define MAX 10int list[MAX] = {1,8,4,6,0,3,5,2,7,9};void display(){
   int i;
   printf("[");
	
   // Duyet qua tat ca phan tu
   for(i = 0; i < MAX; i++){
      printf("%d ",list[i]);
   }
	
   printf("]\n");
}void bubbleSort() {
   int temp;
   int i,j;
	
   bool swapped = false;       
   
   // lap qua tat ca cac so
   for(i = 0; i < MAX-1; i++) { 
      swapped = false;
		
      // vong lap thu hai
      for(j = 0; j < MAX-1-i; j++) {
         printf("     So sanh cac phan tu: [ %d, %d ] ", list[j],list[j+1]);         // kiem xa xem so ke tiep co nho hon so hien tai hay khong
         //   trao doi cac so. 
         //  (Muc dich: lam noi bot (bubble) so lon nhat) 
			
         if(list[j] > list[j+1]) {
            temp = list[j];
            list[j] = list[j+1];
            list[j+1] = temp;            swapped = true;
            printf(" => trao doi [%d, %d]\n",list[j],list[j+1]);
         }else {
            printf(" => khong can trao doi\n");
         }
			
      }      // neu khong can trao doi nua, tuc la 
      //   mang da duoc sap xep va thoat khoi vong lap. 
      if(!swapped) {
         break;
      }
      
      printf("Vong lap thu %d#: ",(i+1)); 
      display();                     
   }
	
}main(){
   printf("Mang du lieu dau vao: ");
   display();
   printf("\n");
	
   bubbleSort();
   printf("\nMang sau khi da sap xep: ");
   display();
}

Kết quả

Biên dịch và chạy chương trình C trên sẽ cho kết quả: