Как я узнаю, что приращения счетчика находятся в правильном месте, чтобы отслеживать количество сравнений ~ C++?

Question

// Вопрос решен. Я запутался в том, где добавить счетчики, чтобы сообщить количество сравнений. Он всегда остается на фиксированном номере и никогда не меняется. Предположим, что вектор содержит двузначные случайные числа при каждом запуске программы. //

Изменить: новый вопрос. Я не уверен, что приращения счетчика находятся в правильном месте или нет для сортировки вставки и сортировки выделения. Код вставлен по безопасной ссылке: http://ideone.com/Bk90du

int insertionSort(vector<int> &v)
{
// Variables
int temp, i, j, counter;
counter = 0;

for (i = 1; i < v.size(); i++)
{
        temp = v[i];

        j = i-1;
        while(temp < v[j] && j >= 0)
        {
            v[j+1]=v[j];
            j--;
            counter++; // tracking # of comparisons. 

        }
        v[j+1]=temp;
}
return counter; // return counter 
}

Answer 1

Согласно (удаленному) комментарию, это main():

int main() {
    int numCount;
    vector<int> myVector2(myVector);
    insertionSort(myVector2);
    cout << endl << endl;
    cout << "Vector after Insertion Sort: ";
    printVector(myVector2);
    cout << endl << endl;
    numCount = insertionSort(myVector2);
    cout << "Number of comparisons: " << numCount;

Вы сортируете один и тот же вектор два раза и печатаете счетчик сравнения второго прогона сортировки. Когда вектор уже отсортирован, количество сравнений равно количеству элементов в векторе, потому что не нужно выполнять никаких действий.

Чтобы получить истинное количество сравнений, измените main() чтобы:

int main() {
    int numCount;
    vector<int> myVector2(myVector);
    numCount = insertionSort(myVector2);
    cout << endl << endl;
    cout << "Vector after Insertion Sort: ";
    printVector(myVector2);
    cout << endl << endl;
    cout << "Number of comparisons: " << numCount;

Answer 2

Не зная, каковы ваши тесты, невозможно прокомментировать количество выполненных сравнений. Если все случаи имеют похожие атрибуты, вполне возможно, что код ведет себя так, как и должен.

РЕДАКТИРОВАТЬ: следующее добавлено в ответ на заявление OP в комментариях о том, что контрольные примеры представляют собой векторы со 100 случайно сгенерированными двузначными элементами.

Если, как вы сказали в комментариях, в ваших тестах используются векторы со 100 случайными двузначными значениями, тогда значение counter будет зависеть от того, насколько "несортированы" элементы (с минимально возможным значением, связанным с количеством элементов). Если предположить, что все ваши тесты имеют одинаковый размер, то единственным способом counter будет то же самое, если векторы сортируются аналогично ДО вызова вашей функции. Например, если все ваши векторы предварительно отсортированы в порядке возрастания и имеют одинаковый размер, каждый тестовый пример даст одинаковое возвращаемое значение. Точно так же, если все ваши векторы предварительно отсортированы в порядке убывания и имеют одинаковый размер, каждый тестовый пример даст одно и то же возвращаемое значение (хотя и отличается от возвращаемого значения, если они изначально находятся в порядке возрастания).

По этой причине я не верю вашему комментарию о том, что тестовые случаи являются случайными. Они, вероятно, предварительно отсортированы (или, возможно, частично отсортированы) каким-либо образом. Например, вы могли бы вызывать свою функцию дважды для каждого тестового случая и выводить только значение count после второго вызова..... когда вектор (если ваш код ведет себя как следует) уже предварительно отсортирован.

Конец Править

Тем не менее, переменная counter в вашем коде накапливается количество раз тело while цикл выполнен. Это не имеет никакого отношения к количеству выполняемых сравнений, поскольку в теле этого цикла сравнение не выполняется. Это связано с количеством вставок, а не с количеством сравнений.

Если под "сравнением" вы хотите подразумевать оценку выражения temp < v[j] (в отличие от других выражений, таких как i < v.size() или же j >= 0(что также можно назвать сравнением в вашем коде), тогда вы можете подумать о том, чтобы сделать что-то вроде

while (++counter && temp < v[j] && j >= 0)

и удаление увеличения counter из тела петли.

поскольку counter инициализируется в ноль, это будет считать количество раз temp < v[j] оценивается (++counter всегда будет давать ненулевой результат). Обратите внимание, что, так как temp < v[j] может быть ложным, он не будет считать количество раз j >= 0 вычисляется