Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Интересное:
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2017-12-13 | 239 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!