Сортировка элементов
массива
сортировки: перестановка
Идея
элементов массива так, чтобы они
располагались
по
возрастанию, либо по убыванию.
То есть, например, из массива
5 2 -1 7 0 -4 3
либо
получить
отсортированный
-4 -1 0 2 3 5 7
возрастанию)
(по
Сортировка элементов
массива
Как видно из предыдущего слайда,
сортировка
к
преобразованию элементов массива.
Заполнять массив будем случайными
числами, выводить в строчку.
Общая задача выглядит так:
формировани
относится
вывод
е
Сортиров
ка
вывод
Алгоритмов сортировок много, но
мы рассмотрим подробнее один –
сортировка обменом.
Сортировка обменом
Идея сортировки обменом состоит
в следующем (сортировать будем по
возрастанию):
На первом шаге сравниваем все
элементы начиная со второго со
значением первого элемента. Если
элемент оказался меньше
наш
первого,
элементы
местами.
то меняем
В результате такого прохода на
самый
первом месте
окажется
Сортировка обменом
5 2 -1 7 0 -4 3
После одного прохода первый элемент
встал на свое место.
Теперь нужно совершить подобный проход
со вторым элементом, затем с третьим и т.д.
• Проделайте подобные проходы в тетради.
• Сколько минимум проходов нужно сделать для
получения конечного результата?
•Проделайте подобные проходы в тетради.•Сколько минимум проходов нужно сделать для получения конечного результата?
Сортировка обменом:
циклы
Итак, если количество элементов в
общем случае равно N, то мы
должны совершить N-1 проходов –
это сделаем циклом.
В каждом проходе мы движемся с
заданного элемента до конца
массива – и на каждый проход тоже
потребуется свой цикл!
Таким образом у нас получается
цикл прохода внутри цикла по
количеству таких проходов.
Сортировка обменом:
циклы
Данная ситуация очень схожа с
вашей учебной неделей – цикл по
цикла
находится
урокам
учебных дней недели:
внутри
Понедельник: 1, 2, 3, 4, 5, …
Вторник: 1, 2, 3, 4, 5, …
Обратите внимание, что в первом
цикле «Понедельник» урок может
первое
принимать
значение, но и 2, 3, 4 и т.д.,
следовательно для цикла в цикле
только
не
Сортировка обменом:
циклы
Внешний
описывает
количество проходов: их от 1 до N-1:
for i:=1 to N-1 do
Внутренний
цикл
с
цикл
должен
i+1-го
элемента
i-м) и совершать
начинаться
(следующего за
проход до конца массива:
for j:=i+1 to N do
Внутри этих циклов проверяется
выполнении
элементов.
условие и при
совершается
его
обмен
Сортировка: обмен
элементов
напрямую
Если
сменить
местами,
например, 1 и 3, то ничего не
выйдет:
попробовать
элементы
Первый элемент
становится равен третьему
А третий элемент равен
первому, т.е. снова самому
a[1]:=a[3];
a[3]:=a[1];
При
себе
такого
попытке
обмена
значение
элемента
бесследно теряется, поэтому это
значение нужно где-то запомнить.
первого
Первый элемент становится равен третьемуА третий элемент равен первому, т.е. снова самому себе
Сортировка: обмен
элементов
Для обмена элемента используется
метод третьего кармана, в качестве
которого для хранения значения
используется
первого
некоторая
(temp)
переменная, тип ее такой же как и
тип элементов массива:
временная
элемента
Запоминаем первый
элемент (в t)
Заменяем 1-ый элемент на
На место 3-го ставим 1-ый
t:=a[1];
a[1]:=a[3];
a[3]:=t;
3-ий
(из t)
Запоминаем первый элемент (в t)Заменяем 1-ый элемент на 3-ийНа место 3-го ставим 1-ый (из t)
Сортировка обменом
Соберем все идеи в одно целое и
решим задачу для сортировки по
возрастанию
массива,
сформированного из 10 целых
случайных чисел в диапазоне от
5 до 30.
program z;
Запишем начало программы:
var a:array[1..10] of integer;
i,j,t:integer;
Переменные
Переменные
для циклов
для циклов
Переменная для обмена
элементов
Переменные для цикловПеременные для цикловПеременная для обмена элементов
Сортировка обменом
Теперь запишем два первых шага
работы с массивом – формирование и
вывод:
begin
for i:=1 to 10 do
a[i]:=random(26)+5;
for i:=1 to 10 do
write(a[i]:4);
writeln;
по
до N-1 элементов
последнего
Сортировка обменом
А
–
сортировка
до
далее
возрастанию:
for i:=1 to 9 do
с 1-
for j:=i+1 to 10 do
го
if a[i]>a[j] then begin
следующ
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
обмен
со
его
если заданный
элемент больше
проходимого
элементов
до N-1 элементовдо последнегос 1-госо следующегоесли заданный элемент больше проходимого обмен элементов
Сортировка обменом
И в конце выводим результат для
сравнения первоначального массива
с отсортированным:
for i:=1 to 10 do
write(a[i]:4);
writeln;
end.
Итак, наша задача решена!
Переходим к другим…
Задания
1. Отсортировать
убыванию.
2. Отсортировать
возрастанию
элемента по седьмой.
от
массив
по
массив
по
третьего
3. *Отсортировать
по
возрастанию с начала и по
элемент
максимальный
массива.
массив
Задания
16_Массивы-3.pptx
