36. Алгоритмы сортировки. Древесная сортировка. Сортировка методом пузырька.

При использовании этой сортировки в массиве постоянно поддерживается такой порядок, при котором максимальный элемент всегда будет оказываться в A[1]. Сортировка называется древесной, потому что в этом методе используется структура данных, называемая двоичным деревом. При чем используется представление дерева в виде массива и при сортировке используется тот же способ расположения вершин дерева в массиве.

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

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

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

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

37. Алгоритмы сортировки. Быстрая сортировка (Хоара). Сортировка слиянием.

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

Этот алгоритм является ярким примером реализации принципа «разделяй и властвуй». Как показывают теоретические выкладки, наиболее эффективным в общем случае оказывается разделение задачи на две равные по сложности части.

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

Разделение массива на две части производится следующим образом. Устанавливают один курсор на левую границу массива, а второй – на правую границу. Затем осуществляют перемещение курсоров навстречу друг другу до тех пор, пока они не пересекутся. При перемещении курсоров сравнивают значения текущих элементов со «средним». Находят левый текущий элемент, больший «среднего», и правый текущий элемент, меньший «среднего» (т. е. элементы, которые находятся «не на своем месте»). Осуществляют обмен этих элементов.

Выбор «среднего» – задача непростая, так как требуется, не производя сортировку, найти элемент со значением максимально близким к среднему.

Сортировка слиянием

Этот метод сортирует массив последовательным слиянием пар уже отсортированных подмассивов.

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