Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Lab_rab_Pascal_OZO / Lab_12_Упоряд-ние_(сортир)_массива

.doc
Скачиваний:
20
Добавлен:
21.03.2015
Размер:
58.88 Кб
Скачать

Лабораторная работа № 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.

Порядок выполнения работы:

Задание: Создать и отладить программу для решения следующую задачу (см. Приложение).

Содержание отчета по каждому заданию:

  • исходные данные (условие задачи);

  • алгоритм (блок-схема) решения задачи;

  • текст программы (или основной фрагмент программы);

  • результаты выполнения программы

Контрольные вопросы:

  1. Опишите идею сортировки массива методом прямого выбора и последовательность действий.

  2. Опишите идею сортировки массива методом прямого обмена (методом «пузырька») и последовательность действий.

Приложение: (ваш номер по журналу соответствует номеру варианта)

  1. Организуйте массив, содержащий 20 различных целых чисел. После этого элементы массива упорядочиваются по убыванию и содержимое отсортированного массива выводится на экран.

  2. Организуйте массив, содержащий 20 различных целых чисел. После этого 10 первых элементов массива упорядочиваются по возрастанию, а 10 последних элементов по убыванию. Содержимое отсортированного таким образом массива выводится на экран.

  3. Организуйте массив, содержащий 15 различных целых чисел. После этого отдельно первых 5 элементов, вторых 5 элементов и последних 5 элементов сортируются по возрастанию. Содержимое отсортированного таким образом массива выводится на экран.

  4. Создайте массив, содержащий 10 различных целых чисел. Содержимое массива сортируется по возрастанию, и после этого определяются минимальный и максимальный элементы массива.

  5. Организуйте массив, содержащий 15 различных целых чисел. После этого отдельно первых 5 элементов сортируйте по убыванию, вторых 5 элементов оставьте несортированными и последних 5 элементов сортируются по возрастанию. Содержимое отсортированного таким образом массива выводится на экран.

  6. Организуйте массив, содержащий 20 различных символов. Отсортируйте его по возрастанию.

  7. Организуйте массив содержащий 20 целых чисел. Отсортируйте отдельно элементы с нечётными индексами по возрастанию.

  8. Создайте массив содержащий 20 целых чисел. Отсортируйте его по возрастанию. После этого определите и выведите на экран сумму элементов с чётными индексами.

  9. Организуйте массив содержащий 20 целых чисел. Отсортируйте отдельно элементы с чётными индексами по возрастанию, и элементы с нечётными индексами по убыванию.

  10. Создайте массив, содержащий 15 целых чисел. Отдельно первых 5 элементов массива, вторых 5 элементов и последних 5 элементов отсортируйте по убыванию. Выведите на экран, отсортированный таким образом массива.

  11. Создайте целочисленный массив, содержащий 10 различных чисел. Отсортируйте первую половину массива по возрастанию, а вторую по убыванию. Выведите на экран, отсортированный таким образом массива.

  12. Организуйте массив содержащий 20 целых чисел. Отсортируйте отдельно элементы с чётными индексами по возрастанию.

  13. Создайте массив, содержащий 20 различных целых чисел. Отсортируйте его по возрастанию. После этого замените все элементы массива на противоположные и выведите содержимое обработанного массива на экран.

  14. Создайте массив, содержащий 20 различных целых чисел. Отсортируйте первую половину массива по убыванию, а вторую по возрастанию. Выведите на экран, отсортированный таким образом массива.

  15. Организуйте массив содержащий 20 целых чисел. Отсортируйте отдельно элементы с чётными индексами по убыванию, и элементы с нечётными индексами по возрастанию.