Какая польза от последнего--;Вот?

Question

Я новичок в C ++, а также в алгоритме. Может ли кто-нибудь помочь мне объяснить использование (last--;) в середине моего кода?Объяснение, которое я получил, заключается в том, что каждый раз, когда массив проходит, добавляется еще одно значение, поэтому нам нужно поставить туда last--.Я пытался удалить его, это ни на что не влияет, поэтому есть ли необходимость поставить last--;?

void bubbleSort(int array[], int size)
{
    bool swap;
    int temp;
    int last = size - 1;    

    do
    {
        swap = false;

        for (int count = 0; count < last; count++)
        {
            if (array[count] > array[count + 1])
            {               
                temp = array[count];
                array[count] = array[count + 1];
                array[count + 1] = temp;
                swap = true;
            }
        }

        last--; 

    } while (swap != false);
}

Answer 1

Я пытался удалить его, это ни на что не влияет,

Ну, вы тестировали производительность?

Попробуйте огромный массив и измерьте времятребуется сортировка с этой строкой и без нее.

Строка гарантирует, что внутренний цикл не посещает числа, которые уже были отсортированы.

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

Со строкой внутренний цикл будет повторяться сначала size раз, затем size-1, затем size-2 ... В худшем случае это дастsize x (size-1) / 2 итераций, т.е.половина итераций и, следовательно, лучшая производительность.

Answer 2

Это просто оптимизация алгоритма.

После каждого прохода дальняя часть массива сортируется.Так что нам больше не нужно это проверять.Поскольку цикл for основан на limit, добавление limit--; просто сокращает цикл.

Я пытался удалить его, он ни на что не влияет, поэтому есть ли необходимостьпоставить последний -;?

Нет, алгоритм не работает.Это будет работать так же счастливо без него.Это просто оптимизация, которая будет влиять на производительность, особенно с большими массивами.

Answer 3

Цикл for вашего алгоритма зацикливает элементы массива и заменяет соседние элементы, если a[i]>a[i+1].После одного прохода этого цикла последний переданный элемент, безусловно, должен быть самым большим из всех зацикленных элементов, он всплыл.Таким образом, в следующем цикле цикла while цикл for не должен снова рассматривать этот элемент.Это обеспечивается last--.Если вы удалите эту строку, алгоритм сработает, но будет выполнять вдвое больше сравнений, и все они не нужны.