Слайд 1ПРЕОБРАЗОВАНИЕ ОДНОМЕРНЫХ МАССИВОВ ДАННЫХ
Слайд 2Классическими примерами для демонстрации возможностей массивов являются
задачи сортировки и поиска.
Слайд 3СОРТИРОВКА МАССИВОВ
Все методы сортировки можно разделить на
две большие группы:
прямые методы сортировки;
улучшенные методы сортировки.
Слайд 4Прямые методы сортировки по принципу, лежащему в
основе метода, в свою очередь разделяются на
три подгруппы:
сортировка обменом ("пузырьковая" сортировка).
сортировка выбором (выделением);
сортировка вставкой (включением);
Слайд 5Улучшенные методы сортировки основываются на тех же
принципах, что и прямые, но используют некоторые
оригинальные идеи для ускорения процесса сортировки.
Слайд 6СОРТИРОВКА ОБМЕНОМ
("ПУЗЫРЬКОВАЯ" СОРТИРОВКА)
Принцип метода:
Слева направо поочередно
сравниваются два соседних элемента, и их взаиморасположение
не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.
После одного такого прохода на последней n-ой позиции массива будет стоять максимальный элемент ("всплыл" первый "пузырек"). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1-го элемента. И так далее. Всего требуется п-1 проход.
Слайд 7РАССМОТРИМ СХЕМУ АЛГОРИТМА СОРТИРОВКИ МЕТОДОМ ПРЯМОГО ОБМЕНА
ПО НЕУБЫВАНИЮ.
Слайд 9ПРОГРАММА:
Program
Uses Crt;
Const n=5;
Var
a
:array [1..n] of byte;
i,j,p :byte;
k,c
:byte;
begin
ClrScr;
Randomize;
n:=5;
WriteLn('Исходный массив:');
for i:=1 to n do
begin
a[i]:=Random(100); {Генерация значений элементов массива}
Write(a[i]:3) {Печать элементов массива}
end;
WriteLn;
WriteLn('Сортировка:');
c:=0; {Начальное значение счетчика итераций}
for i:=1 to n-1 do {Внешний цикл}
begin
for j:=i+1 to n do {Внутренний цикл}
begin
if a[i]>a[j] then {Условие перестановки}
begin
k:=a[i]; {Переменная для обмена значений элементов}
a[i]:=a[j]; {Обмен значений элементов}
a[j]:=k {Обмен закончен}
end
end;
for p:=1 to n do Write(a[p]:3); {Цикл печати состояния массива}
WriteLn;
c:=c+1 {Счетчик итераций}
end;
WriteLn('Количество итераций: ',c);
Write('Отсортированный массив: ');
for i:=1 to n do {Цикл печати отсортированного массива}
Write(a[i]:3);
ReadKey
end.
Слайд 10ПРОВЕРКА
Исходный массив
47 94 34
26 37
Сортировка:
26 94 47 34
37
26 34 94 47 37
26 34 37 94 47
26 34 37 47 94
Количество итераций: 4
Отсортированный массив:
26 34 37 47 94
Слайд 11СОРТИРОВКА ВСТАВКОЙ
Массив данных разделяется на две части:
отсортированную и неотсортированную. Элементы из неотсортированной части
поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части принимается первый элемент массива.
Слайд 12Таким образом будет иметь место n-1 проход
(где n размерность массива), каждый из которых
будет включать четыре действия:
взятие очередного элемента из неотсортированной части и сохранение в дополнительной переменной;
поиск позиции в отсортированной части массива для вставки элемента взятого предыдущим действием, который бы не нарушил порядок;
сдвиг элементов массива для вставки элемента массива в отсортированную часть;
вставка элемента в найденную позицию.
Слайд 14ПРОГРАММА:
Program vv22; {Сортировка вставкой. Insertion sort}
Uses
Crt;
Const n=5;
Var
a :array [1..n]
of byte;
b,i,j,k,p,c :byte;
begin
ClrScr;
Randomize; {Инициализация генератора случайных чисел}
WriteLn('Сортировка методом вставки');
WriteLn('Исходный массив:'); {Генерация и печать исходного массива}
for i:=1 to n do
begin
a[i]:=Random(100);
Write(a[i]:3)
end;
WriteLn;WriteLn; {Перевод двух строк}
WriteLn('Сортировка:');
c:=0; {Начальное значение счетчика итераций}
for i:=2 to n do {Внешний цикл сортировки}
begin
b:=a[i]; {Взятие элемента массива из неотсортированной части и сохранение его в дополнительной переменной}
j:=1; {Присвоение значения индексной переменной} {Цикл поиска позиции вставки }
while b>a[j] do j:=j+1; {Фиксация позиции вставки}
for k:=i-1 downto j do a[k+1]:=a[k]; {Цикл сдвига злементов массива для вставки}
a[j]:=b; {Вставка элемента массива в найденую позицию}
for p:=1 to n do Write(a[p]:3); {Цикл печати итераций сортировки}
c:=c+1; {Счетчик итераций}
WriteLn
end;
WriteLn('Количество итераций',c);
WriteLn;
WriteLn('Отсортированный массив: ');
for i:=1 to n do Write(a[i]:3); {Цикл печати отсортированного массива}
ReadKey
end.
Слайд 15ПРОВЕРКА:
Исходный массив
95 85 98
32 73
Сортировка:
85 95 98 32
73
85 95 98 32 73
32 85 95 98 73
32 73 85 95 98
Количество итераций: 4
Отсортированный массив:
32 73 85 95 98
Слайд 16СОРТИРОВКА ВЫБОРОМ:
Сортировку выбором называют еще сортировкой поиском
последовательных миниумов. При первом проходе ищется минимальное
значение элементов массива, который затем меняется на первый элемент, затем поиск продолжается на оставшихся. Из оставшихся элементов ищется элемент с минимальным значением и меняется местами с первым из оставшихся, т.е. со вторым элементом исходного массива и т.д.
Слайд 17ПРОГРАММА:
{Сортировка выбором. Selection sort}
Program vv21;
Uses
Crt;
Const n=5;
Var
v :array [1..n]
of byte;
i,j,min,imin,c :byte;
begin
ClrScr;
Randomize;
WriteLn('Сортировка методом выбора (вставкой)');
WriteLn('Исходный массив:');
{Генерация исходного массива}
for i:=1 to n do
begin
v[i]:=Random(100);
Write(v[i]:3)
end;
WriteLn;WriteLn;
WriteLn('Сортировка:');
c:=0; {Начальное значение счетчика итераций}
for j:=1 to n-1 do {Внешний цикл сортировки}
begin
min:=v[j];
imin:=j;
for i:=j+1 to n do {Внутренний цикл сортировки}
if v[i]min:=v[i]; {Присвоение мин. значения переменной min}
imin:=i {Присв. индекса мин. знач. переменной imin}
end;
for i:=1 to n do Write(v[i]:3); {Печать преобр. итерацией массива}
WriteLn; {Перевод строки}
v[imin]:=v[j]; {Обмен значений элементов массива}
v[j]:=min; {Присвоение мин. значения элементу массива}
c:=c+1 {Счетчик итераций}
end;
WriteLn('Количество итераций: ',c);
WriteLn;
WriteLn('Отсортированный массив: ');
for i:=1 to n do Write(v[i]:3);
ReadKey
end.
Слайд 18ПРОВЕРКА:
Исходный массив
93 22 74
65 60
Сортировка:
93 22 74 65
60
22 93 74 65 60
22 60 74 65 93
22 60 65 74 93
Количество итераций: 4
Отсортированный массив:
22 60 65 74 93