litceysel.ru
добавить свой файл
1 2 3
ЛАБОРАТОРНАЯ РАБОТА 1


АЛГОРИТМЫ СОРТИРОВКИ


Цель лабораторной ознакомится с различными методами сортировки данных


Под сортировкой понимают процесс перестановки объектов данного множества в определенном порядке. Цель сортировки - облегчить последующий поиск элементов в отсортированном множестве. В этом смысле сортировка присутствует почти во всех задачах обработки информации. С сортировкой связаны многие фундаментальные приемы построения алгоритмов, которые и будут нас интересовать в первую очередь. В частности, сортировка является идеальным примером огромного разнообразия алгоритмов, выполняющих одну и ту же задачу, многие из которых в некотором смысле оптимальные, а большинство имеет какие-либо преимущества по сравнению с остальными. Поэтому на примере сортировки мы убеждаемся в необходимости сравнительного анализа алгоритмов. Зависимость выбора алгоритмов от структуры данных - явление довольно частое, а в случае сортировки она настолько сильна, что методы сортировки обычно разделяются на две категории:


  • сортировка массивов (внутренняя сортировка)

  • сортировка файлов (внешняя сортировка).


ПОСТАНОВКА ЗАДАЧИ

ДАНО


ТРЕБУЕТСЯ

СВЯЗЬ

и последовательность является перестановкой исходной последовательности.


Основное требование к методам внутренней сортировки - экономное использование памяти. Это означает, что переупорядочивание элементов надо выполнять на том же месте.

Методы внутренней сортировки можно разбить на четыре основных класса в зависимости от лежащего в их основе приема:


  • сортировка включением(вставкой),

  • сортировка выбором,

  • сортировка обменом,

  • разделением.


СОРТИРОВКА ВКЛЮЧЕНИЕМ. Этот метод состоит в том, что на каждом шаге берут i-ый элемент последовательности и передают его в готовую отсортированную часть последовательность, вставляя его на свое место. Алгоритм сортировки включениями выглядит следующим образом:


FOR I := 2 TO N DO

BEGIN X := a[I];

<вставить X на подходящее место в a[1],a[2],...,a[I]>

END


СОРТИРОВКА ВЫБОРОМ. Этот метод основан на следующем

правиле. Выбирается минимальный (максимальный) элемент последовательности и обменивается с первым элементом (элементом) последовательности. Очевидно, один элемент при этом встанет на свое место в отсортированной части последовательности. Далее все выше изложенное надо повторить в не отсортированной части последовательности и т.д.


FOR I = 1 TO N-1 DO

BEGIN

<присвоить K индекс наименьшего элемента из a[I]...a[N]>

<поменять местами a[I] и a[K]>

END


СОРТИРОВКА ОБМЕНОМ. Алгоритм обмена основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы. В качестве примера рассмотрим сортировку методом пузырька.


FOR I:= 2 TO N DO

FOR J:= N DOWNTO I DO

IF a[J-1] > a[J] THEN

BEGIN X := a[J-1]; a[J-1] := a[J]; a[J] := X END

СОРТИРОВКА РАЗДЕЛЕНИЕМ. Алгоритм разделением основан на разбиении последовательности на две подпоследовательности по некоторому правилу. При этом каждая из них может не являться упорядоченной, но последовательное применение указанного правила приводит к упорядоченности последовательности. Примером этого класса алгоритмов является алгоритм быстрой сортировки.



Procedure quicksort(S);

begin

if <S содержит один элемент> then <возвратить S>

else begin <выбрать произвольный элемент a из S>;

<пусть S1 ,S2 и S3 - последовательности элементов из S, соответственно меньших, равных и больших a>;

<возвратить quicksort(S1), затем S2,, затем quicksort(S3) >

end

end


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


  • Существенную долю времени в этих сортировках тратится на обмен информации с внешним запоминающим устройством, поэтому нужны алгоритмы, которые минимизируют число таких операций.

  • Оперативная память имеет ограниченные размеры и поэтому в каждый момент времени может быть доступна только часть данных.

Рассмотрим один из алгоритмов внешней сортировки.


СОРТИРОВКА СЛИЯНИЕМ. Главная идея, которая лежит в основе этой сортировки это представлении файла в виде постепенно увеличивающихся серий, т.е. упорядоченных подпоследовательностей. Если есть, по крайней мере, два файла и число серий в них равно или отличается на единицу, то последовательным слиянием отсортированных серий в новый файл можно уменьшить количество серий, по крайней мере, в два раза.


