Question

How to implement shellsort (shell sort) + simulation in C

Answer 1

#include <stdio.h>
 
#define LEN 7
 
void shellsort(int a[], int len);
  
  
int main(void)
{
    int a[LEN] = {5, 1, 6, 3, 2, 7, 4};
 
    shellsort(a, LEN);
    for (int i = 0; i < LEN; i++)
         printf("%d  ", a[i]);
 
    return 0;
}
 
void shellsort(int a[], int len) 
{ 
    int i, j, gap, tmp; 
       
    for (gap = len/2; gap > 0; gap /= 2) 
         for (i = gap; i < len; i++) 
              for (j = i - gap; j >=0 && a[j]> a[j + gap]; j -= gap) 
              { 
                   tmp = a[j]; 
                   a[j] = a[j + gap]; 
                   a[j + gap] = tmp; 
              } 
} 
   
/*
   
run:
   
1  2  3  4  5  6  7

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <stdio.h>
 
#define LEN 7
 
void shellsort(int a[], int len);
void printf_arr(int a[], int len);
  
int main(void)
{
    int a[LEN] = {5, 1, 6, 3, 2, 7, 4};
 
    printf("first: ");
    printf_arr(a, LEN);
    shellsort(a, LEN);
    printf("last: ");
    printf_arr(a, LEN);
    
    return 0;
}
 
void shellsort(int a[], int len) 
{ 
    int i, j, gap, tmp; 
       
    for (gap = len/2; gap > 0; gap /= 2) 
    {
         printf("gap = %d\n", gap);
         for (i = gap; i < len; i++) 
         {
              for (j = i - gap; j >=0 && a[j]> a[j + gap]; j -= gap) 
              { 
                   printf("i = %d j = %d j + gap = %d\n", i, j, j + gap);
                   printf("a[j] = %d a[j + gap] = %d\n", a[j], a[j + gap]);
                   printf("before swap: ");
                   printf_arr(a, LEN);
                   tmp = a[j]; 
                   a[j] = a[j + gap]; 
                   a[j + gap] = tmp; 
                   printf("after swap: ");
                   printf_arr(a, LEN);
                   printf("\n\n");
              } 
         }
    }
} 

void printf_arr(int a[], int len) 
{
   for (int i = 0; i < LEN; i++)
         printf("%d  ", a[i]);

    printf("\n");
}
 
// The simulation
  
/*
   
run:
   
first: 5  1  6  3  2  7  4
gap = 3
i = 3 j = 0 j + gap = 3
a[j] = 5 a[j + gap] = 3
before swap: 5  1  6  3  2  7  4
after swap: 3  1  6  5  2  7  4


i = 6 j = 3 j + gap = 6
a[j] = 5 a[j + gap] = 4
before swap: 3  1  6  5  2  7  4
after swap: 3  1  6  4  2  7  5


gap = 1
i = 1 j = 0 j + gap = 1
a[j] = 3 a[j + gap] = 1
before swap: 3  1  6  4  2  7  5
after swap: 1  3  6  4  2  7  5


i = 3 j = 2 j + gap = 3
a[j] = 6 a[j + gap] = 4
before swap: 1  3  6  4  2  7  5
after swap: 1  3  4  6  2  7  5


i = 4 j = 3 j + gap = 4
a[j] = 6 a[j + gap] = 2
before swap: 1  3  4  6  2  7  5
after swap: 1  3  4  2  6  7  5


i = 4 j = 2 j + gap = 3
a[j] = 4 a[j + gap] = 2
before swap: 1  3  4  2  6  7  5
after swap: 1  3  2  4  6  7  5


i = 4 j = 1 j + gap = 2
a[j] = 3 a[j + gap] = 2
before swap: 1  3  2  4  6  7  5
after swap: 1  2  3  4  6  7  5


i = 6 j = 5 j + gap = 6
a[j] = 7 a[j + gap] = 5
before swap: 1  2  3  4  6  7  5
after swap: 1  2  3  4  6  5  7


i = 6 j = 4 j + gap = 5
a[j] = 6 a[j + gap] = 5
before swap: 1  2  3  4  6  5  7
after swap: 1  2  3  4  5  6  7


last: 1  2  3  4  5  6  7

*/

 

70+ SQL courses for beginners and professionals