Задание "интерфейс и сортировка" на 1-ом курсе ВМиК

resident

Кто напомнит ?
Или вообще шикарно будет поиметь отсканенную методичку( совсем тонкая такая )
Попросили в общем помочь

CrazyProg


["Задания практикума на ЭВМ (1 курс)". Методическая разработка (сос-
тавители Н.П.Трифонов и В.Н.Пильщиков). - М.: МГУ, 1992. Задание N3.]

ЗАДАНИЕ N3. "МЕТОДЫ СОРТИРОВКИ" (язык Паскаль).
ПОСТАНОВКА ЗАДАЧИ
Требуется реализовать два метода сортировки, определяемых вариан-
том задания, и провести их экспериментальное сравнение.
Под "сортировкой" понимается упорядочение элементов последователь-
ности x[1], x[2], ..., x[n] (n>1) по неубыванию, т.е. такая переста-
новка элементов, после которой будет выполняться условие x[i]<=x[i+1]
для всех i. В качестве элементов x[i] использовать даты вида 23.11.16,
9.5.97 и т.п.
Сравнение реализованных методов сортировки нужно проводить на од-
них и тех же последовательностях. Следует рассмотреть последователь-
ности разной длины (например, n=10, 20, 50, 100 используя при каждом
n по крайней мере следующие исходные расстановки элементов:
- элементы уже упорядочены по неубыванию;
- элементы упорядочены в обратном порядке (по невозрастанию);
- две случайные расстановки элементов.
Оценку методов производить по следующим трем параметрам:
1) число сравнений элементов последовательности, выполненных в
процессе упорядочения;
2) число перемещений (либо обменов пар элементов, либо пересылок
элементов на новые места - в зависимости от метода выполнен-
ных в процессе упорядочения;
3) время работы процедуры сортировки.
Результаты экспериментов оформить в виде двух таблиц, например,
такого формата:
<название метода сортировки>
----------------------------------------------------------
| n | параметр | номер последовательности | среднее |
| | | 1 2 3 4 | значение |
----------------------------------------------------------
| 10 | сравнения | 9 45 33 25 | 28 |
| | перемещения | ... | ... |
| | время | | |
----------------------------------------------------------
| 20 | сравнения | ... | ... |
| | ... | | |


ВАРИАНТЫ ЗАДАНИЯ (методы сортировки)
Методы 1-5 - простые, но медленные (число сравнений порядка n*n
методы 6-10 - сложные, но быстрые (порядка n*log2(n. Названия мето-
дов даны по книге [1], кроме метода 4. В скобках указаны номера книг
по списку литературы и их страницы, на которых приводятся описания
данных методов.
1) Сортировка простыми вставками ([1] 101-103; [3] 95-96).
2) Сортировка бинарными вставками ([1] 103-104; [3] 97-98).
3) Метод пузырька ([1] 130-132; [2] 27-28; [3] 101-102).
4) Челночная сортировка ([2] 30-31).
5) Сортировка посредством простого выбора ([1] 169-171; [2] 15-16;
[3] 99-100).
6) Метод Шелла ([1] 105-107; [2] 37-40; [3] 105-107).
7) Быстрая сортировка, рекурсивный вариант ([3] 114-117).
8) Быстрая сортировка, нерекурсивный вариант ([1] 140-144; [2]
88-97; [3] 114-121).
9) Сортировка простым двухпутевым слиянием ([1] 198-199; [2]
106-111).
10) Сортировка естественным двухпутевым слиянием ([1] 193- 197; [2]
12-117).


