shell Sort Algorithm

Shell Sort Algorithm, also known as diminishing increment sort, is an advanced in-place comparison sort algorithm that generalizes the insertion sort by allowing the exchange of elements that are far apart. It was developed by Donald Shell in 1959. The main idea behind this algorithm is to sort disjoint subsets of the input data by applying the insertion sort and gradually reduce the gap between the compared elements. By doing this, the algorithm can take advantage of the partially sorted structure that is built up during the sorting process, leading to improved performance. The algorithm begins by defining a gap, which is usually chosen to be half the size of the input data. The elements are then compared and swapped if they are not in the correct order, taking into account the specified gap. Once the pass through the data is complete, the gap is reduced, and the process is repeated until the gap is equal to 1. At this point, the algorithm works similar to the regular insertion sort. The complexity of the shell sort algorithm depends on the choice of gap sequence, with the best-known complexity being O(n log² n) using the Ciura gap sequence. Although Shell Sort is not as efficient as other advanced sorting algorithms like Quick Sort or Merge Sort, it is straightforward to implement and is suitable for mid-sized data sets or when the simplicity of implementation is more important than the speed of execution.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ELEMENT_NR 20
#define ARRAY_LEN(x) (sizeof(x) / sizeof((x)[0]))
const char *notation = "Shell Sort Big O Notation:\
						\n--> Best Case: O(n log(n)) \
						\n--> Average Case: depends on gap sequence \
						\n--> Worst Case: O(n)";

void show_data(int arr[], int len)
{
    int i;

    for (i = 0; i < len; i++)
        printf("%3d ", arr[i]);
    printf("\n");
}

void swap(int *a, int *b)
{
    int tmp;

    tmp = *a;
    *a = *b;
    *b = tmp;
}

void shellSort(int array[], int len)
{
    int i, j, gap;

    for (gap = len / 2; gap > 0; gap = gap / 2)
        for (i = gap; i < len; i++)
            for (j = i - gap; j >= 0 && array[j] > array[j + gap]; j = j - gap)
                swap(&array[j], &array[j + gap]);
}

int main(int argc, char *argv[])
{
    int i;
    int array[ELEMENT_NR];
    int range = 500;
    int size;
    clock_t start, end;
    double time_spent;

    srand(time(NULL));
    for (i = 0; i < ELEMENT_NR; i++)
        array[i] = rand() % range + 1;

    size = ARRAY_LEN(array);

    show_data(array, size);
    start = clock();
    shellSort(array, size);
    end = clock();
    time_spent = (double)(end - start) / CLOCKS_PER_SEC;

    printf("Data Sorted\n");
    show_data(array, size);

    printf("%s\n", notation);
    printf("Time spent sorting: %f\n", time_spent);

    return 0;
}

LANGUAGE:

DARK MODE: