2015-01-13
441
1. Составить и оценить алгоритм сортировки простыми обменами (сортировка пузырьком).
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
procedure BubbleSort;
var i,j: index; x:item;
begin
for i:=2 to n do
begin 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;
end;
end;
2. Составить и оценить алгоритм сортировки выбором
Шаги алгоритма:
находим минимальное значение в текущем списке
производим обмен этого значения со значением на первой неотсортированной позиции
теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы.
Существует также двунаправленный вариант сортировки методом выбора, в котором на каждом проходе отыскиваются и устанавливаются на свои места и минимальное, и максимальное значения.
3. Составить и оценить алгоритм сортировки вставками.
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
4. Составить и оценить алгоритм сортировки слиянием
Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Для решения задачи сортировки эти три этапа выглядят так:
1. Сортируемый массив разбивается на две части примерно одинакового размера;
2. Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
3. Два упорядоченных массива половинного размера соединяются в один.
Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
Нетривиальным этапом является соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем две стопки карт, лежащих рубашками вниз так, что в любой момент мы видим верхнюю карту в каждой из этих стопок. Пусть также, карты в каждой из этих стопок идут сверху вниз в неубывающем порядке. Как сделать из этих стопок одну? На каждом шаге мы берём меньшую из двух верхних карт и кладём её (рубашкой вверх) в результирующую стопку. Когда одна из оставшихся стопок становится пустой, мы добавляем все оставшиеся карты второй стопки к результирующей стопке.
Содержание отчета:
Выписать в тетрадь практических работ название, цель работы и решения выполненных задач. Сделать вывод к работе.
Критерии оценок:
«5» - выполнено 4 задания.
«4» - выполнено 3 заданий.
«3» - выполнено 2 задания.
Литература.
1. Семакин, И.Г. Основы алгоритмизации и программирования. Практикум [Текст]: учеб. пособие / И.Г. Семакин, А.П. Шестаков. - М.:Изд. центр «Академия», 2013-144с.
2. Википедия https://ru.wikipedia.org
- Д.Кнут "Искусство программирования для ЭВМ"
