Перестановки и сравнения в сортировке оболочки

Question

Я пытаюсь выяснить, как найти общее количество свопов и сравнений, используемых в функции сортировки оболочки, но я не совсем уверен, где разместить добавления свопов и сравнений.

Я добавляю дополнения в эту функцию вставки сортировки ниже.

void insertionSortInterleaved(int numbers[], int numbersSize, int startIndex, int gap) {
    int i = 0;
    int j = 0;
    int temp = 0;

    for (i = startIndex + gap; i < numbersSize; i += gap) {
        j = i;
        while (j - gap >= startIndex && numbers[j] < numbers[j - 1]) {
            temp = numbers[j];
            numbers[j] = numbers[j - gap];
            numbers[j - gap] = temp;
            j = j - gap;
            totalComps++; //declared globally
            totalSwaps++; //declared globally
        }

    }
}

Я знаю, что totalSwaps в порядке, но я не очень уверен, куда поставить totalComps, поскольку мы также сравниваем в цикле while.

Answer 1

Увеличивайте условный счетчик каждый раз, когда вы делаете тест.

Компактный способ сделать это - добавить префикс операции приращения к каждому тесту с помощью && (который будет успешным, поскольку счетчик положительный, так как переменная без знака без давления):

для (i = startIndex + пробел; ++ totalComps && (i

и

while (++ totalComps && (j - gap> = startIndex) && ++ totalComps && (numbers [j]

Answer 2

Вы можете использовать пару функциональных объектов , один из которых выполняет сравнение, а другой - своп.

struct counted_less
{
    int count = 0;
    bool operator()(int lhs, int rhs)
    {
        ++count;
        return lhs < rhs;
    }
}

struct counted_swap
{
    int count = 0;
    void operator()(int & lhs, int & rhs)
    {
        ++count;
        using std::swap;
        swap(lhs, rhs);
    }
}


std::pair<int, int> insertionSortInterleaved(int numbers[], int numbersSize, int startIndex, int gap) {
    counted_less less;
    counted_swap swap;

    for (int i = startIndex + gap; i < numbersSize; i += gap) {
        for (int j = i; j - gap >= startIndex && less(numbers[j], numbers[j - 1]); j -= gap) {
            swap(numbers[j], numbers[j - gap]);
        }
    }

    return { less.count, swap.count };
}

Answer 3

Я думаю, что сравнение должно учитываться, даже если условие было ложным

Это означало только сравнение элементов массива, а не каждое сравнение в вашем коде ...

см. Следующий код

void insertionSortInterleaved(int numbers[], int numbersSize, int startIndex, int gap) {
    int i = 0;
    int j = 0;
    int temp = 0;

    for (i = startIndex + gap; i < numbersSize; i += gap) {
        j = i;
        while (j - gap >= startIndex) {
            //each iteration is compare so increment here
            totalComps++; //declared globally
            if( numbers[j] < numbers[j - 1])  {
              temp = numbers[j];
              numbers[j] = numbers[j - gap];
              numbers[j - gap] = temp;
              j = j - gap;
              //had a swap
              totalSwaps++; //declared globally
            }
            else break;
        }

    }
}