как работает это пузырьковая сортировка

Question

#include<iostream>
#include"Header.h"
using namespace std;
#define N 80
void funcsortupgrade2(int array[], int size) {
    funcrand(array, N);
    int temp;
    size_t n=N;
    do {
        size_t newn = 0;
        for (size_t i = 1; i < n; i++) {
                if (array[i-1] > array[i]) {
                    temp = array[i];
                    array[i] = array[i - 1];
                    array[i - 1] = temp;
            }
                newn = i;
        }
        n = newn;
    } while (n > 1);
}

Answer 1

Это обычная пузырьковая сортировка, в которой вместо внешнего цикла for использован do-while.

Верхняя граница прохода n снижается от N до единицы, а обновляется она не в заголовке for, а просто как индекс предпоследнего обрабатываемого во внутреннем цикле элемента.

После каждого внутреннего цикла самый большой элемент текущей части встаёт на свое окончательной место в конце (пузырёк "всплывает")

Выгод по сравнению с двумя for нет.

Если newn = i; перенести выше фигурной скобки, то это даст несколько оптимизированный вариант - запоминается позиция последнего обмена, значит все элементы с бОльшими индексами уже на своих местах, и можно уменьшить обрабатываемую область не на единицу, а на несколько элементов.

БЛОГ НА HUSL

как работает это пузырьковая сортировка

Ответы (1 шт):