ТРЕБОВАНИЯ К ПРОГРАММЕ
1. Сравнение двух элементов (дат) должно быть реализовано в виде
логической функции, а перемещение (обмен или пересылка) элементов - в
виде процедуры. Как побочный эффект, функция и процедура должны изме-
нять значения (глобальных) счетчиков сравнений и перемещений, соответ-
ственно.
2. Каждый из предложенных методов сортировки реализовать в виде
процедуры от двух параметров: массива (x в котором вначале находится
неупорядоченная последовательность, а в конце работы процедуры должна
оказаться упорядоченная последовательность, и длины (n) упорядочивае-
мой последовательности. Эти процедуры должны правильно работать при
любом n<=100.
Прежде чем проводить эксперименты, следует отладить каждую из этих
процедур (например, на двух-трех последовательностях длины 10).
3. Основная программа должна генерировать все необходимые последо-
вательности, обращаться к процедурам сортировки и печатать таблицы ре-
зультатов.
Замечание: при проведении экспериментов никаких изменений в проце-
дурах сортировки не делать!


СОДЕРЖАНИЕ ОТЧЕТА
1. Постановка задачи (конкретный вариант).
2. Описание каждого из реализованных методов сортировки.
3. Листинг программы на языке Паскаль.
4. Результаты тестирования процедур сортировки.
5. Таблицы с результатами экспериментов.

ЛИТЕРАТУРА
1. Кнут Д. Искусство программирования для ЭВМ. Том 3. - М.: Мир,
1978.
2. Лорин Г. Сортировка и системы сортировки. - М.: Наука, 1983.
3. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989.


КРАТКОЕ ОПИСАНИЕ МЕТОДОВ СОРТИРОВКИ
СОРТИРОВКА ВСТАВКАМИ
Общая идея методов сортировки вставками: в ранее упорядоченную
подпоследовательность x[1], x[2], ..., x[k-1] вставляется x[k] так,
чтобы упорядоченными оказались k первых элементов исходной последова-
тельности.
В зависимости от способа поиска места для элемента q=x[k] различа-
ются следующие методы.
а) ПРОСТЫЕ ВСТАВКИ. Величина q по очереди сравнивается с x[k-1],
x[k-2], ... Если q>x[i], то x[i] сдвигается в (i+1)-ю позицию и q
сравнивается с x[i-1], иначе q вставляется в (i+1)-ю позицию.
б) БИНАРНЫЕ ВСТАВКИ. Величина q сравнивается со средним элементом
подпоследовательности x[1], x[2], ..., x[k-1]. Если q меньше этого
элемента, то место для q ищется тем же способом в левой половине под-
последовательности, а если больше - в правой половине. Когда место для
q будет найдено, правые (от этого места) элементы сдвигаются на одну
позицию вправо, а в освободившуюся позицию вставляется q.
СОРТИРОВКА ОБМЕНАМИ
В методах сортировки обменами переставляются пары элементов, в ко-
торых первый элемент больше второго.
В зависимости от порядка перебора таких пар различаются следующие
методы.
а) МЕТОД ПУЗЫРЬКА. По очереди просматриваются пары соседних эле-
ментов (x[1] и x[2], x[2] и x[3], x[3] и x[4] и т.д.) и в неупорядо-
ченных парах (x[i]>x[i+1]) переставляются элементы; в результате мак-
симальный элемент окажется на своем окончательном месте - в конце пос-
ледовательности. Далее аналогичная процедура применяется ко всем эле-
ментам, кроме последнего. (Замечание: если при очередном просмотре
последовательности не было ни одной перестановки, то последователь-
ность уже упорядочена и следует прекратить сортировку.)
б) ЧЕЛНОЧНАЯ СОРТИРОВКА (метод просеивания). Здесь также сравнива-
ются пары x[i] и x[i+1] (i=1, 2, ... но только до обнаружения неупо-
рядоченной пары x[k]>x[k+1]. В этом случае "неупорядоченный" элемент
x[k+1] начинают сравнивать и переставлять с элементами x[k], x[k-1],
x[k-2], ... до тех пор, пока не окажется упорядоченной подпоследова-
тельность из k+1 первых элементов. Далее возобновляется просмотр впе-
ред: сравниваются пары x[k+1] и x[k+2], x[k+2] и x[k+3] и т.д.
СОРТИРОВКА ВЫБОРОМ
В сортировке выбором берется какой-то элемент и он помещается на
свое окончательное место, и так для каждого элемента.
Основная разновидность этой идеи - сортировка простым выбором: на-
ходится минимальный (максимальный) элемент последовательности и он
переставляется с первым (последним) элементом; с оставшимися элемента-
ми поступают аналогично.

МЕТОД ШЕЛЛА
Пусть k - целое от 1 до n/2. Независимо друг от друга упорядочива-
ются (одним из описанных выше методов) подпоследотельности из элемен-
тов, отстоящих друг от друга на k позиций:
x[i], x[i+k], x[i+2k], ... (i=1, 2, ..., k)
Затем k уменьшается и процесс повторяется заново. Последний шаг должен
выполняться при k=1.
Значение k можно менять разными способами, один из них таков: вна-
чале k равно (целой части от) n/2, а затем k каждый раз уменьшается
вдвое.

БЫСТРАЯ СОРТИРОВКА
Выбирается некоторый элемент (например, средний) и все элементы
последовательности переставляются так, чтобы выбранный элемент оказал-
ся на своем окончательном месте, т.е. чтобы слева от него были только
меньшие или равные ему элементы, а справа - большие или равные. Затем
этот же метод применяется к левой и правой частям последовательности.
(Замечание: если в части оказалось два-три элемента, то упорядочивать
ее следует более простым способом.)
Требуемая перестановка элементов выполняется следующим образом:
последовательность просматривается слева направо, пока не встретится
элемент, больший или равный выбранному, и просматривается справа нале-
во до элемента, меньшего выбранного; эти два элемента переставляются,
после чего просмотр последовательности с обоих концов продолжается.
Быструю сортировку можно реализовать рекурсивно и нерекурсивно.
Во втором случае границы одной из частей (лучше - более длинной) пос-
ледовательности запоминаются в стеке, а другая часть упорядочивается
описанным способом. Когда она будет упорядочена, из стека извлекаются
границы первой части и теперь она упорядочивается тем же способом.

СОРТИРОВКА СЛИЯНИЕМ
Основная идея такой сортировки - разделить последовательность на
несколько уже упорядоченных подпоследовательностей (назовем их "отрез-
ками") и затем объединять их во все более длинные отрезки, пока не по-
лучится единая упорядоченная последовательность. Отметим, что при этом
необходима дополнительная память (массив y[1..n]).
Если на каждом шаге сливаются два отрезка, то такое слияние назы-
вается двухпутевым. В этом случае можно выделить следующие варианты
сортировки слиянием.
а) ПРОСТОЕ СЛИЯНИЕ. Вначале отрезками считаются подпоследователь-
ности из одного элемента, и они сливаются в отрезки из двух элементов
(из x[1] и x[2], из x[3] и x[4], ... которые переносятся в массив y.
На втором этапе соседние отрезки (y[1], y[2] и y[3], y[4]; y[5], y[6]
и y[7], y[8]; ...) объединяются в отрезки из 4 элементов, которые за-
писываются в массив x. На третьем этапе строятся отрезки из 8 элемен-
тов и они заносятся в массив y, и т.д. (Замечание: учесть, что в конце
концов упорядоченные элементы должны оказаться в массиве x).
б) ЕСТЕСТВЕННОЕ СЛИЯНИЕ. Берутся наиболее длинный (по неубыванию)
отрезок в начале массива x и наиболее длинный (также по неубыванию, но
при просмотре справа налево) отрезок в конце массива, и они сливаются
в один отрезок, который записывается в начало массива y. Затем слива-
ются следующие максимально длинные отрезки с обоих концов, и получен-
ный отрезок записывается (справа налево) в конец массива y. Третьи по
порядку отрезки после слияния записываются снова в начало y (вслед за
первым объединенным отрезком четвертые - в конец y (перед вторым об-
ъединенным отрезком) и т.д. Первый этап сортировки оканчивается, когда
все элементы из x будут перенесены в массив y. На втором этапе приме-
няется та же процедура, только массивы x и y меняются ролями. И так
далее.


оно есть.

resident

Спасиба
Оставить комментарий
Имя или ник:
Комментарий: