Shell Sort trong C

Shell Sort là một giải thuật sắp xếp mang lại hiệu quả cao dựa trên giải thuật sắp xếp chèn (Insertion Sort). Giải thuật này tránh các trường hợp phải tráo đổi vị trí của hai phần tử xa nhau trong giải thuật sắp xếp chọn (nếu như phần tử nhỏ hơn ở vị trí bên phải khá xa so với phần tử lớn hơn bên trái).

Đầu tiên, giải thuật này sử dụng giải thuật sắp xếp chọn trên các phần tử có khoảng cách xa nhau, sau đó sắp xếp các phần tử có khoảng cách hẹp hơn. Khoảng cách này còn được gọi là khoảng (interval) – là số vị trí từ phần tử này tới phần tử khác. Khoảng này được tính dựa vào công thức Knuth như sau:

h = h * 3 + 1trong đó:
   h là Khoảng (interval) với giá trị ban đâu là 1

Chương trình Shell 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) {
      printf("Vong lap thu %d#:",i); 
      display();
      
      for(outer = interval; outer < elements; outer++) {
         valueToInsert = intArray[outer];
         inner = outer;
			
         while(inner > interval -1 && intArray[inner - interval] 
            >= valueToInsert) {
            intArray[inner] = intArray[inner - interval];
            inner -=interval;
            printf(" Di chuyen phan tu :%d\n",intArray[inner]);
         }
         
         intArray[inner] = valueToInsert;
         printf(" Chen phan tu :%d, tai vi tri :%d\n",valueToInsert,inner);
      }
		
      interval = (interval -1) /3;           
      i++;
   }          
}int main() {
   printf("Mang du lieu dau vao: ");
   display();
   printline(50);
   shellSort();
   printf("Mang ket qua: ");
   display();
   printline(50);
   return 1;
}

Kết quả

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