Как я могу реализовать этот пузырь сортировки по-другому?

Question

Я собираюсь реализовать сортировку пузырьков.У меня есть следующий код, который я написал, который использует цикл for внутри цикла do.Как я могу превратить это в пузырьковую сортировку, которая использует две for петли?

Вот мой код:

do {
    switched = false;
    for (int i = 1; i < size; i++) {
        if (a[i] < a[i-1]) {
            int temp = a[i];
            a[i] = a[i-1];
            a[i-1] = temp;
            switched = true;
        }
    }
} while (switched);

(Это помеченное домашнее задание, но оно готовится к финальному экзамену, а не домашнее задание.)

Answer 1

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

for(int x = size; x >= 0; x--) {
    bool switched = false;
    for(int i = 1; i < x; i++) {
        if(blah) {
            // swap code here
            switched = true;
        }

    }
    if(!switched) break; // not the biggest fan of this but it gets the job done
}

Answer 2

Немного обязателен, но эй, вы просили об этом:

for(bool switched=true; switched;)
{
    switched = false;
    for (int i = 1; i < size; i++) {
        if (a[i] < a[i-1]) {
            int temp = a[i];
            a[i] = a[i-1];
            a[i-1] = temp;
            switched = true;
        }
    }
}

Два для циклов ...

Answer 3

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

for (int x = 0; x < size; x++ )
{
    switched = false;
    for (int i = 1; i < size; i++)
    {
        if (a[i] < a[i - 1])
        {
            int temp = a[i];
            a[i] = a[i - 1];
            a[i - 1] = temp;
            switched = true;
        }
    }

    if(switched)
    {
        break;
    }
}

Answer 4

Простое улучшение в пузырьковой сортировке заключается в запоминании местоположения last , где произошел обменПосле каждого прохода элементы за этой точкой сортируются.В следующий раз через цикл только итерируйте до предыдущей максимальной отметки.

void bubble_sort(int *arr, int size)
{
    for (int hwm; size > 1; size = hwm)
    {
        hwm = 0;
        for (int i = 1; i < size; ++i)
        {
            if (arr[i] < arr[i-1])
            {
                std::swap(arr[i], arr[i-1]);
                hwm = i;
            }
        }
    }
}

Answer 5

Действительно глупый способ использовать два цикла for был бы следующим:

for(bool switched=true;switched;)
{
    switched=false;
    for(int i=1; i<size; ++i)
    {
        if (a[i] < a[i-1]) 
        {
            int temp = a[i];
            a[i] = a[i-1];
            a[i-1] = temp;
            switched = true;
        }
    }
}

Более серьезный ответ мог бы быть таким, как показано ниже ... но теперь, когда я думаю об этом, это, вероятно, не пузырьковая сортировка.:

for(int i=0; i<(size-1); ++i)
{
    for(int j=(i+1); j<(size-1); ++j)
    {
        if(a[i]>a[j])
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
}

Answer 6

Подумайте о максимальном числе циклов do.

Answer 7

Первый полный проход через цикл (то есть первая итерация вашего внешнего do цикла) гарантированно поместит самый большой элемент в позицию a[size - 1].(Вы понимаете, почему?) Следующий полный проход гарантированно не изменит этого, и , кроме того, чтобы поместить второй по величине элемент в положение a[size - 2].(Опять понимаете почему?) И так далее.Таким образом, для первого прохода необходимо i, чтобы перейти от 1 до size - 1, а второму - i, чтобы перейти от 1 до size - 2, для третьего - i, чтобы перейти от 1 до size - 3 и т. д.В целом, вам нужно максимум size - 1 проходов (последний проход просто покрывает позицию 1 и сравнивает a[1] с a[0], чтобы убедиться, что самый маленький элемент на месте).

Итак, вашexternal for -loop должен изменяться max_i, изначально установлен на size - 1 и заканчиваться на 1, а ваш внутренний for -loop должен варьироваться i от 1 до max_i.

Answer 8

Вы можете запустить внутренний цикл size раз вместо проверки switched, имея внешний цикл for(int j=0; j<size; ++j). Чтобы сделать его немного менее неэффективным, вы можете каждый раз сокращать внутреннюю петлю на 1 шаг.