Конспект лекций по программированию для начинающих. Гладков В.П. - 175 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Составители: 

Рубрика: 

177
массива. В теле этого цикла вначале находим минимальный элемент и его номер.
Затем переставляем найденный элемент на первое место в просматриваемой части.
Фрагмент программы, реализующей данный алгоритм, приведен ниже:
for i:=1 to n-1 do {i - начало обрабатываемой части массива}
begin {поиск минимального элемента от i-го элемента до n-го}
min:=a[i];
imin:=i;
for j:=i+1 to n do
if a[j]<min then begin min:=a[j]; imin:=j end;
{обмен местами минимального и i-го элементов}
a[imin]:=a[i];
a[i]:=min
end.
Упражнение. Постройте аналогичный алгоритм сортировки, используя поиск
максимального элемента в массиве или его части.
11.7.3. Сортировка обменом
Простейшей сортировкой этого типа является «пузырьковая» сортировка. Суть
этой сортировки сводится к следующему. Просматриваем по два соседних
элемента, двигаясь от конца массива к началу. Если левый сосед больше правого,
то меняем их местами. В результате такого просмотра минимальный элемент
окажется на первом месте в массиве («всплыл» первый «пузырек»). Поскольку
минимальный
элемент уже стоит на своем месте, на следующем шаге
просматриваем элементы с последнего до второго. После второго просмотра два
элемента массива будут отсортированы. Выполнив n-1 раз просмотры пар соседних
элементов, начиная с последнего до элемента с номером,равным номеру шага,
получим полностью отсортированный массив.
Например, пусть a={ 3, 1, 9, 2, 5, 7 }, тогда первый просмотр даст следующие
результаты: 3 1 9 2 5 7
5 7 сравниваем,
2 5 сравниваем,
2 9 сравниваем и меняем местами,
1 2 сравниваем,
1 3 сравниваем и меняем местами.
Второй просмотр: 1 | 3 2 9 5 7
5 7 сравниваем,
5 9 сравниваем и меняем
местами,
2 5 сравниваем,
2 3 сравниваем и меняем местами.
Третий просмотр: 1 2 | 3 5 9 7
7 9 сравниваем и меняем
местами, 
                                          177

массива. В теле этого цикла вначале находим минимальный элемент и его номер.
Затем переставляем найденный элемент на первое место в просматриваемой части.
Фрагмент программы, реализующей данный алгоритм, приведен ниже:
   for i:=1 to n-1 do {i - начало обрабатываемой части массива}
   begin      {поиск минимального элемента от i-го элемента до n-го}
              min:=a[i];
              imin:=i;
              for j:=i+1 to n do
                      if a[j]

Страницы