- •Лекция 1.
- •Контрольные вопросы.
- •Лекция 2.
- •Контрольные вопросы.
- •Лекция 3.
- •Контрольные вопросы.
- •Лекция 4.
- •Контрольные вопросы.
- •Лекция 5.
- •Контрольные вопросы.
- •Лекция 6.
- •Контрольные вопросы.
- •Лекция 7.
- •Моделирование как метод познания.
- •Статистические и динамические информационные модели.
- •Формы представления информационных моделей.
- •Классификация информационных моделей.
- •Пример иерархической статистической информационной модели.
- •IV. Объектно-ориентированное моделирование.
- •Контрольные вопросы.
- •Лекция 8.
- •Лекция 9.
- •Контрольные вопросы.
- •Лекция 10.
- •Контрольные вопросы.
- •Лекция 11.
- •Контрольные вопросы.
- •Лекция 12.
- •Обобщенная схема циклического алгоритма
- •Составление алгоритмов циклической и сложной структуры.
- •Контрольные вопросы.
- •Лекция 13.
- •Контрольные вопросы.
- •Лекция 14.
- •1. Краткая характеристика языка Паскаль.
- •2. Интегрированная среда программирования Turbo Pascal.
- •2.1. Клавиши оперативного вмешательства.
- •2.2. Основное меню.
- •2.3. Локальное меню.
- •2.4. Экранный редактор.
- •Контрольные вопросы.
- •Лекция 15.
- •1. Символы языка.
- •2. Комментарии.
- •3. Простейшие конструкции языка.
- •Выражения
- •Контрольные вопросы.
- •Лекция 16.
- •Структура программы Turbo Pascal.»
- •Структура программы на языке Турбо Паскаль
- •Контрольные вопросы.
- •Лекция 17.
- •2.Простейшие операторы.
- •3.Операторы ввода - вывода.
- •Контрольные вопросы.
- •Лекция 18.
- •Контрольные вопросы.
- •Лекция 19.
- •Контрольные вопросы.
- •Лекция 20.
- •1.Понятие подпрограммы.
- •2.Процедуры.
- •3.Функции.
- •Контрольные вопросы.
- •Лекция 21.
- •1.Понятие массив данных.
- •2.Операция над массивами.
- •3. Одномерные массивы.
- •3.2.Способы задания одномерных массивов.
- •3.3.Описание типа одномерных массивов.
- •4.Двумерные массивы.
- •4.1Способы объявления двумерного массива.
- •Контрольные вопросы.
- •Лекция 22.
- •1. Сортировка массива.
- •1.1.Линейная сортировка (сортировка отбором)
- •1.2.Сортировка методом пузырька.
- •1.3.Метод быстрой сортировки с разделением
- •2. Бинарный поиск в упорядоченных массивах.
- •Контрольные вопросы.
- •Лекция 23.
- •1.Графический экран.
- •2.Текстовый экран.
- •3.Управление звуком.
- •Контрольные вопросы.
- •Лекция 24.
- •Основы взаимодействия пользователя с системой
- •Навигация по дискам и каталогам с помощью пиктограммы «Мой компьютер»
- •Контрольные вопросы.
- •Лекция 25.
- •Контрольные вопросы.
- •Лекция 26.
- •Контрольные вопросы.
- •Лекция 27.
- •1 Способ:
- •2 Способ:
- •Контрольные вопросы.
- •Лекция 28.
- •1. Основные понятия электронных таблиц.
- •2. Ввод, редактирование и форматирование данных.
- •3. Вычисления в электронных таблицах.
- •Контрольные вопросы.
- •Лекция 29.
- •Контрольные вопросы.
Контрольные вопросы.
1. Определите понятие «массив данных».
2. Какие операции используются над массивами?
3. Каковы способы задания одномерных массивов?
4. Как могут объявляться двумерные массивы?
Лекция 22.
Тема: «Сортировка массива».
1. Сортировка массива.
Сортировка – один из наиболее распространенных процессов современной обработки данных. Сортировкой называется распределение элементов множества по группам в соответствии с определенными правилами. Например, сортировка элементов массива, в результате которой получается массив, каждый элемент которого, начиная со второго, не больше стоящего от него слева, называется сортировкой по не возрастанию.
Рассмотрим следующую задачу:
Составить программу, которая выводит несортированный массив целых чисел на экран, затем выполняет его сортировку по не возрастанию и выводит отсортированный массив на экран.
Рассмотрим три метода сортировки одного и того же массива М из 20-ти целых чисел. Использование одного массива позволит объективно сравнить эффективность разных методов.
В связи с этим описание массива во всех примерах выполним следующим образом:
Const
Count=20;
M: array [1.. Count] of
Byte=(9,11,12,3,19,1,5,17,10,18,3,19,17,9,12,20,20,19,2,5);
Для сравнения эффективности разных способов сортировки введем целую переменную А, значение которой будет равно числу итераций (повтор просмотра массива). Для наблюдения текущего состояния массива после каждой перестановки элементов будем выводить его на экран:
for L:=1 to Count do Write (‘’,M[L]); Writeln(′Число итераций′,А);
1.1.Линейная сортировка (сортировка отбором)
Идея линейной сортировки по не возрастанию заключается в том, чтобы, последовательно просматривая весь массив, отыскать наибольшее число и поместить его на первую позицию, обменяв его с элементом, который ранее занимал первую позицию. Затем просматриваются все остальные элементы массива и выполняется аналогичная операция по отбору из рассматриваемой части массива максимального элемента и обмену местами этого элемента и первого в рассматриваемой части и т.д.
Введем в разделе описание следующие целые переменные:
I-для указания позиции первого элемента в рассматриваемой части массива;
J-для указания позиции очередного сравниваемого с ним элемента;
N-для временного хранения значения первого элемента для обмена значениями с максимальным из рассматриваемой части массива;
L-параметр цикла при выводе текущего значения элементов массива в процессе сортировки для наблюдения происходящих в массиве наблюдений;
A-переменная, значение которой будет равно числу перестановок элементов.
Вначале запишем вывод исходного массива на экран:
Writeln (′Исходный массив:′);
for I:=1 to Count do Write (‘’,M[I]);
Writeln;
Переход началом сортировки установим значение счетчика итераций А, равно 0. для сортировки организуем два цикла for. Внешний цикл с параметром I, указывающим позицию первого элемента в не отсортированной части массива, и внутренний цикл с параметром J, указывающим позицию очередного, сравниваемого с первым, элемента не отсортированной части массива. Сравнение элементов запишем оператором:
if M[I]<M[J] then
begin
N:= M[I];
M[I]:= M[J];
M[J]:=N;
end;
Если условие M[I]<M[J] выполняется, т.е. в не отсортированной части массива найден элемент, больший, чем первый, то обменять местами эти элементы. Обмен осуществляется следующим образом: сначала значение M[i] запоминается в переменой N, затем значение элемента массива из J-й позиции записывается в 1-го позицию, а после этого в J-ю позицию массива записывается значение переменной N. Для наблюдения изменений состояния массива после каждой перестановки зададим цикл вывода значений всех элементов массива и напечатаем текущее значение числа перестановок элементов А следующим образом:
for L:=1 to Count do Write (‘’,M[L]); Writeln(′Число итераций=′,А);
Полный текст программы линейной сортировки массива М по невозрастанию может быть записан так:
Program Sort Lin; {Линейная сортировка по невозрастанию}
const
Count=20;
M: array [1.. Count] of byte=(9, 11, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 20, 19, 2, 5);
var
I, J, N, L: Byte;
A:integer;
begin
Writeln(′Исходный массив:′);
for I:=1 to Count do
Write (‘’, M [L]); Writeln
A:=0;
for I:=1 to Count-1do{Изменять размер неотсортированной части массива}
for J:=I+1 to Count do {Сравниваем поочередной 1-й элемент неотсортированной части массива со всеми отI+1-го до конца}
begin
A:=A+1;
if M[I]<M[J] than {Если в неотсортированной части массива нашли элемент/больший, чем 1-й, то обменять их местами}
begin
N: = M [I]; {Запомнить на время значение M [I]}
M [I]: = M [J];
M [J]: = N;
end;
for L:=1 to Count do
Write (‘’, M [L]); Writeln (′Число итераций=′,А);
end;
end.