Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Топ:
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Интересное:
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Дисциплины:
2017-12-13 | 242 |
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;
|
|
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!