Shell Sort C language

Question

The task was simply to write a program to sort the entered (or randomly generated) numbers using the Shell sort method. But then the teacher decided to complicate the task and said:

Create another function that will test Shell's algorithm: create many arrays from n random numbers, sort by Shell's method and display the average number of iterations for all these arrays.

Please, help and explain how to do it

This is my code:

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void shellsort(int v[], int n);

int main() {
    srand(time(NULL));
    int N;
    printf("Input N: ");
    scanf_s("%d", &N);
    int *a = (int *)malloc(N * sizeof(int));
    int i = 0;

    printf("Enter masiv: ");
    for (; i < N; i++) {
        a[i] = rand() % 100;
        printf("%d ", a[i]);
    }

    shellsort(a, N);

    printf("\n");
    printf("Result: ");
    for (i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

void shellsort(int v[], int n) {
    int i, j, gap, temp;
    int num = 0;

    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++)
            for (j = i - gap; j >= 0 && v[j] > v[j + gap]; j -= gap) {
                temp = v[j];
                v[j] = v[j + gap];
                v[j + gap] = temp;
                num++;
            }
    }
    printf("\n");
    printf("Number of iterations: %d\n", num);
}

Many thanks in advance to everyone who responds;))

Answer 1

Alright, I will start by saying that I am not gonna do your homework and write the code for it. I'll just try to give you a starting point.

Shell sort currently doesn't compute the number of iterations, so you might declare a variable named iterations at the beginning of shellsort and increment it in the deepest loop inside shell sort, and return this variable instead of returning void.

The new function that you're about to write should be similar to what you're doing in the main for the number generation part. Make a loop that encapsulates the loop that generates arrays for you. Because you need multiple arrays now.

Store the sum of iterations, maybe like this sum += shellsort(a); Then the average of iterations is the sum/N, where N is the number of random arrays you want to generate.