Как мне узнать количество сравнений?

Рейтинг: 0Ответов: 2Опубликовано: 20.03.2023

Сортировка Шелла. Вопрос в том, как мне корректно посчитать количество сравнений, которое происходит в цикле. Если внутри прибавлять сравнение, то это не корректно, так как если условие не выполнится, то и прибавляться ничего не будет, а сравнение то произошло.

static int shellSort(T** mass, int massSize)
{
    int i, j, h, n = 0;
    for (h = 1; h <= massSize / 9; h = h * 3 + 1);  
    while (h >= 1)
    {
        for (i = h; i < massSize; i++)
        {
            for (j = i - h; j >= 0 && *mass[j] > *mass[j + h]; j -= h)
            {   
                n += 1;
                T* pt = mass[j]; mass[j] = mass[j + h]; mass[j + h] = pt;
            }
        }
        h = (h - 1) / 3;
    }
    return n;
}

n - это переменная, которая должна возвращать количество сравнений.

Ответы

▲ 0Принят

Видимо, вы хотите получить сравнения в n? тогда замените

for (j = i - h; j >= 0 && *mass[j] > *mass[j + h]; j -= h, cmpCount++)
{
     n += 1;

на

for (j = i - h; j >= 0 && (++n, *mass[j] > *mass[j + h]); j -= h, cmpCount++)
{

чтобы n увеличивалось только при выполнении сравнения

▲ 0

Внесите сравнение *mass[j] > *mass[j + h] внутрь цикла, после n++. По результатам сравнения делайте break

Отмечу, что это не совсем сортировка Шелла, т.к. внутри используются перестановки, как в пузырьке, а должен быть сдвиг, как во вставках.