sorting_algorithms/100-shell_sort.c at main · Apinedas/sorting_algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include "sort.h"

/**
 * shell_sort - sorts an array using the shell algorithm
 * @array: Array to sort
 * @size: Array's size
 */

void shell_sort(int *array, size_t size)
{
    size_t nextgap = 1, i;
    int gap = 0, j, aux;

    while (nextgap < size)
    {
        gap = nextgap;
        nextgap = (3 * gap) + 1;
    }
    while (gap > 0)
    {
        i = 0;
        while (i < (size - 1))
        {
            if (i + gap <= (size - 1) && array[i] > array[i + gap])
            {
                aux = array[i];
                array[i] = array[i + gap];
                array[i + gap] = aux;
                for (j = i; (j - gap) >= 0; j -= gap)
                {
                    if (array[j] < array[j - gap])
                    {
                        aux = array[j];
                        array[j] = array[j - gap];
                        array[j - gap] = aux;
                    }
                }
            }
            else if (i != (size - 1) && array[i] < array[size - 1])
            {
                aux = array[i];
                array[i] = array[size - 1];
                array[size - 1] = aux;
                for (j = i; (j - gap) >= 0; j -= gap)
                {
                    if (array[j] < array[j - gap])
                    {
                        aux = array[j];
                        array[j] = array[j - gap];
                        array[j - gap] = aux;
                    }
                }
            }
            i++;
        }
        gap = (gap - 1) / 3;
        print_array(array, size);
    }
}