Data-structures-algorithms-shell-sort-program-in-c

Cのシェルソートプログラム

シェルソートは非常に効率的なソートアルゴリズムであり、挿入ソートアルゴリズムに基づいています。 このアルゴリズムは、より小さい値が右端にあり、左端に移動する必要がある場合、挿入ソートの場合のような大きなシフトを回避します。

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&plus;&plus;) {
      printf("=");
   }

   printf("=\n");
}

void display() {
   int i;
   printf("[");

  //navigate through all items
   for(i = 0;i < MAX;i&plus;&plus;) {
      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 &plus;1;
   }

   while(interval > 0) {
      printf("iteration %d#:",i);
      display();

      for(outer = interval; outer < elements; outer&plus;&plus;) {
         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&plus;&plus;;
   }
}

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 ]
==================================================