Программирование на языке Паскаль Урок Сортировка массивов Рыжикова С. В. Учитель информатики МОУ СОШ 2 г. Волжского Волгоградской обл. - презентация

1 Программирование на языке Паскаль Урок Сортировка массивов Рыжикова С. В. Учитель информатики МОУ СОШ 2 г. Волжского Волгоградской обл.

2 2 Сортировка Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …). Задача: переставить элементы массива в порядке возрастания. Алгоритмы: сортировка обменом – «пузырьковая» сортировка выбором сортировка вставками сортировка подсчетом

3 3 Метод пузырька Идея – пузырек воздуха в стакане воды поднимается со дна вверх. Для массивов – самый маленький ("легкий") элемент перемещается вверх ("всплывает") начиная снизу, сравниваем два соседних элемента; если они стоят "неправильно", меняем их местами за 1 проход по массиву один элемент (самый маленький) становится на свое место ый проход 2-ой проход 3-ий проход Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

4 Программная реализация алгоритма Program C; uses crt; {пузырьковая сортировка} var a:array [1..30] of integer; i,d,l:integer; begin clrscr; randomize; writeln ('исходный массив'); for i:= 1 to 30 do begin a[i]:=random(10); write (a[i],' '); end; writeln; for l:=30 downto 2 do for i:=1 to l-1 do if a[i]>a[i+1] then begin d:=a[i]; a[i]:=a[i+1]; a[i+1]:=d; end; writeln('новый отсортированный массив'); for i:=1 to 30 do write (a[i],' '); readkey; end. исходный массив новый отсортированный массив

5 5 Метод выбора Идея: найти минимальный элемент и поставить на первое место (поменять местами с A[1] ) из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[2] ), и т.д

6 Программная реализация алгоритма Program C; {сортировка выбором} uses crt; var b,a:array [1..30] of integer; i,h,k,d,l:integer; begin clrscr; randomize; writeln ('исходный массив'); for i:= 1 to 30 do begin a[i]:=random(10); write (a[i],' '); end; writeln; for l:=1 to 29 do begin k:=30-l+1; h:=k; for i:=1 to 30-l do if (a[i]>a[h]) then h:=i; d:=a[k]; a[k]:=a[h]; a[h]:=d; end; writeln('новый отсортированный массив'); for i:=1 to 30 do write (a[i],' '); readkey; end. исходный массив новый отсортированный массив

7 Сортировка вставками Идея : основана на внедрении в отсортированную часть массива элемента следующего за этой частью, если он удовлетворяет условию сортировки. на первом шаге сортировки второй элемент сравнивается с первым, на втором шаге третий элемент сравнивается с двумя первыми и т. д. среди уже отсортированных i-1 элементов массива вставляют i-й элемент без нарушения порядка, т. е. при вставке i-го элемента на j-е место (j j и

8 Программная реализация алгоритма Program C; {сортировка вставками} uses crt; var a:array [1..30] of integer; i,h,d,l:integer; begin clrscr; randomize; writeln ('исходный массив'); for i:= 1 to 30 do begin a[i]:=random(10); write (a[i],' '); end; writeln; for l:=2 to 30 do begin d:=a[l]; h:=1; while d>a[h] do h:=h+1; for i:=l downto h+1 do a[i]:=a[i-1]; a[h]:=d; end; writeln('новый отсортированный массив'); for i:=1 to 30 do write (a[i],' '); readkey; end. исходный массив новый отсортированный массив

9 Сортировка подсчетом Идея: основана на подсчете для каждого элемента количества элементов массива, меньших данному. от этого количества зависит номер каждого элемента в новом массиве, т. е. если 5 элементов меньше данного, то его место в новом массиве будет 6-ым (при сортировке по возрастанию) Массив А Массив В 2 элемента его меньше 0 элементов его меньше 1 элемент его меньше 3 элемента его меньше номер= номер= номер= номер=

10 Программная реализация алгоритма Program C; {сортировка подсчетом} uses crt; var b,a:array [1..30] of integer; i,h,l:integer; begin clrscr; randomize; writeln ('исходный массив'); for i:= 1 to 30 do begin a[i]:=random(10); write (a[i],' '); end; writeln; for l:= 1 to 30 do begin h:=0; for i:= 1 to 30 do if (a[i] l) then h:=h+1; b[h+1]:=a[l]; end; for i:=2 to 30 do if b[i]=0 then b[i]:=b[i-1]; writeln('новый массив'); for i:=1 to 30 do write (b[i],' '); readkey; end. исходный массив новый отсортированный массив

11 11 Задания "5 ":Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать его по последней цифре. Пример: Исходный массив: Результат: "4": Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать первую половину по возрастанию, а вторую – по убыванию. Пример: Исходный массив: Результат: решение задачи

12 Program gr3; uses crt; {используем пузырьковую сортировку} var d:array [1..10] of byte; i,k,h:byte; begin clrscr; randomize; writeln ('исходный массив'); for i:= 1 to 10 do begin d[i]:=random(101); write (d[i],' '); end; writeln; for k:=5 downto 2 do for i:=1 to k-1 do if d[i]>d[i+1] then begin h:=d[i]; d[i]:=d[i+1]; d[i+1]:=h; end; for k:=10 downto 7 do for i:=6 to k-1 do if d[i]

13 Program gr2; uses crt; {используем пузырьковую сортировку} var w:array [1..10] of byte; i,k,h:byte; begin clrscr; randomize; writeln ('исходный массив'); for i:= 1 to 10 do begin w[i]:=random(101); write (w[i],' '); end; writeln; for k:=10 downto 2 do for i:=1 to k-1 do if w[i] mod 10 > w[i+1] mod 10 then begin h:=w[i]; w[i]:=w[i+1]; w[i+1]:=h; end; writeln('полученный массив'); for i:=1 to 10 do write (w[i],' '); Readkey; end. Результат работы группы 2 исходный массив полученный массив