/*
    xx__shell_sort.c
    -----
    Program generirani niz slucajnih brojeva sortira shell sort algoritmom
    za sortiranje.
*/
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define MAX 100
 
int main()
{
	int n, i, j, k, gap, a[MAX];
 
	srand((unsigned)time(NULL));
 
    printf("Unesite zeljenu velicinu niza brojeva: ");
    scanf("%d", &n);
	printf("Niz slucajnih brojeva [1-100]:\n");
	for (k = 0; k < n; k++) {
		a[k] = rand() % 100 + 1;
		printf("%d ", a[k]);
	}
	printf("\n\n");
 
	for (gap = n/2; gap > 0; gap /= 2) {
/*        printf("gap = %d : ", gap);*/
		for (i = gap; i < n; i++)
			for (j = i-gap; j >=0 && a[j] > a[j+gap]; j -= gap) {
                int t;
				t = a[j];
				a[j] = a[j+gap];
				a[j+gap] = t;
			}
/*	    for(k = 0; k < n; k++)
		    printf("%d ", a[k]);
	    printf("\n");*/
     }
 
	printf("\nNiz brojeva nakon provodjenja shell sort algoritma:\n");
	for(k = 0; k < n; k++)
		printf("%d ", a[k]);
	printf("\n");   
 
	return 0;
}