ЗАДАНИЕ 1. Используя указанную ниже литературу, изучить и реализовать следующие сортировки:

  1. Простой вставкой.

  2. Пузырьковая сортировка.

  3. Простым выбором.

  4. Пирамидальная сортировка.

  5. Быстрая рекурсивная сортировка.

  6. Быстрая сортировка с использованием стека.
  7. Файловая сортировка естественным слиянием.




ЗАДАНИЕ 2. Провести анализ сложности алгоритмов сортировок 1 – 6 из задания 1 , для этого включить в алгоритм подсчет числа базовых операций ( сравнения и обмена) и вычисление времени работы программы на данном массиве.


ВАРИАНТЫ ДОМАШНИХ ЗАДАНИЙ

Изучить, используя литературу , и реализовать указанный ниже метод сортировки, оценить его сложность и построить график эффективности программы.

ВАРИАНТ 1. “Карманная” сортировка [2]

ВАРИАНТ 2. Поразрядная сортировка [2]

ВАРИАНТ 3. Сортировка Шелла. [2]

ВАРИАНТ 4. Сортировка двухпутевым слиянием [3].

ВАРИАНТ 5. Сортировка связных списков слиянием сверху вниз[3].

ВАРИАНТ 6. Восходящая сортировка связных списков слиянием [3].

ВАРИАНТ 7. Быстрая сортировка с разделением на три части[3].

ВАРИАНТ 8. Индексная сортировка [3]

ВАРИАНТ 9. Сортировка бинарными включениями.[1].

ВАРИАНТ 10.Шейкер-сортировка [1].

ВАРИАНТ 11.Сортировка связных списков [3]

ВАРИАНТ 12. Метод распределяющего подсчета [3].

ВАРИАНТ 13.Метод разделения с вычислением медианы трех элементов [3].

ВАРИАНТ 14.Поразрядная сортировка [3].

DFHBFYN


ЛАБОРАТОРНАЯ РАБОТА 2


АЛГОРИТМЫ ОБРАБОТКИ МНОЖЕСТВ


Цель лабораторной работы освоение программирования операций над множествами.


Под множеством понимается неупорядоченная совокупность различных элементов.

Множество, число элементов которого конечно, называется конечным множеством. При программировании задач над множествами естественно рассматривать конечные множества. Число элементов множества A называется его мощностью и обозначается через |A|.

Множество можно задать перечислением его элементов. Например, A = {1, 3, 4, 5, 7}.


Основными операциями над множествами являются изучаемые в школе операции объединения и пересечения , имеющие следующую интерпретацию

, .

Здесь использовано другой способ задания множества – описание свойств, которыми обладают элементы множества.

Операция дополнение множества требует введения понятия универсального множества. При решении многих задач рассматриваются только множества, являющиеся подмножествами некоторого множества U. Это множество U называется универсальным множеством. Универсальное множество определяется классом задач и может иметь малую мощность. Например, в качестве универсального множества можно рассматривать множество из двух элементов {0, 1}.

Дополнением множества A, являющегося подмножеством универсального множества U, является множество .

Булеаном множества A называется множество всех подмножеств множества A. Булеан множества A обозначают через . Это объясняется равенством . Для доказательства этого равенства подмножеству A1 множества A ставится в соответствие двоичный набор длины |A|. В этом наборе i-я компонента равна 1 тогда и только тогда, когда i-й элемент множества A является элементом множества A1. Нетрудно проверить, что различным подмножествам соответствуют различные наборы из 0 и 1. Напомним, что число двоичных наборов длины k равно .


При выполнении лабораторной работы в качестве универсального множества будем рассматривать множество U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. Внутримашинным представлением множества A = {i1, i2, , ik} считаем целое число nA (типа int), единичными битами которого являются только биты с номерами i1, i2, , ik. Например, внутримашинным представлением множества {1, 3, 8} является число 21 + 23 + 28 = 265.

При таком внутримашинном представлении множеств операции над последними выполняются на компьютере с использованием очень быстрых побитовых операций; при этом, также, экономится память.

Заметим, что в более новом, чем Паскаль, языке программирования Си для обозначения побитовых операций & и | (дизъюнкция) используется один символ, а для обозначения логических операций И и ИЛИ применяют два символа && и ||.

Пусть nA и nB – внутримашинные представления множеств A и B. Нетрудно проверить, что внутримашинным представлением множества (множеств и ) является число nA|nB (числа nA&nB и (