Lab_rab_Pascal_OZO / Lab_12_Упоряд-ние_(сортир)_массива
.docЛабораторная работа № 12.
Упорядочивание (сортировка) массива.
Цель: изучение и приобретение навыков упорядочивания (сортировки) массива и получение дальнейших навыков по отладке и тестированию программ.
Оборудование и программное обеспечение: компьютер, Turbo Pascal 7.0.
Место проведения:
Время:
Теоретические сведения:
Под упорядочиванием (сортировкой) массива подразумевается процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием
Рассмотрим задачу о сортировки массива: дан числовой массивx1, x2,... xn, элементы которого попарно различны; требуется переставить элементы массива так, чтобы после перестановки они были упорядоченны в порядке возрастания: x1 < x2 < ... < xn.
Существует несколько алгоритмов решения этой задачи. Мы рассмотрим два наиболее популярных.
Сортировка методом прямого выбора
Очевидно, что первое место в массиве должен занять минимальный элемент массива, второе - наименьший из всех остальных, третий - наименьший из оставшихся и т.д.
Для этого необходимо выполнить следующую последовательность действий:
1. Определить минимальный элемент массива;
2. Поменять его местами с первым элементом;
3. Определить минимальный элемент среди оставшихся;
4. Поменять его местами со вторым элементом и т.д.;
Эта последовательность действий должна выполняться до тех пор, пока не будет определён последний минимальный элемент.
Всю операцию по упорядочиванию массива можно разбить на более простые задачи.
Первая - поиск минимального элемента.
Вторая - замена местами минимального элемента с номером min с элементом N 1, в первом случае, и с номером i в общем случае. Для этого необходимо объявить дополнительную переменную buf тип которой должен совпадать с типом элементов массива, и выполнить последовательность действий:
Пример 1. Сортировка массива по возрастанию методом прямого выбора.
program sortarr;
const SIZE=5;
var a:array[1..SIZE] of integer;
i:integer; {номер элемента, от которого ведется поиск минимального эл-та }
min:integer; {номер минимального элемента в массива от i до верхней границы
массива}
j:integer; {номер эл-та, сравниваемого с минимальным}
buf:integer; {буфер, используемый при обмене эл-тов массива}
k:integer;
begin
writeln('Сортировка массива.');
write('Введите',SIZE:3,' целых в одной строке ');
writeln('через пробел и нажмите <Enter>');
for k:=1 to SIZE do read(a[k]);
writeln('Сортировка');
for i:=1 to SIZE-1 do
begin {поиск минимального эл-та в части массива от a[i] до a[SIZE]}
min:=i;
for j:=i+1 to SIZE do begin
if a[j]<a[min] then min:=j;
{поменяем местами a[min] и a[i]}
buf:=a[i];
a[i]:=a[min];
a[min]:=buf;
{выведем массив }
for k:=1 to SIZE do write(a[k],' ');
writeln;
end;
end;
writeln('Массив отсортирован.');
end.
Сортировка методом прямого обмена (метод «пузырька»).
В основе алгоритма лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим, и если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива (всплывают), а элементы с большим значением – к концу массива (тонут). Этот процесс повторяется на единицу меньше раз, чем элементов в массиве
Пример 2. Сортировка массива целых по возрастанию методом "пузырька".
program sortarr1;
const SIZE=5;
var a:array[1..SIZE] of integer;
i:integer; { счетчик циклов }
k:integer; { текущий индекс элемента массива }
buf:integer;
begin
writeln('Сортировка массива методом "пузырька".');
write('Введите',SIZE:3,' целых в одной строке через пробел ');
writeln ('и нажмите <Enter>');
for k:=1 to SIZE do read(a[k]);
writeln('Сортировка.');
for i:=1 to SIZE-1
do begin
for k:=1 to SIZE-1
do begin
if a[k]>a[k+1]
then begin
{ обменяем k-й и (k+1)-й элементы }
buf:=a[k];
a[k]:=a[k+1];
a[k+1]:=buf;
end;
end;
for k:=1 to SIZE do write(a[k],' ');
writeln;
end;
writeln('Массив отсортирован.');
end.
Порядок выполнения работы:
Задание: Создать и отладить программу для решения следующую задачу (см. Приложение).
Содержание отчета по каждому заданию:
-
исходные данные (условие задачи);
-
алгоритм (блок-схема) решения задачи;
-
текст программы (или основной фрагмент программы);
-
результаты выполнения программы
Контрольные вопросы:
-
Опишите идею сортировки массива методом прямого выбора и последовательность действий.
-
Опишите идею сортировки массива методом прямого обмена (методом «пузырька») и последовательность действий.
Приложение: (ваш номер по журналу соответствует номеру варианта)
-
Организуйте массив, содержащий 20 различных целых чисел. После этого элементы массива упорядочиваются по убыванию и содержимое отсортированного массива выводится на экран.
-
Организуйте массив, содержащий 20 различных целых чисел. После этого 10 первых элементов массива упорядочиваются по возрастанию, а 10 последних элементов по убыванию. Содержимое отсортированного таким образом массива выводится на экран.
-
Организуйте массив, содержащий 15 различных целых чисел. После этого отдельно первых 5 элементов, вторых 5 элементов и последних 5 элементов сортируются по возрастанию. Содержимое отсортированного таким образом массива выводится на экран.
-
Создайте массив, содержащий 10 различных целых чисел. Содержимое массива сортируется по возрастанию, и после этого определяются минимальный и максимальный элементы массива.
-
Организуйте массив, содержащий 15 различных целых чисел. После этого отдельно первых 5 элементов сортируйте по убыванию, вторых 5 элементов оставьте несортированными и последних 5 элементов сортируются по возрастанию. Содержимое отсортированного таким образом массива выводится на экран.
-
Организуйте массив, содержащий 20 различных символов. Отсортируйте его по возрастанию.
-
Организуйте массив содержащий 20 целых чисел. Отсортируйте отдельно элементы с нечётными индексами по возрастанию.
-
Создайте массив содержащий 20 целых чисел. Отсортируйте его по возрастанию. После этого определите и выведите на экран сумму элементов с чётными индексами.
-
Организуйте массив содержащий 20 целых чисел. Отсортируйте отдельно элементы с чётными индексами по возрастанию, и элементы с нечётными индексами по убыванию.
-
Создайте массив, содержащий 15 целых чисел. Отдельно первых 5 элементов массива, вторых 5 элементов и последних 5 элементов отсортируйте по убыванию. Выведите на экран, отсортированный таким образом массива.
-
Создайте целочисленный массив, содержащий 10 различных чисел. Отсортируйте первую половину массива по возрастанию, а вторую по убыванию. Выведите на экран, отсортированный таким образом массива.
-
Организуйте массив содержащий 20 целых чисел. Отсортируйте отдельно элементы с чётными индексами по возрастанию.
-
Создайте массив, содержащий 20 различных целых чисел. Отсортируйте его по возрастанию. После этого замените все элементы массива на противоположные и выведите содержимое обработанного массива на экран.
-
Создайте массив, содержащий 20 различных целых чисел. Отсортируйте первую половину массива по убыванию, а вторую по возрастанию. Выведите на экран, отсортированный таким образом массива.
-
Организуйте массив содержащий 20 целых чисел. Отсортируйте отдельно элементы с чётными индексами по убыванию, и элементы с нечётными индексами по возрастанию.