希爾排序範例程式(C程式)


使用C語言來編寫 shell 排序程式範例,如下所示:

#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("[");
	
   // navigate through all items 
   for(i = 0;i<MAX;i++){
      printf("%d ",intArray[i]);
   }
   printf("]\n");
}

void shellSort(){
   int inner, outer;
   int valueToInsert;
   int interval = 1;   
   int elements = MAX;
   int i = 0;
   
   while(interval <= elements/3) {
      interval = interval*3 +1;                   
   }

   while(interval > 0) {
      printf("iteration %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(" item moved :%d\n",intArray[inner]);
         }
         
         intArray[inner] = valueToInsert;
         printf(" item inserted :%d, at position :%d\n",valueToInsert,inner);
      }
      interval = (interval -1) /3;           
      i++;
   }          
}

int main() {
   printf("Input Array: ");
   display();
   printline(50);
   shellSort();
   printf("Output Array: ");
   display();
   printline(50);
   return 1;
}

如果我們編譯並執行上述程式那麼這將產生以下結果 -

Input Array: [4, 6, 3, 2, 1, 9, 7]
==================================================
iteration 0#: [4, 6, 3, 2, 1, 9, 7]
 item moved :4
 item inserted :1, at position :0
 item inserted :9, at position :5
 item inserted :7, at position :6
iteration 1#: [1, 6, 3, 2, 4, 9, 7]
 item inserted :6, at position :1
 item moved :6
 item inserted :3, at position :1
 item moved :6
 item moved :3
 item inserted :2, at position :1
 item moved :6
 item inserted :4, at position :3
 item inserted :9, at position :5
 item moved :9
 item inserted :7, at position :5
Output Array: [1, 2, 3, 4, 6, 7, 9]
==================================================