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 
#include 
#define MAX 7int intArray[MAX] = {4,6,3,2,1,9,7};void printline(int count){
   int i;
	
   for(i = 0;i  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ả: