Лабораторная работа №3 Тема. Простейшие классы и объекты и сортировка массивов

Метод простого выбора
В исходной последовательности отыскивается наименьший элемент. Этот элемент записывается в выходной массив. Найденное минимальное значение помечается признаком и не участвует в дальнейшей сортировке. Этот процесс необходимо повторить N раз (N - размерности исходного массива).
Метод парных перестановок
Метод заключается в попарном сравнении элементов и их обмене ‚, если они стоят не в порядке возрастания (убывания). Просмотр всего массива и сравнение пар повторяется до тех пор, пока не будут отсортированы все элементы, т.е. во время очередного просмотра не произойдет ни одной перестановки.
Метод "всплывающего пузырька"
Метод получил свое название в результате следующей аналогии. Если элементы в вертикально расположенном массиве представить себе пузырьками в резервуаре с водой, обладающими весом, равным значению элемента, то каждый просмотр массива и перестановки элементов будут рассматриваться как "всплывание" пузырька на соответствующий его весу уровень. В последовательности сравниваются два соседних элемента, например, К и К+1, допустим, произошла перестановка этих элементов. В этом случае далее делается проверка для всех элементов от К-го до первого, т.е. движение "вверх" по последовательности с перестановкой соответствующих элементов. Чтобы не просматривать массив каждый раз с самого начала, можно запомнить место (индекс) последнего обмена. Все пары соседних элементов с индексами, меньшими запомненного, уже расположены в нужном порядке.
Метод шейкер-сортировки
В последовательности во время первого просмотра ищется минимальный элемент и ставится в начало массива. Далее, во время второго просмотра усеченного массива (исключен из рассмотрения первый элемент) находится максимальный элемент и ставится в конец массива. Затем следующим просмотром определяется минимальный элемент и ставится на свое место и так далее, постоянно чередуя поиск минимума и максимума и уменьшая зону просмотра с краев.
Сортировка методом Шелла
Сортировка методом Шелла подобна сортировке методом парных перестановок в том смысле, что идет сравнение и, в нужном случае, перестановка пар элементов. Но сравниваются не рядом стоящие элементы, а те, которые находятся друг от друга на расстоянии D. Эта величина первоначально равна D=(N+1)/2 ( N - количество элементов сортируемой последовательности). После каждого просмотра расстояние между элементами (D) уменьшается:
D(i+1)=floor((D(i)+1/2)
Функция floor возвращает округленное в сторону уменьшения значение выражения. Последний просмотр осуществляется при О=1.