Презентация "Сортировка методом пузырька"

Сортировка массива методом пузырька

Сортировка пузырьком - это метод сортировки массивов и списков путем последовательного сравнения и обмена соседних элементов, если предшествующий оказывается больше последующего.

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

Пусть имеется список [6, 12, 4, 3, 8].
За первую итерацию внешнего цикла число 12 переместится в конец. Для этого потребуется 4 сравнения во внутреннем цикле:
6 > 12? Нет
12 > 4? Да. Меняем местами
12 > 3? Да. Меняем местами
12 > 8? Да. Меняем местами
Результат: [6, 4, 3, 8, 12]
За вторую итерацию внешнего цикла число 8 переместиться на предпоследнее место. Для этого потребуется 3 сравнения:
6 > 4? Да. Меняем местами
6 > 3? Да. Меняем местами
6 > 8? Нет
Результат: [4, 3, 6, 8, 12]

На третьей итерации внешнего цикла исключаются два последних элемента. Количество итераций внутреннего цикла равно двум:
4 > 3? Да. Меняем местами
4 > 6? Нет
Результат: [3, 4, 6, 8, 12]
На четвертой итерации внешнего цикла осталось сравнить только первые два элемента, поэтому количество итераций внутреннего равно единице:
3 > 4? Нет
Результат: [3, 4, 6, 8, 12]

Сортировка массивов. Метод выбора

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

Двоичный поиск в массиве

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

Описание алгоритма
Находится средний элемент последовательности. Для этого первый и последний индексы связываются с переменными, а индекс среднего элемента вычисляется.
Значение среднего элемента сравнивается с искомым значением. В зависимости от того, больше оно или меньше значения среднего элемента, дальнейший поиск будет происходить только в левой или только в правой половинах массива. Если значение среднего элемента оказывается равным искомому, поиск завершается.
Иначе одна из границ исследуемой последовательности сдвигается. Если искомое значение больше значения среднего элемента, то нижняя граница сдвигается за средний элемент на один элемент справа. Если искомое значение меньше значения среднего элемента, то верхняя граница сдвигается на элемент перед средним.
Снова находится средний элемент теперь уже в выбранной половине. Описанный выше алгоритм повторяется для данного среза.