Презентация на тему Преобразование одномерных массивов данных

задачи сортировки и поиска.

две большие группы:
прямые методы сортировки;
улучшенные методы сортировки.

основе ме­тода, в свою очередь разделяются на

три подгруппы:
сортировка обменом ("пузырьковая" сортировка).
сортировка выбором (выделением);
сортировка вставкой (включением);

принципах, что и прямые, но используют некоторые

оригинальные идеи для ускорения процесса сортировки.

сравниваются два соседних элемента, и их взаиморасположение

не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.
После одного такого прохода на последней n-ой позиции массива будет стоять максимальный элемент ("всплыл" первый "пузырек"). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1-го элемента. И так далее. Всего требуется п-1 проход.

ПО НЕУБЫВАНИЮ.

: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.

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

отсортированную и неотсортированную. Элементы из неотсортированной части

поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части принимается первый элемент массива.

(где n размерность массива), каждый из которых

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

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.

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

последовательных миниумов. При первом проходе ищется минимальное

значение элементов массива, который затем меняется на первый элемент, затем поиск продолжается на оставшихся. Из оставшихся элементов ищется элемент с минимальным значением и меняется местами с первым из оставшихся, т.е. со вторым элементом исходного массива и т.д.

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.

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