Вопросы (1110763), страница 3
Текст из файла (страница 3)
Под одним «перемещением» в методах 1, 2, 9 и 10 понимается пересылка элемента на новое место, а в остальных методах — перестановка значенийдвух элементов.)2.Каждый из предложенных методов сортировки должен быть реализован в видепроцедуры от двух параметров: массива (X), в котором вначале находится неупорядоченная последовательность, а в конце работы процедуры должна оказатьсяупорядоченная последовательность, и длины (n) упорядочиваемой последовательности. Эти процедуры должны правильно работать при любом n ≤ 100.Прежде чем проводить эксперименты, следует отладить каждую из этих процедур(например, на двух-трех последовательностях длины 10).Основная программа должна генерировать все необходимые последовательности,обращаться к процедурам сортировки и печатать таблицы результатов.(Замечание.
Для генерации случайных последовательностей можно использоватьфункцию random(k) языка Турбо Паскаль, которая при каждом обращении к ней вкачестве своего значения выдает новое случайное целое число из отрезка [0, k-1].)3.4. ЛИТЕРАТУРА[1]. Кнут Д. Искусство программирования для ЭВМ. Т.3. — М.: Мир, 1978.[2].
Лорин Г. Сортировка и системы сортировки. — М.: Наука, 1983.[3]. Вирт Н. Алгоритмы и структуры данных. — М.: Мир, 1989.[4]. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. — М.:Наука, 1988.10Методическое пособие[5]. Епанешников А.М., Епанешников В.А. ПрограммированиеPascal 7.0 — М.: «ДИАЛОГ-МИФИ», 2000.всредеTurbo3.5. КРАТКОЕ ОПИСАНИЕ МЕТОДОВ СОРТИРОВКИСОРТИРОВКА ВСТАВКАМИИдея методов сортировки вставками состоит в том, что в ранее упорядоченную подпоследовательность X1, X2, ..., Xk − 1 вставляется Xk так, чтобы упорядоченными оказались уже k первых элементов исходной последовательности.
В зависимости от способапоиска места для элемента q = Xk различаются следующие методы.1) ПРОСТЫЕ ВСТАВКИ. Если q < Xk − 1, то величина q по очереди сравниваетсяс Xk − 1, Xk − 2, ..., пока не будет найдена такая пара элементов Xi − 1 и Xi, что Xi− 1 ≤ q < Xi.
Это означает, что местом для q является i-я позиция. Поэтомуэлементы Xi, …, Xk − 1 сдвигаются на одну позицию вправо и в освободившуюся i-ю позицию вставляется q.2) БИНАРНЫЕ ВСТАВКИ. Величина q сравнивается со средним элементомподпоследовательности X1, X2, ..., Xk − 1. Если q меньше этого элемента, то место для q ищется тем же способом в левой половине подпоследовательности,иначе - в правой половине. Когда место для q будет найдено, правые (от этого места) элементы сдвигаются на одну позицию вправо, а в освободившуюся позицию вставляется q.СОРТИРОВКА ОБМЕНАМИВ методах сортировки обменами переставляются элементы неупорядоченных пар, т.е.таких пар, в которых левый элемент больше правого.
В зависимости от порядка перебора пар различаются следующие методы.1) МЕТОД ПУЗЫРЬКА. По очереди просматриваются пары соседних элементов (X1 и X2, X2 и X3, X3 и X4 и т.д.) и в неупорядоченных парах (Xi > Xi+1) переставляются элементы; в результате просмотра всей последовательности еемаксимальный элемент окажется на своем окончательном месте - в конце.Далее аналогичная процедура применяется ко всем элементам последовательности, кроме последнего. (Замечание: если при очередном просмотрепоследовательности не было ни одной перестановки, то последовательностьуже упорядочена и потому следует прекратить сортировку.)2) ЧЕЛНОЧНАЯ СОРТИРОВКА (метод просеивания). Здесь также сравниваются пары X1 и X2, X2 и X3 и т.д., но только до обнаружения неупорядоченнойпары Xk > Xk+1. В этом случае осуществляется «движение назад»: сравниваются и переставляются пары Xk + 1 и Xk, Xk и Xk − 1 и т.д.
до тех пор, пока Xk + 1не попадет на свое место, т.е. пока не окажется упорядоченной подпоследовательность из k + 1 первых элементов. Далее возобновляется «движениевперед»: сравниваются пары Xk + 1 и Xk + 2, Xk + 2 и Xk + 3 и т.д.СОРТИРОВКА ПРОСТЫМ ВЫБОРОМВ сортировке простым выбором находится минимальный (максимальный) элемент последовательности и он переставляется с первым (последним) элементом.
Далее аналогичная процедура применяется ко всем элементам, кроме первого (последнего). И такдалее.11Трифонов Н.П., Пильщиков В.Н. Практикум на ЭВММЕТОД ШЕЛЛАПусть k — целое от 1 до n/2. Независимо друг от друга упорядочиваются (одним изописанных выше методов, например, простых вставок) подпоследовательности из элементов, отстоящих друг от друга на k позиций:Xi, Xi + k, Xi + 2k, Xi + 3k, ... (i = 1, 2, ..., k)Затем k уменьшается и процесс повторяется заново.
Последний шаг обязательно должен быть выполнен при k = 1.Значение k можно менять разными способами, один из них таков: вначале k равно (целой части от) n/2, а затем k каждый раз уменьшается вдвое.БЫСТРАЯ СОРТИРОВКАВыбирается некоторый элемент (например, средний) и все элементы последовательности переставляются так, чтобы выбранный элемент оказался на своем окончательномместе, т.е. чтобы слева от него были только меньшие или равные ему элементы, а справа — только большие или равные. Затем этот же метод применяется к левой и правойчастям последовательности, на которые ее разделил выбранный элемент. (Замечание:если в части оказалось два-три элемента, то упорядочивать ее следует более простымспособом.)Требуемая перестановка элементов выполняется так. Выбранный элемент копируется внекоторую переменную q. Последовательность просматривается слева направо, пока невстретится элемент, больший или равный q, а затем просматривается справа налево доэлемента, меньшего или равного q.
Оба этих элемента меняются местами, после чегопросмотры с обоих концов последовательности продолжаются со следующих элементов, и т.д. В итоге выбранный элемент окажется в той позиции, где просмотры сошлись, это и есть его окончательное место.Быструю сортировку можно реализовать рекурсивно и нерекурсивно. Во втором случаеграницы одной из двух частей (лучше - более длинной), на которые выбранный элементразделил последовательность, запоминаются в стеке, а другая часть упорядочиваетсяописанным способом.
После ее упорядочения из стека извлекаются границы первойчасти, и теперь уже она упорядочивается.СОРТИРОВКА СЛИЯНИЕМОсновная идея такой сортировки — разделить последовательность на уже упорядоченные подпоследовательности (назовем их «отрезками») и затем объединять эти отрезкиво все более длинные упорядоченные отрезки, пока не получится единая упорядоченная последовательность.
Отметим, что при этом необходима дополнительная память(массив Y [1..n]).Различаются следующие варианты сортировки слиянием.1) ПРОСТОЕ СЛИЯНИЕ. Считается, что вначале отрезки состоят только из одного элемента, и они сливаются в отрезки из двух элементов (из X1 и X2, из X3и X4, ...), которые переносятся в массив Y. На втором этапе соседние двухэлементные отрезки (Y1, Y2 и Y3, Y4; Y5, Y6 и Y7, Y8; ...) объединяются в отрезкииз 4 элементов, которые записываются в массив X. На третьем этапе строятсяотрезки из 8 элементов, и они заносятся в массив Y, и т.д.2) ЕСТЕСТВЕННОЕ СЛИЯНИЕ. Берутся наиболее длинный (по неубыванию)отрезок в начале массива X и наиболее длинный (также по неубыванию, нопри просмотре справа налево) отрезок в конце массива, и они сливаются в12Методическое пособиеодин отрезок, который записывается в начало массива Y.
Затем сливаютсяследующие максимально длинные отрезки с обоих концов, и полученный отрезок записывается (справа налево) в конец массива Y. Третьи по порядку отрезки после слияния записываются снова в начало Y (вслед за первым объединенным отрезком), четвертые — в конец Y (перед вторым объединеннымотрезком) и т.д. Первый этап сортировки оканчивается, когда все элементыиз X будут перенесены в массив Y. На втором этапе применяется та же процедура, только массивы X и Y меняются ролями.
И так далее.Замечание: в обоих вариантах следует учитывать, что в конце концов упорядоченныеэлементы должны оказаться в массиве X.13Трифонов Н.П., Пильщиков В.Н. Практикум на ЭВМЗадание 4. ЯЗЫК ПАСКАЛЬ. ИНТЕРФЕЙСПРОГРАММЫ СОРТИРОВКИ.4.1. ПОСТАНОВКА ЗАДАЧИТребуется дополнить программу сортировки, реализованную в задании 3, подсистемойдиалогового взаимодействия с пользователем (интерфейсом), которая с помощью экранных окон, меню и других средств упрощает общение пользователя с этой программой. Работу с экраном подсистема должна осуществлять в текстовом режиме.Объединенная система должна предусматривать следующие возможности.— Пользователь должен иметь возможность выбрать из нескольких предъявленныхему методов сортировки тот метод, которым затем будут упорядочиваться последовательности.— Пользователь должен иметь возможность задавать свою длину последовательностей, которые будут упорядочиваться выбранным методом.— В системе должна быть предусмотрена возможность работы в двух режимах —отладки и счета.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
