Shell-Sortierung in C liefert kein Ergebnis

Question

Ich muss eine Shell-Sortierung in C implementieren und die optimierte Version verwenden (wobei die Lücke zuerst auf die Größe von Array/2 gesetzt wird und diese Zahl dann wiederholt durch 2,2 geteilt wird). Das Problem ist, dass die Antwort nicht immer vollständig sortiert ist und ich bin nicht sicher, ob dies an einem logischen Fehler in meinem Code oder an einem Mangel der Shell-Sortierung liegt.

Dies ist mein Code:

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <time.h> 
#define MAX 7 

void shellSort(int *a, int size); 
void insert(int *a, int next_pos, int gap); 

void shellSort(int *a,int size) 
{ 
    int gap = floor(size/2); 
    int next_pos; 
    while (gap>0) 
    { 
     for(next_pos = gap; next_pos < size; next_pos++) 
      insert(a, next_pos, gap); 

     if(gap == 2) 
      gap = 1; 
     else 
      gap = (int)(gap/2.2); 
    } 
} 

void insert(int *a, int next_pos, int gap) 
{ 
    int value = a[next_pos]; 
    while(next_pos >= gap && a[next_pos] < a[next_pos-gap]) 
    { 
     a[next_pos] = a[next_pos-gap]; 
     next_pos = next_pos - gap; 
    } 
    a[next_pos] = value; 
} 

int main() 
{ 
    int nums[MAX]; 
    time_t t; 
    srand((unsigned) time(&t)); // seed randomiser 

    printf("Array before sorting:\n"); 
    int i; 
    for(i=0; i<MAX; i++) 
    { 
     nums[i] = rand() % 101; // filling array with random numbers 
     printf("%d\t", nums[i]); 
    } 

    shellSort(nums, MAX); 

    printf("\nArray after sorting:\n"); 
    for(i=0; i<MAX; i++) 
     printf("%d\t", nums[i]); 

    return 0; 
} 

Die folgende meiner Ausgabe ist:

Array before sorting: 
74 26 1 12 38 81 94 
Array after sorting: 
12 1 26 38 74 81 94 

edit: geschrieben, bevor ich mit meiner Frage fertig war oops

Answer 1

Ich denke, das Problem liegt hier :

int value = a[next_pos]; 
while(next_pos >= gap && a[next_pos] < a[next_pos-gap]) 

Da Sie unter next_pos in den Leitungen sind zu ändern, ich denke, diese Zeilen (wenn mein Verständnis von shellsort korrekt ist) sollte lauten:

int value = a[next_pos]; 
while(next_pos >= gap && value < a[next_pos-gap])