ЛОЙКО В И СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ КРАСНОДАР 2004 261 С 12

7.Вывести по алфавиту марки машин, которые должны быть отремонтированы раньше всех (дата конца ремонта меньше 01.08.96).
8.Вывести по возрастанию номера машин марки "Жигули".
9.Вывести по алфавиту имена владельцев, чьи машины не ремонтировались с прошлого года.
10.Вывести машины, которые надо отремонтировать к следующему месяцу по возрастанию даты их последнего ремонта.
11. Вывести по алфавиту в обратном порядке имена владельцев, количество предыдущих ремонтов машин которых больше трех.
12. Вывести по убыванию номера машин марки "Мерседес".

Лабораторная работа № 7. "СОРТИРОВКА МЕТОДОМ ПРЯМОГО ВЫБОРА"

Цель работы: исследовать и изучить сортировки методом прямого выбора.

Задача работы: овладеть навыками написания программ для сортировки методом прямого выбора на языке программирования ПАСКАЛЬ .

Порядок работы :
* изучить описание лабораторной работы;
* по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
* написать программу на языке ПАСКАЛЬ;
* отладить программу;
* решить задачу;
* оформить отчет.

Краткая теория

В общем сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки облегчить последующий поиск элементов в таком отсортированном множестве. Это почти универсальная, фундаментальная деятельность. Мы встречаемся с отсортированными объектами в телефонных книгах, в списках подоходных налогов, в оглавлениях книг, в библиотеках, в словарях, на складах почти везде, где нужно искать хранимые объекты. Даже малышей учат держать свои вещи "в порядке", и они уже сталкиваются с некоторыми видами сортировок задолго до того, как познакомятся с азами арифметики.
Таким образом, разговор о сортировке вполне уместен и важен, если речь идет об обработке данных. Что может легче сортироваться, чем данные? Тем не менее наш первоначальный интерес к сортировке основывается на том, что при построении алгоритмов мы сталкиваемся со многими весьма фундаментальными приемами. Почти не существует методов, с которыми не приходится встречаться при обсуждении этой задачи. В частности, сортировка это идеальный объект для демонстрации огромного разнообразия алгоритмов, все они изобретены для одной и той же задачи, многие в некотором смысле оптимальны, большинство имеет свои достоинства. Поэтому это еще и идеальный объект, демонстрирующий необходимость анализа производительности алгоритмов. К тому же на примерах сортировок можно показать, как путем усложнения алгоритма, хотя под рукой и есть уже очевидные методы, можно добиться значительного выигрыша в эффективности.
Выбор алгоритма зависит от структуры обрабатываемых данных это почти закон, но в случае сортировки такая зависимость столь глубока, что соответствующие методы были даже разбиты на два класса сортировку массивов и сортировку файлов последовательностей . Иногда их называют внутренней и внешней сортировкой, поскольку массивы хранятся в быстрой оперативной, внутренней памяти машины со случайным доступом, а файлы обычно размещаются в более медленной, но и более емкой внешней памяти, на устройствах, основанных на механических перемещениях дисках или лентах . Уже на примере сортировки пронумерованных карточек становится очевидным существенное различие в этих подходах. Если карты "выстроены" в виде массива, то они как бы лежат перед сортирующим, он видит каждую из них и имеет к ней доступ. Если же карты образуют файл, то это предполагает, что видна только верхняя карта в каждой из стопок. Такое ограничение, конечно же, серьезно повлияет на метод сортировки, но ничего не поделаешь: ведь карточек может быть так много, что все они на столе не поместятся.
Прежде чем идти дальше, введем некоторые понятия и обозначения. Ими мы будем пользоваться далее. Если у нас есть элементы а1, а2,..., аn, то сортировка есть перестановка этих элементов массив ак1, ак2, ..., акn, где при некоторой упорядочивающей функции f выполняются отношения f аk1 <= f аk2 <= ... <= f аkn.
Обычно упорядочивающая функция не вычисляется по какому-либо правилу, а хранится как явная компонента поля каждого элемента. Ее значение называется ключом кеу элемента. Поэтому для представления элементов хорошо подходят такие образования, как запись, а графически это представляется так (рис. 1):
Говоря об алгоритмах сортировки, мы будем обращать внимание лишь на компоненту - ключ, другие же компоненты можно даже и не определять (рис.2). Поэтому из наших дальнейших рассмотрений вся сопутствующая информация. Чтобы уменьшить эти затраты, сортировку производят в таблице адресов ключей. После сортировки перестанавливают указатели. Это метод сортировки таблицы адресов (рис.3) . Метод сортировки называется устойчивым, если в процессе сортировки относительное расположение элементов с равными ключами не изменяется. Устойчивость сортировки часто бывает желательной, если речь идет об элементах, уже упорядоченных (отсортированных) по некоторым вторичным ключам (т.е. свойствам) , не влияющим на основной ключ.

