Sắp xếp chèn (Insertion Sort) trong C

Sắp xếp chèn là một giải thuật sắp xếp dựa trên so sánh in-place. Ở đây, một danh sách con luôn luôn được duy trì dưới dạng đã qua sắp xếp. Sắp xếp chèn là chèn thêm một phần tử vào danh sách con đã qua sắp xếp. Phần tử được chèn vào vị trí thích hợp sao cho vẫn đảm bảo rằng danh sách con đó vẫn sắp theo thứ tự.

Với cấu trúc dữ liệu mảng, chúng ta tưởng tượng là: mảng gồm hai phần: một danh sách con đã được sắp xếp và phần khác là các phần tử không có thứ tự. Giải thuật sắp xếp chèn sẽ thực hiện việc tìm kiếm liên tiếp qua mảng đó, và các phần tử không có thứ tự sẽ được di chuyển và được chèn vào vị trí thích hợp trong danh sách con (của cùng mảng đó).

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 độ 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ử.

Chương trình minh họa Sắp xếp chèn (Insertion Sort) trong C

#include <stdio.h>
#include <stdbool.h>
#define MAX 7

int intArray[MAX] = {4,6,3,2,1,9,7};

void printline(int count){
   int i;
	
   for(i = 0;i <count-1;i++){
      printf("=");
   }
	
   printf("=\n");
}

void display(){
   int i;
   printf("[");
	
   // duyet qua tat ca phan tu
   for(i = 0;i<MAX;i++){
      printf("%d ",intArray[i]);
   }
	
   printf("]\n");
}

void insertionSort(){

   int valueToInsert;
   int holePosition;
   int i;
  
   // lap qua tat ca cac so
   for(i = 1; i < MAX; i++){ 
	
      // chon mot gia tri de chen
      valueToInsert = intArray[i];
		
      // lua chon vi tri de chen
      holePosition = i;
		
      // kiem tra xem so lien truoc co lon hon gia tri duoc chen khong
      while (holePosition > 0 && intArray[holePosition-1] > valueToInsert){
         intArray[holePosition] = intArray[holePosition-1];
         holePosition--;
         printf(" Di chuyen phan tu : %d\n" , intArray[holePosition]);
      }

      if(holePosition != i){
         printf(" Chen phan tu : %d, tai vi tri : %d\n" , valueToInsert,holePosition);
         // chen phan tu tai vi tri chen 
         intArray[holePosition] = valueToInsert;   
      }

      printf("Vong lap thu %d#:",i);
      display();
		
   }  
}

main(){
   printf("Mang du lieu dau vao: ");
   display();
   printline(50);
   insertionSort();
   printf("Mang sau khi da sap xep: ");
   display();
   printline(50);
}

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.