Методы сортировки линейного массива (лекция 6)

1. Методы сортировки линейного массива

2. Постановка задачи:

1.
2.
3.
Заполнить линейный массив случайными числами,
вывести его на экран
выполнить сортировку элементов массива по
убыванию
вывести
на
экран
отсортированный
(упорядоченный) массив

3. 1. Линейная сортировка (сортировка отбором)

Идея:
последовательно
просматривая
весь
массив,
отыскать наибольшее число и поменять его местами
с первым элементом
затем просматриваются элементы массива, начиная
со второго, снова находится наибольший, который
меняется местами со вторым
и т.д.

4. Список величин:

m – линейный массив
n – число элементов массива
i – индекс элемента массива
p – номер просмотра
max – индекс максимального элемента области
просмотра
buf – буферная переменная

5.

Заполнение линейного массива случайными
числами и вывод его на экран
p := 1,n-1, 1
max := p
i := p,n, 1
+
m[i]>m[max]
max := i
Buf:=m[p]; M[p]:=m[max];
M[max]:=buf
-

6. 2. Сортировка методом «пузырька»

Идея:
в процессе исполнения алгоритма более «легкие»
элементы массива постепенно «всплывают»
особенностью данного метода является сравнение, а
затем, если нужно, и перестановка соседних
элементов
результат
достигается
путем
просмотра и обработки массива
многократного

7. Список величин:

m – линейный массив
n – число элементов массива
i – индекс элемента массива
p – номер просмотра
buf – буферная переменная

8.

Заполнение линейного массива случайными
числами и вывод его на экран
p:=1,n-1, 1
i :=1,n-1, 1
+
buf := m[i];
m[i] := m[i+1];
m[i+1] := buf
m[i] < m[i+1]
-