Отсортированный массив (рис. 2):

Массив отсортированный другим методом (рис. 3):

Основное условие: выбранный метод сортировки массивов должен экономно использовать доступную память. Это предполагает, что перестановки, приводящие элементы в порядок, должны выполняться на том же месте, т.е. методы, в которых элементы из массива А передаются в результирующий массив H, представляют существенно меньший интерес. Ограничив критерием экономии памяти наш выбор нужного метода среди многих возможных, мы будем сначала классифицировать методы по их экономичности, т.е. по времени их работы. Хорошей мерой эффективности может быть С - число необходимых сравнений ключей и М - число пересылок (перестановок) элементов.
Эти числа - функции от n- числа сортируемых элементов. Хотя улучшенные алгоритмы сортировки требуют порядка n*log n сравнений, мы разберем простой метод, который причисляется к так называемым прямым, где требуется порядка n^2 сравнений ключей. К достоинствам прямых методов относятся :
1.Прямые методы особенно удобны для объяснения характерных черт основных принципов большинства сортировок.
2.Программы этих методов легко понимать, и они коротки. Напомним, что сами программы также занимают память.
3.Улучшенные методы требуют небольшого числа операций, но эти операции обычно сами более сложны, и поэтому для достаточно малых n прямые методы оказываются быстрее, хотя при больших n их использовать, конечно, не следует.
Методы сортировки "на том же месте" можно разбить в соответствии с определяющими их принципами на три основные категории:
1.Сортировки прямым включением Bу insertion .
2.Сортировки прямым выделением Bу selection .
3.Сортировки прямым обменом Bу exchange .

Алгоритм

К прямым методам относится метод прямого выбора.
Рассматриваем весь ряд массива и выбираем элемент меньший или больший элемента а(i), определяем его место в массиве - k, и затем меняем местами элемент а(i) и элемент а(k).
for i = 1 to n - 1
x = a(i)
k = i
for j = i + 1 to n
if x > a(j) then
k = j
x = a(k)
endif
next j
a(k) = a(i)
a(i) = x
next i
return
for i := 1 to n - 1 do
begin
x := a[i];
k := i;
for j := i + 1 to n do
if x > a[j] then
begin
k := j;
x := a[k];
end;
a[k] := a[i];
a[i] := x;
end;

Эффективность алгоритма:
* Количество сравнений

* Количество перемещений, когда массив упорядочен

* Количество перемещений когда массив обратно отсортирован

В худшем случае сортировка прямым выбором дает порядок n2, как и для числа сравнений, так и для числа перемещений.
Задания

Создать группу из N студентов. Ввести их: фамилия, имя, год рождения, оценки по предметам: стр. и алг.данных, высш. математика, физика, программирование, общий балл сдачи сессии; Разработать программу с использованием метода "прямого выбора", которая бы осуществляла сортировку (согласно варианту) :
1. Фамилий студентов по алфавиту.
2. Фамилий студентов по алфавиту в обратном порядке.
3. Студентов по старшинству (начиная со старшего).
4. Студентов по старшинству (начиная с младшего).
5. Студентов по общему баллу (по возрастанию).
6. Студентов по общему баллу (по убыванию).
7. Студентов по результатам 1-го экзамена (по возрастанию).
8. Студентов по результатам 2-го экзамена (по убыванию).
9. Студентов по результатам 3-го экзамена (по возрастанию).
10. Студентов по результатам 4-го экзамена (по убыванию).
11. Имен в алфавитном порядке.
12. Имен в обратном алфавитном порядке.

