double arrow

Ход работы. 1. Составить и оценить алгоритм сортировки простыми обменами (сортировка пузырьком)


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. Википедия http://ru.wikipedia.org

  1. Д.Кнут "Искусство программирования для ЭВМ"






Сейчас читают про: