Презентация "Алгоритмы сортировки двумерных массивов. Пузырьковая сортировка" 11 класс


Подписи к слайдам:
Алгоритмы сортировки двумерных массивов

Алгоритмы сортировки двумерных массивов. Пузырьковая сортировка

Учитель информатики ФГКОУ «СОШ№152»

Нигматуллина О.А.

Презентация к элективному курсу

«Программирование в Турбо Паскале» 11 класс

Цели и задачи

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

Задачи:

Воспитательная – развитие познавательного интереса, логического мышления.

Учебная – совершенствование навыков составления программ на языке Pascal

Развивающая – развитие алгоритмического мышления, памяти, внимательности.

Содержание

  • Принцип «Пузырьковой сортировки» или метода обмена
  • Построение алгоритма
  • Алгоритм в словесно-пошаговой форме
  • Программа пузырьковой сортировки массива
  • Практикум по решению задач
  • Источники

Принцип «Пузырьковой сортировки» или метода обмена

  • В порядке возрастания.
  • Последовательно просматриваются пары соседних элементов.
  • Если левый элемент больше правого, то они обмениваются местами.

Пусть задан неупорядоченный массив  В = (20,10,8,7):

20

10

8

7

>

1 шаг:

>

>

2 шаг:

10

8

7

20

>

>

3 шаг:

8

7

10

20

>

>

Вывод

  • Итак, для сортировки массива из 4 элементов понадобилось выполнить 3 шага.
  • Т.е. отсортировать массив, состоящий из n чисел, можно, выполнив n — 1 шагов.

Построение алгоритма

Задан массив А[1..n] из n элементов, где

- номер шага выполнения сортировки,

- номер первого элемента в паре элементов A[j], A[j +1], которые надо сравнивать.

i 1:

просматриваются пары, в которых номер j изменяется от 1 до -1 (последними сравниваются элементы A[n-1],A[n]).

i = 2:

 

просматриваются пары, в которых номер изменяется от 1  до   n-2  (последними сравниваются элементы A[n-2],  А[n-1]).

i= 3 :

просматриваются пары, в которых номер j изменяется от  1  до   n - 3 (последними сравниваются элементы   A[n -3], А[n-2]).

i = n-1:

 

просматриваются пары, в которых номер j изменяется от 1 до n - (n -1) = 1 (сравниваются только элементы А [1], A[2]).

Вывод:

  • всего выполняется (n —1) шагов, то есть переменная i изменяется от 1 до (n -1);
  • на i-м шаге просматриваются пары, в которых номер j изменяется от 1 до (n-1) .

Алгоритм в словесно-пошаговой форме (t - переменная для обмена значений элементов)

  • Задать массив A[1..n].
  • i:=1.
  • Если i < n, то перейти к пункту 4, иначе перейти к пункту 9.
  • j:=1.
  • Если j < n - i, то перейти к пункту 6, иначе i-й шаг сортировки выполнен, перейти к пункту 8.
  • Если  A[j]>A[ j + 1], то поменять их местами:  t:=A[j]; A[j]: =A[j + 1];A[j +1l]: = t.
  • Увеличить номер j (j:=j+1) и перейти к пункту 5.
  • Увеличить номер i (i:=i+1) и перейти к пункту 3.
  • Сортировка массива завершена. Вывод массива.

Внутренний цикл

Внешний цикл

Программа пузырьковой сортировки массива

Program Bubble;

Var A: array [l..n] of real; {массив вещественных чисел} i,   j:integer;

t: real; {переменная для обмена должна быть такого же типа,   как и элементы массива!}

begin                                                                                                    

for i:=1 to n do read(A[i]);   {создание массива}

{сортировка}

for  i:=1  to n-1  do for j:=1   to n-i  do

if A[j] > A[j+1]   then                                                           £>

begin       

t:=  A[j];  A[j]:=  A[j+1];  A[j+1]:=t;                                                                       

end;

for  i:=1   to  n  do 

Write (A[i] :3:1,    '   ');   {вывод отсортированного массива}

end.

Практикум по решению задач

  • Сформировать матрицу случайным образом. Отсортировать массив по возрастанию в строках
  • Сформировать массив n-порядка с элементами из диапазона (0, 20). N – вводится с клавиатуры. Отсортировать массив в порядке убывания.

Источники

  • Андреева Е.В. Методика обучения основам программирования на уроках информатики. М.: Педагогический университет «Первое сентября», 2006.
  • Ракитина Е.А., Бешенков С.А., Галыгина И.В., Милохина Л.В. Сборник типовых задач по информатике. М.: Образование и информатика, 2005
  • http://www.chezgundula.fr/wp-content/uploads/2013/01/bulles.jpg
  • http://99px.ru/sstorage/53/2010/09/mid_4272_5606.png