Лабораторная работа № 8."СОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ОБМЕНА"

Цель работы: исследовать и изучить методы сортировки с помощью прямого обмена.

Задача работы: овладеть навыками написания программ для сортировки с помощью прямого обмена на языке программирования ПАСКАЛЬ .

Порядок работы :
* изучить описание лабораторной работы;
* по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
* написать программу на языке ПАСКАЛЬ;
* отладить программу;
* решить задачу;
* оформить отчет.

Краткая теория

Пузырьковая сортировка
Идея : (N-1) раз массив проходится снизу вверх (сверху вниз), при этом элементы попарно сравниваются, если нижний элемент меньше верхнего, то элементы переставляются.
Пример : массив - 4, 3, 7, 2, 1, 6.

Можно улучшить "пузырьковый" метод, если проходить массив элементов и вверх и вниз одновременно.
Количество сравнений :

Количество перемещений :

Пример вычисления "пузырьковым" методом

На примере представлен массив из пяти элементов, это означает, что массив проходится снизу вверх (сверху вниз) 5-1=4 раза. Так же на примере видно, что алгоритм "в пустую" обрабатывает массив начиная уже с третьего шага внутреннего цикла, а 4-й шаг можно уже не выполнять.
Преимущества данного метода :
1) Самый простой алгоритм
2) Простой в реализации
3) Не нужно дополнительных переменных
Недостатки:
1) Долго обрабатывает большие массивы
2) В любом случае количество проходов не уменьшается

Quiksort - метод быстрой сортировки
Идея : В основе данного метода положен метод разделение ключей по отношению к выбранному.
Пример :

После первого прохода выбранный элемент становится на свое место.

Улучшение "пузырькового" метода.
1) Если проходить массив не только сверху вниз, но и снизу вверх одновременно, то не только "легкие" элементы будут "всплывать", но и "тяжелые" "тонуть".
2) Для отмены прохода массива "впустую" нужно в во внешний цикл вставить проверку на отсортированность массива.

Алгоритм

Алгоритм пузырькового метода
(ПСЕВДОКОД)
for i=2 to n
for j=n to i step -1
if A( j-1 ) > A( j ) then
x=A( j-1 )
A( j-1 )=A( j )
A( j )=x
end if
next j
next i

Алгоритм метода Quiksort
(ПСЕВДОКОД)
Sub Sort(L,R)
i=l
j=r
x=A(( l+r ) div 2 )
while A( i ) < x do
i=i+1
end while
while A( j )>x do
j=j-1
end while
if i<=j then
Y=A( i )
A( i )=A( j )
A( j )=Y
while i>j do
if l sort( l,j )
end if
if i sort( i,r )
end if
return
sub Quiksort
sort ( 1, n )
return

Число перестановок и сравнений: (n* log( n )).

Задания
Варианты:
1. Составить программу вывода на экран самого большого (самого малого) элемента массива А.
2. Составить программу сортировки массива А по убыванию величин его элементов.

3. В массиве А находятся элементы. Составить программу, которая сформирует массив В, в котором расположить элементы масива В в порядке убывания.

4. Дан упорядоченный массив А - числа, расположенные в порядке возрастания, и число а, которое необходимо вставить в массив А, так, чтобы упорядоченность массива сохранилась.

5. Составить программу для быстрой перестройки данного массива А, в котором элементы расположены в порядке возрастания, так, чтобы после перестройки эти же элементы оказались расположенными в порядке убывания.

6. Дан массив А, содержащий как отрицательные, так и положительные числа. Составить программу исключения из него всех отрицательных чисел, а оставшиеся положительные расположить в порядке их возрастания.

7. Составить программу, которая будет из массива А брать одно число за другим и формировать из них массив В, располагая числа в порядке возрастания.

8. Дан список авторов в форме массива А. Составить программу формирования указателя авторов в алфавитном порядке и вывести его на экран.

9. Имеется n абонентов телефонной станции. Составить программу, в которой формируется список по форме: номер телефона, фамилия (номера идут в порядке возрастания).

