Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Топ:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Дисциплины:
2017-12-13 | 240 |
5.00
из
|
Заказать работу |
|
|
Рассмотрим два способа сортировки одномерного массива.
1. Сортировка одномерного массива методом «пузырька» (случай сортировки по возрастанию). В массиве находят min элемент и меняют его местами с первым элементом. После этого первый элемент из обработки исключается. Теперь в массиве, начиная уже со второго элемента, вновь находят min элемент и меняют его местами со вторым элементом. Каждый раз число обрабатываемых элементов массива уменьшается на единицу. Процесс повторяется до тех пор, пока весь массив не будет упорядочен (рис. 6.2). Блок-схема алгоритма приведена на рис. 6.1.
Hачало |
Ввод ak |
k=1, n-1 |
Вывод ak |
конец |
p=ak; ak=aj; aj=p |
ak>aj |
да |
нет |
j=k+1,n-1 |
Рис. 6.1. Блок-схема сортировки одномерного массива методом «пузырька»
М1 |
М2 |
М1 |
М1 |
М2 |
М3 |
М1 |
М2 |
М3 |
Мn |
М1 |
М2 |
М3 |
Мn |
…. |
|
Рис. 6.2. Сортировка одномерного массива методом «пузырька»
2. Метод линейной сортировки одномерного массива. В методе линейной сортировки сравнивают значения каждой пары соседних элементов:
Если два соседних элемента не упорядочены, то их меняют местами (выполняется перестановка элементов массива). Если не производилось ни одной замены, это означает, что массив упорядочен и вычисления заканчивают. Если не все пары соседних элементов упорядочены сравнение и перестановку проводят снова.
Рассмотрим алгоритм линейной сортировки одномерного массива (рис. 6.3):
1) число k – счетчик для подсчета упорядоченных пар приравнивают нулю;
2) сравнивают первый элемент со вторым, если они не упорядочены то их меняют местами, иначе увеличивают k на 1;
3) сравнивают второй элемент с третьим, если они не упорядочены, тогда их меняют местами, иначе увеличивают k на 1;
4) процесс продолжается до n -1 (n – размерность массива);
5) анализируют значение k:
- если k >= n -1 это означает, что замен не было (т.е. последовательность упорядочена) и вычисления завершают;
- если k < n -1 возвращаются к шагу 1.
Пример. Дан массив а (n) упорядочить его в порядке возрастания методом линейной сортировки, n – размерность массива задается константой в программе.
Начало |
Ввод ai |
k=0 |
j=1, n-1 |
k>=n-1 |
k=k+1 |
Вывод ai |
конец |
да |
нет |
p=ai; ai=ai+1; ai+1=p |
да |
нет |
(while, repeat) |
Рис.6.3. Блок-схема метода линейной сортировки одномерного массива
{Сортировка одномерного массива методом «пузырька»}
for k:=1 to n-1 do
for j:=k+1 to n do
if a[k]>a[j] then
begin
p:=a[k];
a[k]:=a[j];
a[j]:=p;
end;
{Метод линейной сортировки одномерного массива}
repeat
k:=0;
for i:=1 to n-1 do
if a[i]>a[i+1] then
begin
p:=a[i];
a[i]:=a[i+1];
a[i+1]:=p;
end
else
k:=k+1;
until k>=n-1;
|
|
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!