Задания к данному параграфу. Задание 1. Задайте массив целых чисел a[1:n]
Задание 1. Задайте массив целых чисел a[1:n]. Смоделируйте последовательность преобразований содержимого памяти при реализации сортировки элементов массива методами:
· методом простого выбора;
· методом простых включений, стр. 147, 149,151;
· методом простого обмена, суть метода изложена ниже;
· улучшенным методом сортировки обменом, когда необходимо запомнить, производился ли на данном проходе массива обмен элементов, если нет, то сортировку массива закончить;
· улучшенным методом сортировки обменом, когда необходимо запомнить не только, производился ли на данном проходе массива обмен элементов, но и место последнего обмена, следующие проходы можно закончить на этом индексе, вместо того, чтобы сравнивать элементы до установленной границы i.
Задание 2. Составьте блок-схемы алгоритмов решения задач задания 1, напишите программы на языках программирования, отличных от Ершола.
Пояснение к выполнению задания
Идея метода сортировки массивов простым обменом
Идея сортировки простым обменом элементов массива a[1:n] заключается в повторении n-1 раз попарных сравнений рядом стоящих элементов массивов A[1:n], A[2:n], A[3:n], A[4:n], … , A[n-1:n]. Каждый из этих массивов содержит на один элемент меньше, чем предыдущий. При сравнении элементы массива переставляются в заданном порядке, поэтому при каждом проходе элемент a[i], i изменяется от 1 до n-1, занимает своё место в отсортированной части массива. Последний элемент массива после попарных сравнений n-1 раз и обменов, если необходимо, стоит тоже на своём месте в отсортированном массиве. Элементы массивов просматриваются либо от конца к началу, либо от начала к концу. При сортировке будем просматривать элементы массивов A[1:n], A[2:n], A[3:n], A[4:n], … , A[n-1:n] от конца к началу, и массив отсортируем по возрастанию значений элементов массива. Алгоритм сортировки элементов массива методом простого обмена и программа на языке Ершол даны в таблице 10.
Программа сортировки массивов простым обменом и сущность
этого метода
| алг сортобмен нач 1шаг. Введи элементы массива в память компьютера. 2 шаг. Для i изменяющегося от 2 до n выполни следующие шаги. 2.1 шаг. Для j, изменяющегося от n до i с шагом -1, выполни следующие шаги. 2.1.1 шаг. Сравни элементы a[j] и a[j-1]. Если a[j] < a[j-1], то поменяй их местами. 2.1.2 шаг. Организуй вывод элементов массива, полученного при прохождении текущего цикла. кон | алг сортобмен (аргцел n) начцел i,j,b,целтаб a[1:n] │input(n,a) │print(n,a) │нцдля i от 2 до n ││нцдля j от n до i шаг -1 │││если a[j] < a[j-1] ││││то ││││ |обмен значениями a[j] и a[j-1] ││││ b:=a[j]; a[j]:=a[j-1];a[j-1]:=b │││все ││кц ││print(n,a) │кц кон Вспомогательные алгоритмы input и print смотри в таблице 9. |
| Таблица 10. Алгоритм и программа на языке Ершол сортировки элементов массива методом простого обмена |
Дата добавления: 2015-01-26; просмотров: 860;