II. СОРТИРОВКА ЭЛЕМЕНТОВ В МАССИВЕ
Изучить алгоритмы сортировки и по данным блок-схемам составить программы на языке Паскаль. Отработать сортировку по возрастанию и по убыванию элементов. Результаты работы предоставить преподавателю.
Сортировка представляет собой процесс упорядочения элементов в массиве в порядке возрастания или убывания их значений. Например, массив X из n элементов будет отсортирован в порядке возрастания значений его элементов, если X1 ≤ X2 ≤… ≤ Xn, и в порядке убывания, если X1 ≥ X2 ≥… ≥ Xn.
Существует большое количество алгоритмов сортировки, но все они базируются на трех основных:
· сортировка обменом;
· сортировка выбором;
· сортировка вставкой.
Представим, что нам необходимо разложить по порядку карты в колоде. Для сортировки карт обменом можно разложить карты на столе лицевой стороной вверх и менять местами те карты, которые расположены в неправильном порядке, делая это до тех пор, пока колода карт не станет упорядоченной.
Для сортировки выбором из разложенных на столе карт выбирают самую младшую (старшую) карту и держат ее в руках. Затем из оставшихся карт вновь выбрать наименьшую (наибольшую) по значению карту и помещают ее позади той карты, которая была выбрана первой. Этот процесс повторяется до тех пор, пока вся колода не окажется в руках. Поскольку каждый раз выбирается
наименьшая (наибольшая) по значению карта из оставшихся на столе карт, по завершению такого процесса карты будут отсортированы по возрастанию (убыванию).
Для сортировки вставкой из колоды берут две карты и располагают их в необходимом порядке по отношению друг к другу. Каждая следующая карта, взятая из колоды, должна быть установлена на соответствующее место по отношению к уже упорядоченным картам.
Итак, решим следующую задачу.
Задан массив Y из n целых чисел. Расположить элементы массива в порядке возрастания их значений.
Сортировка методом «пузырька»
Сортировка пузырьковым методом является наиболее известной. Ее популярность объясняется запоминающимся названием, которое происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень, и простотой алгоритма.
Сортировка методом «пузырька» использует метод обменной сортировки и
основана на выполнении в цикле операций сравнения и при необходимости
обмена соседних элементов. Рассмотрим алгоритм пузырьковой сортировки более подробно.
Сравним первый элемент массива со вторым, если первый окажется больше
второго, то поменяем их местами. Те же действия выполним для второго и
третьего, третьего и четвертого, i–го и (i+1)–го, (n–1)–го и n–го элементов. В
результате этих действий самый большой элемент станет на последнее (n-е)
место. Теперь повторим данный алгоритм сначала, но последний (n-й) элемент, рассматривать не будем, так как он уже занял свое место. После проведения данной операции самый большой элемент оставшегося массива станет на (n–1)-е место. Так повторяем до тех пор, пока не упорядочим весь массив.
Обратите внимание на то, что для перестановки элементов (блок 4) используется буферная переменная b, в которой временно хранится значение элемента, подлежащего замене.
Совет: Для перестановки элементов в массиве по убыванию их значений необходимо при сравнении элементов массива заменить знак > на <.
Сортировка выбором
Алгоритм сортировки выбором приведен в виде блок-схемы. Найдем в массиве самый большой элемент (блоки 3–7) и поменяем его местами с
последним элементом (блок 8). Повторим алгоритм поиска максимального элемента, уменьшив количество просматриваемых элементов на единицу (блок 9), и поменяем его местами с предпоследним элементом (блоки 3–7). Описанную выше операцию поиска проводим до полного упорядочивания элементов в массиве. Так как в блоке 9 происходит изменение переменной n, то в начале
алгоритма ее значение необходимо сохранить (блок 1).
Совет. Для упорядочивания массива по убыванию необходимо перемещать
минимальный элемент.
Сортировка вставкой
Сортировка вставкой заключается в том, что сначала упорядочиваются два
элемента массива. Затем делается вставка третьего элемента в соответствующее место по отношению к первым двум элементам. Четвертый элемент помещают в список из уже упорядоченных трех элементов. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены.
Рассмотрим следующий пример. Пусть известно, что в массиве из восьми элементов первые шесть уже упорядочены, а седьмой элемент нужно вставить между вторым и четвертым. Сохраним седьмой элемент во вспомогательной переменной, а на его место запишем шестой. Далее пятый переместим на место шестого, четвертый на место пятого, а третий на место четвертого, тем самым, выполнив сдвиг элементов массива на одну позицию вправо. Записав содержимое вспомогательной переменной в третью позицию, достигнем нужного результата.
Составим блок–схему алгоритма (рис. 6.11), учитывая, что возможно
описанные выше действия придется выполнить неоднократно.
Организуем цикл для просмотра всех элементов массива, начиная со второго
(блок 4). Сохраним значение текущего i–го элемента во вспомогательной переменной X, так как оно может быть потеряно при сдвиге элементов (блок 5) и присвоим переменной j значение индекса предыдущего (i–1)–го элемента
массива (блок 6). Далее движемся по массиву влево в поисках элемента меньшего, чем текущий и пока он не найден сдвигаем элементы вправо на одну позицию. Для этого организуем цикл (блок 7), который прекратиться, как только будет найден элемент меньше текущего. Если такого элемента в массиве не найдется и переменная j станет равной нулю, то это будет означать, что достигнута левая граница массива, и текущий элемент необходимо установить в первую позицию.
Смещение элементов массива вправо на одну позицию выполняется в блоке 8, а изменение счетчика j в блоке 9. Блок 10 выполняет вставку текущего элемента в соответствующую позицию.
Задания для самостоятельной работы
Номер варианта определяем следующим образом. Находим остаток от деления вашего номера в списке группы на десять и добавляем единицу.