14var_3task

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

int middle_digit(int n)
{
    n = n / 10 % 10;
    return n;
}

void ShellSort(int *array, int size)
{
    int step, i, j, tmp, k;
    int ind_array[size], tmp_i;

    for (i = 0; i < size; i++)
        ind_array[i] = i;

    for (step = size / 2; step > 0; step /= 2)          // выбор шага
        for (i = step; i < size; i++)                   // перечисление элементов, которые сортируются на определённом шаге
            for (j = i - step; j >= 0 && middle_digit(array[j]) < middle_digit(array[j + step]); j -= step) // Перестановка элементов внутри подсписка, пока i-тый не будет отсортирован
            {
                tmp = array[j];
                array[j] = array[j + step];
                array[j + step] = tmp;

                tmp_i = ind_array[j];
                ind_array[j] = ind_array[j + step];
                ind_array[j + step] = tmp_i;
            }
    for (i = 0; i < size - 1; i++)
    {
        if (middle_digit(array[i]) == middle_digit(array[i + 1]) && ind_array[i] < ind_array[i + 1])
            {
                tmp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = tmp;
            }
    }
}

int ip_search(int *a, int n, int search_number)
{
    int ind_size, i, j, kp_size;

    if (n > 8)
        kp_size = 8;
    else
        kp_size = 2;

    int kindex[n/kp_size], pindex[n/kp_size];

    for (i = 0, j = 0; i < n; i += 8, j++)
    {
        kindex[j] = a[i];              // переносим каждый 8-й ключ в индексную таблицу
        pindex[j] = i;                 // запоминаем текущий индекс
    }

    ind_size = j;                      // запоминаем размер индексной таблицы
    pindex[j] = i;                     // последний индекс равен n

    for (j = 0; j < ind_size; j++)
    {
        if (middle_digit(search_number) > middle_digit(kindex[j])) // если находим ключ больше введенного,
            break;                     // то выходим из цикла - мы нашли нужную область основной таблицы
    }

    if (j == 0)
        i = 0;                         // присваиваем i начальный индекс диапазона поиска в основной таблице
    else
        i = pindex[j - 1];

    for (i; i < pindex[j]; i++)        // осуществляем поиск в основной таблице
    {                                  // до следующего индекса индексной таблицы
        if (a[i] == search_number)     // если найдено введенное значение, выводим его
        {
            printf("\na[%1d] = %2d", i, a[i]);
            return 0;
        }
    }

    printf("\nElement doesn't exist");
    return 0;
}

int main()
{
    int n, search_number;

    printf("Enter array size = ");
    scanf("%d", &n);

    printf("Enter number for search = ");
    scanf("%d", &search_number);

    int a[n];

    for (int i = 0; i < n; i++)
    {
        printf("a[%d] = ", i);
        scanf("%d", &a[i]);
    }

    ShellSort(a, n);
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    ip_search(a, n, search_number);

    return 0;
}