GapSort или ShellSort не меняются должным образом - PullRequest
1 голос
/ 07 июня 2019

Я устанавливаю программу GapSort, для некоторых массивов код не работает. Чего мне не хватает?

void main()
{
    int eX[10] = {1, 3, 49, 29, 20, 8, 28, 24, 10, 29};
    int eXlen = sizeof(eX) / sizeof(int);
    gapSort(eX, eXlen);
} 
void gapSort(int arr[], int len)
    {
        int temp, gap, swap;
        gap = len / 2;
        while (1)
        {
            for (int i = 0; i < len - gap; i++)
            {
                swap = 0;
                if (arr[i] > arr[i + gap])
                {
                    temp = arr[i];
                    arr[i] = arr[i + gap];
                    arr[i + gap] = temp;
                    swap = 1;
                }
            }
            if (swap == 0)
            {
                if (gap == 1)
                    break;
                gap /= 2;
            }
        }
    }

1, 3, 49, 29, 20, 8, 28, 24, 10, 29 для этого типа массива он не работает

1 Ответ

3 голосов
/ 07 июня 2019

Вы должны поставить swap = 0; перед циклом for.

Вы хотите изменить значение gap, если вы ничего не меняли в течение полного цикла. В вашей текущей реализации вы могли поменять значения, например с i=1, но вы сбросите swap=0 в следующем цикле, поэтому вы будете повторять с тем же gap, только если вы поменяли местами значения последнего значения i. Вы, возможно, видели проблему самостоятельно, если бы показывали значение swap рядом с arrDisp. (Я предполагаю, что arrDisp - это функция для отображения содержимого массива. Этот вызов функции был в исходном вопросе до того, как он был отредактирован.)

static void gapSort(int arr[], int len)
{
    int temp, gap, swap;
    gap = len / 2;
    while (1)
    {
        swap = 0;
        for (int i = 0; i < len - gap; i++)
        {
            if (arr[i] > arr[i + gap])
            {
                temp = arr[i];
                arr[i] = arr[i + gap];
                arr[i + gap] = temp;
                swap = 1;
            }
        }
        /* arrDisp(arr, len); */
        if (swap == 0)
        {
            if (gap == 1)
                break;
            gap /= 2;
        }
    }
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...