Сортировка массивов Что изменилось? ЧТО ДАЛЬШЕ ? Поменяем местами голубой и лиловый прямоугольники. - презентация

1

2 Сортировка массивов

3

4

5

6

7

8 Что изменилось?

9 ЧТО ДАЛЬШЕ ? Поменяем местами голубой и лиловый прямоугольники.

10

11

12

13

14

15 Все прямоугольники расположены в порядке увеличения

16 Необходимость отсортировать какие-либо величины возникает в программировании очень часто. Необходимость отсортировать какие-либо величины возникает в программировании очень часто. Существует разные способы сортировки массивов. Существует разные способы сортировки массивов. Задача этого урока – рассмотреть алгоритм сортировки массива по возрастанию.

17 Сформулируйте определение сортировки

18 Сортировка - это процесс упорядочения заданного множества объектов в некотором, заранее определённом порядке.

19 Рассмотрим один из алгоритмов сортировки

20 Сортировка обменом «пузырьковая» сортировка Принцип метода: Слева на право поочерёдно сравниваются два соседних элемента,

21 Сортировка обменом «пузырьковая» сортировка Если их взаимное расположение не соответствует заданному условию упорядоченности, то они меняются местами

22 Сортировка обменом «пузырьковая» сортировка Далее берутся два следующих соседних элемента и так до конца массива

23 Сортировка обменом «пузырьковая» сортировка После одного прохода на последней n-ой позиции массива будет стоять максимальный элемент («всплыл» первый «пузырёк»)

24 Сортировка обменом «пузырьковая» сортировка Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполнятся до n-1 – го элемента

25 Для реализации этого метода сортировки будем использовать алгоритм перестановки 11 5 C:=A АВ С

26 Сортировка обменом «пузырьковая» сортировка 11 5 АВ С

27 Сортировка обменом «пузырьковая» сортировка A:=B АВ С

28 Сортировка обменом «пузырьковая» сортировка B:=C АВ С

29 5 11 АВ С

30 Сортировка обменом «пузырьковая» сортировка Схема алгоритма:

31 Сортировка обменом «пузырьковая» сортировка

32 ! Первый и второй элементы стоят на своих местах

33 В результате перестановок мы получим отсортированный по возрастанию массив

34 135711

35 Данный массив отсортирован по не убыванию13378 Данный массив отсортирован по возрастанию

36 Данный массив отсортирован по убыванию Данный массив отсортирован по не возрастанию87711

37 Программа на Pascal i:=1; repeat if Vector[i]> Vector[i+1] then begin B:=Vector[i]; Vector[i]:=Vector[i+1]; Vector[i+1]:= B; end; i:=i+1; until i>5-k;

38 Программа на Pascal for k:=1 to 4 do begin i:=1; repeat if Vector[i]> Vector[i+1] then begin B:=Vector[i]; Vector[i]:=Vector[i+1]; Vector[i+1]:= B; end; i:=i+1; until i>5 - k; end;

39 Программа, реализующая данный алгоритм uses Crt; type TVector=array [1..5] of real; var Vector:Tvector; B: real; i,k :integer; begin Clrscr; for i:=1 to 5 do Read (Vector[i]); for k:=1 to 4 do begin i:=1; repeat if Vector[i]> Vector[i+1] then begin B:=Vector[i]; Vector[i]:=Vector[i+1]; Vector[i+1]:= B; end; i:=i+1; until i>5-k; end; for i:=1 to 5 do write(Vector[i]:8:2); end.