Информатика. Ч.2 Майстренко А.В. - 41 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

меру, для сортировки n элементов требуется выполнить около n
2
/2 сравнений независимо от их перво-
начального расположения, включая даже случай, когда задан полностью упорядоченный ряд. Таким об-
разом, путь к повышению производительности линейной сортировки лежит через уменьшение общего
числа сравнений, для чего необходимо учитывать характер предварительного распределения значений
элементов.
НЕТ
Выход
Вход
ДА
Nomer = 1
Etalon = M
1
k = 2, N, 1
M
k
< Etalon
Etalon = M
k
Вывод
Etalon,
Nomer
Nomer = k
Рис. 23 Нахождение наименьшего значения
одномерного массива и его индекса
Указанный недостаток отсутствует в методе "пузырьковой" сортировки, в основе которого лежит
следующая идея: если каждый элемент ряда находится в правильном положении по отношению к двум
соседним с ним, то весь ряд отсортирован. В соответствии с этой идеей алгоритм "пузырьковой" сор-
тировки заключается в следующих действиях. Берется первая пара рядом стоящих элементов (1-й и 2-й
элементы) и сравнивается между собой. В случае если элементы стоят неверно друг по отношению к
другу, то они меняются местами. Далее таким же образом сравнивается следующая пара (2-й и 3-й эле-
менты) и так до конца ряда, пока не произойдет сравнение предпоследнего и последнего элемента. Та-
кое сравнение всех членов ряда равносильно прохождению одного "пузырька" через ряд. После этого
возвращаются в начало ряда и повторяют сравнение всех элементов (второй "пузырек") и т.д. Описан-
ные действия продолжаются многократно – до тех пор, пока очередной проход через ряд не зарегистри-
рует отсутствие перестановок (для этого можно использовать логическую либо какую другую перемен-
ную). В этом случае сортировка считается законченной. На рис. 25 приведен алгоритм "пузырьковой"
сортировки одномерного массива по убыванию.

Страницы