Сортировка элементов массива. (Урок 45)

Сентябрь 7, 2022

Главная
Алгебра
Сортировка элементов массива. (Урок 45)

Содержание

2. §2.2.6 (стр.71–73) Текст программы и тесты записать в тетрадь. Домашнее задание
3. Сортировка Сортировка – это перестановка элементов массива в заданном порядке (по возрастанию, убыванию, другим условиям). Задача:
4. Метод выбора Идея: найти минимальный элемент и поставить на первое место (поменять местами с A[1]) из
5. Этот приём основан на следующих принципах: 1. Выбираем элемент с наименьшим ключом. 2. Он меняется местами
6. Метод выбора нужно N-1 раз поиск минимального от A[k] до A[N] переставляем for k:=1 to N-1
7. {Процесс сортировки} for k:=1 to N-1 do begin nMin=k; for i:=k+1 to N do if A[i]
8. Наибольшее значение в массиве MAX:= a[1] i,2,N MAX:=a[i] Дано: a – массив чисел N – количество
9. Задание Составить программу, которая заданные числа вводит в массив и сортирует массив по неубыванию. Протестировать при
10. Начало Конец Сортировка массива Ввод массива Вывод массива Укрупнённый алгоритм
11. Ввод массива с клавиатуры (вспомним) write('Количество чисел? '); readln(N); for i:=1 to N do begin write('a[',
12. Вывод массива на экран const K=50; var a: array[1..K] of integer; for i:=1 to N do
14. Скачать презентацию

Слайд 2

§2.2.6 (стр.71–73) Текст программы и тесты записать в тетрадь.
Домашнее задание

Слайд 3

Сортировка
Сортировка – это перестановка элементов массива в заданном порядке (по возрастанию,

убыванию, другим условиям).
Задача: переставить элементы массива в порядке возрастания.
Методы:
простые и понятные, но неэффективные для больших массивов
метод пузырька
метод выбора
метод вставки
эффективные, но сложные
«быстрая сортировка» (Quick Sort)
метод Шелла
сортировка «кучей» (Heap Sort)
сортировка слиянием
пирамидальная сортировка

время O(N2)

время O(N·logN)

Слайд 4

Метод выбора
Идея:
найти минимальный элемент и поставить на первое место (поменять местами

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

Слайд 5

Этот приём основан на следующих принципах:
1. Выбираем элемент с наименьшим ключом.
2.

Он меняется местами с первым элементом а[1].
3. Затем этот процесс повторяется с оставшимися N-1 элементами, N-2 элементами и т.д. до тех пор, пока не останется один самый большой элемент.
Алгоритм формулируется следующим образом:
для k от 1 до N-1 нц
найти nmin – индекс наименьшего из a[k],…a[N];
поменять местами a[nmin] и a[k]
кц;

44 55 12 42 94 18 06 67
06 55 12 42 94 18 44 67
06 12 55 42 94 18 44 67
06 12 18 42 94 55 44 67
06 12 18 42 94 55 44 67
06 12 18 42 44 55 94 67
06 12 18 42 44 55 94 67
06 12 18 42 44 55 67 94

Метод выбора

Слайд 6

Метод выбора
нужно N-1 раз
поиск минимального от A[k] до A[N]
переставляем
for

k:=1 to N-1 do begin
nMin=k;
for i:=k+1 to N do
if A[i] then nMin:=i;
c:=A[i];
A[i]:=A[nMin];
A[nMin]:=c;
end;

Слайд 7

{Процесс сортировки}
for k:=1 to N-1 do begin
nMin=k;
for i:=k+1 to

N do
if A[i] nMin:=i;
c:=A[i];
A[i]:=A[nMin];
A[nMin]:=c;
end;
{Отсортировано}

Метод выбора – фрагмент программы

Слайд 8

Наибольшее значение в массиве
MAX:= a[1]
i,2,N
MAX:=a[i]
Дано:
a – массив чисел
N – количество чисел
Результат:
MAX

– наибольшее число

i - промежуточная переменная

a[i]>MAX

да

нет

Слайд 9

Задание
Составить программу, которая заданные числа вводит в массив и сортирует массив

по неубыванию.

Протестировать при учителе программу. Исходный текст программы оставить на рабочем столе. Имя файла:
V1<до 6 букв фамилии>.PAS
Например: V1LAZARE.PAS

Слайд 10

Начало
Конец
Сортировка массива
Ввод массива
Вывод массива
Укрупнённый алгоритм

Слайд 11

Ввод массива с клавиатуры
(вспомним)
write('Количество чисел? ');
readln(N);
for i:=1 to N do begin

write('a[', i, ']=');
readln( a[i] )
end;

a[1] =
a[2] =
a[3] =
a[4] =
a[5] =

5
12
34
56
13

Постановка проблемы. Описан массив. Ввести все его элементы

Описан массив

const K=50;
var a:array[1..K] of integer;

var a:array[1..50] of integer;

или так, что то же самое!

Слайд 12

Вывод массива на экран
const K=50;
var a: array[1..K] of integer;
for i:=1

to N do
writeln('a[',i,']=',a[i]);

a[1]=25
a[2]=144
a[3]=1316
a[4]=3466
a[5]=169

Постановка проблемы. Описан массив. Значения элементам присвоены. Вывести N его элементов на экран

Можно в строку через пробел

Массив A:
25 144 1316 3466 169

writeln('Массив A:');
for i:=1 to N do
write(a[i]),' ');

Сортировка элементов массива. (Урок 45)

Содержание

§2.2.6 (стр.71–73) Текст программы и тесты записать в тетрадь.Домашнее задание

СортировкаСортировка – это перестановка элементов массива в заданном порядке (по возрастанию,

Метод выбораИдея:найти минимальный элемент и поставить на первое место (поменять местами

Этот приём основан на следующих принципах:1. Выбираем элемент с наименьшим ключом.2.

Метод выборанужно N-1 раз поиск минимального от A[k] до A[N]переставляем for

{Процесс сортировки}for k:=1 to N-1 do begin nMin=k; for i:=k+1 to

Наибольшее значение в массивеMAX:= a[1]i,2,NMAX:=a[i]Дано:a – массив чиселN – количество чиселРезультат:MAX

ЗаданиеСоставить программу, которая заданные числа вводит в массив и сортирует массив

НачалоКонецСортировка массиваВвод массиваВывод массиваУкрупнённый алгоритм

Ввод массива с клавиатуры(вспомним)write('Количество чисел? ');readln(N);for i:=1 to N do begin

Вывод массива на экранconst K=50; var a: array[1..K] of integer;for i:=1

Похожие презентации