10. Имеется n слов различной длины, все они занесены в массив А. Составить программу упорядочения слов по возрастанию их длин.

11. Составить программу для сортировки массива А по возрастанию и убыванию модулей его элементов.

12. В отсортированный массив А между каждой соседней парой элементов вставить число больше левого и меньше правого элемента в массиве и вывести полученный массив на экран.

Лабораторная работа № 9. "СОРТИРОВКА С ПОМОЩЬЮ ДЕРЕВА"

Цель работы: исследовать и изучить методы сортировки с помощью дерева.

Задача работы: овладеть навыками написания программ для сортировки с помощью бинарного дерева на языке программирования ПАСКАЛЬ .

Порядок работы :
* изучить описание лабораторной работы;
* по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
* написать программу на языке ПАСКАЛЬ;
* отладить программу;
* решить задачу;
* оформить отчет.

Краткая теория

При обработке данных в ЭВМ важно знать и информационное поле элемента, и его размещение в памяти машины. Для этих целей используется сортировка. Итак, сортировка - это расположение данных в памяти в регулярном виде по их ключам. Регулярность рассматривают как возрастание значения ключа от начала к концу в массиве.
Различают следующие типы сортировок:
* внутренняя сортировка - это сортировка, происходящая в оперативной памяти машины
* внешняя сортировка - сортировка во внешней памяти.
Схематичное представление двоичного дерева : имеется набор вершин, соединенных стрелками. Из каждой вершины выходит не более двух стрелок (ветвей ), направленных влево - вниз или вправо - вниз. Должна существовать единственная вершина, в которую не входит ни одна стрелка - эта вершина называется корнем дерева. В каждую из оставшихся вершин входит одна стрелка.

Существует множество способов упорядочивания дерева. Рассмотрим один из них :
" Левый " сын имеет ключ меньше, чем ключ " Отца "
" Правый " сын имеет ключ больше, чем ключ " Отца "
Получили бинарное упорядоченное дерево с минимальным числом уровней.
Строго сбалансированное дерево : дерево, в котором левое и правое поддерево имеют уровни , отличающиеся не более, чем на единицу.
Рассмотрим принцип построения дерева при занесении элементов в массив :
Пусть в первоначально пустой массив заносятся последовательно поступающие элементы : 70, 60, 85, 87, 90, 45, 30, 88, 35, 20, 86 ; Т.к. это еще пустое дерево, то ссылки left и right равны nil( left - указатель на левого сына (элемент), right - указатель на правого сына (элемент)).
Четвертый из поступающих элементов 87. Т.к. этот ключ больше ключа 70 ( корень ), то новая вершина должна размещаться на правой ветви дерева. Чтобы определить ее место, спускаемся по правой стрелке к очередной вершине ( с ключом 85 ), и если поступивший ключ больше 85, то новую вершину делаем правым сыном вершины с ключом 85 .

В рассмотренном примере ПРИНЦИП ПОСТРОЕНИЯ ДЕРЕВА имеет следующий вид : если поступает очередной элемент массива, то начиная с корня дерева (в зависимости от сравнения текущего элемента с очередной вершиной) идем влево или вправо от нее до тех пор, пока не найдем подходящую вершину, к которой можно подключить новую вершину с текущим ключом. В зависимости от результата сравнения ключей, новую вершину делаем левой или правой для найденной вершины.

Алгоритм

Для создания дерева необходимо создать в памяти элемент следующего типа :

Тип на ПАСКАЛе :
type
pelem = ^elem;
elem = record
left : pointer;
right : pointer;
K : integer;
end;
K - элемент массива, V - указатель на созданный элемент.
В процедуре создания дерева бинарного поиска будут использованы следующие указатели :
tree - указатель на корень дерева;
p - рабочий указатель;
q - указатель отстающий на шаг от p;
key - новый элемент массива;

Создание дерева бинарного поиска :
(псевдокод)

writeln(' Введите элемент массива ');
readln(key);
tree:=maketree(key);
p:=tree;
while not eof do
begin

<< Пред. стр. 12 (из 19) След. >>

Список литературы по разделу