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 <stdio.h>
#include <stdbool.h>

#define MAX 10

int 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ả:

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.