Сортировка методом прямого выбора

Сортировка методом прямого выбора сортировки одномерных массивов и поиска элементов 1. Сортировка методом прямого выбора методом «пузырька» В основе алгоритма лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим, и если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива всплываюта элементы с большим значением — к концу массива тонут. Поэтому данный метод сортировки обменом иногда называют методом "пузырька". Этот процесс повторяется столько раз, сколько элементов в массиве, минус единица. Вместе с тем возможно, что массив реально будет упорядочен за меньшее число циклов. Например, последовательность чисел 5 1 2 3 4, если ее рассматривать как представление массива, будет упорядочена за один цикл, и выполнение оставшихся трех циклов не будет сортировка методом прямого выбора смысла. Поэтому в программу введена логическая переменная changed, которой перед выполнением очередного цикла присваивается значение FALSE. Процесс сортировки цикл repeat завершается, если после выполнения очередного цикла проверки соседних сортировка методом прямого выбора массива цикл for ни один элемент массива не был обменен с соседним, и, следовательно, массив уже упорядочен. Сортировка массива методом пузырька - медленная, но если скорость не главное, можно применить и его. Алгоритм очень прост - если два соседних элемента расположены не по порядку, то меняем их местами. Так повторяем до тех пор, пока в очередном проходе не сделаем ни одного обмена, т. В массиве А сортировка методом прямого выбора. Для того, чтобы не потерять элементстоящий на первом местеэтот элемент устанавливается на место минимального. Затем в усеченной последовательности, сортировка методом прямого выбора первый элемент, отыскивается минимальный элемент и ставится на второе место и так далее n-1 раз пока не встанет на свое место предпоследний n-1 элемент массива А, сдвинув максимальный элемент сортировка методом прямого выбора самый конец. Рассмотрим алгоритмическое решение задачи на примере сортировки некоторого массива значений по возрастанию. В соответствии с вышеописанным методом нам необходимо несколько раз выполнять операции поиска минимального элемента и его перестановку с другим элементом, то есть потребуется сортировка методом прямого выбора раз просматривать элементы массива с этой целью. Количество просмотров элементов массива согласно описанию модифицированного метода простого сортировка методом прямого выбора равно n-1, где n- количество элементов массива. Таким образом, можно сделать вывод, что проектируемый алгоритм сортировки будет содержать цикл, в котором будет выполняться поиск минимального элемента и его перестановка с другим элементом. Обозначим через i - счетчик сортировка методом прямого выбора просмотров элементов массива изобразим обобщенный алгоритм сортировки на рис. Обобщенный алгоритм сортировки массива модифицированным методом простого выбора Отметим, что для перестановки элементов местами необходимо знать их порядковые номера, алгоритм перестановки элементов массива был рассмотрен ранее см. Алгоритмы ввода исходного массива и вывода этого же массива после сортировки изображены на рисунках 16 и 24 соответственно. Сортировка методом прямого выбора поиска в массиве минимального элемента и его номера будет аналогичен рассмотренному в примере 10 алгоритму поиска максимального элемента, который представлен на рис. Однаков этом алгоритме будут внесены изменения. Для тогочтобы определить какие изменения следует внести рассмотрим выполнение сортировки данным методом с акцентом на поиск минимального элемента на конкретном примере. Пусть исходный массив содержит 5 элементов 2,8,1,3,7. Количество просмотров согласно модифицированному методу простого выбора будет равно 4. Покажем в таблице 7, как будет изменяться исходный массив на каждом просмотре. Пример сортировки Номер просмотра массива i Исходный массив Минимальный элемент Переставляемый элемент Массив после перестановки Номер Сортировка методом прямого выбора Номер Значение 1 2,8,1,3,7 3 1 1 2 1,8,2,3,7 2 1, 8,2,3,7 3 2 2 8 1, 2,8,3,7 3 1,2, 8,3,7 4 3 3 8 сортировка методом прямого выбора, 3,8,7 4 1,2,3, 8,7 5 7 4 8 1,2,3,7,8 Из данных, приведенных в таблице 7, следует, что поиск минимального значения в массиве на каждом просмотре осуществляется в сокращенном массиве, который сначала начинается с первого элемента, а на последнем просмотре массив, в котором ищется минимальный элемент начинается уже с четвертого или n-1 элемента. При этом можно заметить, что номер первого элемента массива для каждого поиска и перестановки совпадает с номером просмотра i. Введем следующие обозначения : К- номер минимального элемента, J - номер элемента массива, М и А К - одно и тоже значение минимального элемента массива, i - номер переставляемого с минимальным элемента, А i - сортировка методом прямого выбора переставляемого элемента. Тогда циклический алгоритм сортировки модифицированным методом простого выбора будет выглядеть следующим образом рис. Алгоритм сортировки массива модифицированным методом простого выбора В этом алгоритме 2 цикла, внутренний цикл выделен цветом. Синтаксис - Сортировка массива методом прямого выбора Сортировка массива методом сортировка методом прямого выбора выбора Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так: 1. Просматривая массив от первого элемента, найти минимальный элемент и поместить его на место первого элемента, а первый — на место минимального. Просматривая массив от второго элемента, найти минимальный элемент и поместить его на место второго элемента, а второй — на место минимального. И так далее до предпоследнего элемента. Ниже представлена программа сортировки массива целых чисел по возрастанию procedure TForm1. Заключается он в следующем: при каждом просмотре массива находим минимальный элемент и меняем местами его с первым на первом проходе, со вторым - на втором и т. Не забудьте только, что первый элемент массива должен иметь индекс 0. Суть её в том, что на n-ном шаге мы имеем упорядоченную часть массива из n элементов, и следующий элемент встаёт на подходящее ему место. Имейте в виду - первый индекс массива - 0. Следующая функция возвращает индекс заданного элемента массива. Её аргументы: массив с первым индексом 0, количество элементов в массиве искомое число. Если число не найдено, возвращается -1. Затем следует новая итерация цикла, и так повторяется до тех пор, пока не найдётся нужное число, или Up не станет больше Doun.

См. также