Презентация по информатике на тему Сортировка методом пузырька
Сортировка массивов Что изменилось? Поменяем местами голубой и лиловый прямоугольники. ЧТО ДАЛЬШЕ ? Все прямоугольники расположены в порядке увеличения Задача этого урока – рассмотреть алгоритм сортировки массива по возрастанию. Необходимость отсортировать какие-либо величины возникает в программировании очень часто.Существует разные способы сортировки массивов. Сформулируйте определение сортировки Сортировка - это процесс упорядочения заданного множества объектов в некотором, заранее определённом порядке. Рассмотрим один из алгоритмов сортировки 1 7 3 5 11 Сортировка обменом«пузырьковая» сортировка Принцип метода:Слева на право поочерёдно сравниваются два соседних элемента, 1 7 3 5 11 Сортировка обменом«пузырьковая» сортировка Если их взаимное расположение не соответствует заданному условию упорядоченности, то они меняются местами 1 7 3 11 5 Сортировка обменом«пузырьковая» сортировка Далее берутся два следующих соседних элемента и так до конца массива 11 1 7 3 5 Сортировка обменом«пузырьковая» сортировка После одного прохода на последней n-ой позиции массива будет стоять максимальный элемент(«всплыл» первый «пузырёк») 11 1 7 3 5 Сортировка обменом«пузырьковая» сортировка Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполнятся до n-1 – го элемента. 11 11 5 C:=A
А В С Для реализации этого метода сортировки будем использовать алгоритм перестановки 11 11 5 А В С Сортировка обменом«пузырьковая» сортировка 5 11 5 A:=B
А В С Сортировка обменом«пузырьковая» сортировка 5 11 5 B:=C А В С Сортировка обменом«пузырьковая» сортировка 5 11 11 А В С 1 7 3 5 11 1 1 7 3 11 5 1 7 11 3 5 1 11 7 3 5 11 1 7 3 5 Сортировка обменом«пузырьковая» сортировка Схема алгоритма: 11 1 7 3 5 11 1 7 5 3 11 1 7 5 3 2 11 7 1 5 3 Сортировка обменом«пузырьковая» сортировка 11 7 1 5 3 3 ! Первый и второй элементы стоят на своих местах 11 7 1 5 3 11 7 5 1 3 Сортировка обменом«пузырьковая» сортировка 11 7 5 1 3 4 В результате перестановок мы получим отсортированный по возрастанию массив Сортировка обменом«пузырьковая» сортировка 11 7 5 3 1 11 7 5 3 1 Данный массив отсортирован по не убыванию 8 7 3 3 1 Данный массив отсортирован по возрастанию 1 4 5 7 11 Данный массив отсортирован по убыванию Данный массив отсортирован по не возрастанию 1 1 7 7 8 Программа на 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;
Программа на 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;
Программа, реализующая данный алгоритм 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.