Сортировки массива и бинарный поиск элемента

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]
-

9. Поиск элемента в массиве

10.

Поиск в неупорядоченном массиве заключается в
последовательном переборе элементов массива и
сравнении их значений с искомым до того момента,
пока результат сравнения не даст значение истина
Наиболее эффективные методы поиска работают
только на упорядоченных наборах данных, для чего
их предварительно сортируют

11. Бинарный поиск (поиск методом деления пополам)

Является одним из эффективных методов поиска в
больших отсортированных массивах

12. Идея метода:

делим массив пополам (определяем номер среднего
элемента)
сравнивая искомый элемент со значением среднего
элемента массива, мы в состоянии сделать вывод, в
какой половине он находится, т.е. сузить область
дальнейшего поиска
затем делим пополам ту часть массива, в которой
элемент обнаружен
так до тех пор, пока рассматриваемая часть массива
не получится состоящей из одного элемента

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

m – линейный упорядоченный массив
n – число элементов массива
i – индекс элемента
f – номер первого элемента области просмотра
l – номер последнего элемента области просмотра
c – искомое число
found – логический результат (найдено число или
нет)
a – число повторов

14.

Ввод c
a=0; f=1; l=n; found=false
i:=(f+l) / 2
+
-
m[i] == c
found = true
+
first = i+1
a = a+1
+
НЕ (found)
И(first>last)
-
m[i] > c
last = i-1

15.

+
Вывод i, a
found
c не
найдено