- •Предисловие
- •Основные навыки и умения
- •Логическая культура: знание логики, логическая интуиция.
- •Языковые знания и умения.
- •Поисковые знания и умения.
- •Алгоритмические навыки и умения.
- •Общие подходы к построению алгоритмов
- •Тестирование и сопровождение программ
- •Обязательный минимум содержания среднего (полного) общего образования
- •Технология обработки текстовой информации
- •Введение в информатику
- •Системы счисления
- •Перевод из десятичной системы счисления
- •Перевод в десятичную систему счисления
- •Перевод чисел из двоичной системы счисления в восьмеричную, шестнадцатеричную системы и обратно
- •Выполнение арифметических операций в позиционных системах счисления
- •Элементы математической логики
- •Логические законы
- •Алгоритм и его свойства
- •Исполнители. Компьютер - универсальный исполнитель
- •Работа компьютера
- •Turbo pascal - исполнитель паскаль-программ
- •Конструкции Паскаля
- •Типы данных
- •Целый тип данных
- •Вещественный тип данных
- •Символьный тип данных
- •Логический тип данных
- •Выражения
- •Операторы ввода-вывода
- •Оператор присваивания
- •Общий вид программы на Паскале
- •Условный оператор
- •If логическое_выражение then оператор1 else оператор2;
- •If логическое_выражение then оператор1;
- •Операторы цикла
- •Построение линейных алгоритмов
- •Построение ветвящихся алгоритмов
- •Построенние циклических алгоритмов
- •Нахождение суммы
- •Вложенные циклы
- •Переборный метод решения задач
- •Численные методы
- •Метод итераций
- •Метод половинного деления
- •Вычисление определенного интеграла методом трапеций
- •Случайные числа
- •Метод Монте-Карло (метод статистических испытаний)
- •Массивы Одномерные массивы
- •Перебор элементов массива
- •Перебор подмассивов
- •Классы задач по обработке массивов
- •Задачи первого класса
- •Задачи второго класса
- •Задачи третьего класса
- •Задачи четвертого класса
- •Сортировка массивов
- •Сортировка вставками
- •Сортировка пузырьком (обменом)
- •Сортировка выбором
- •Сортировка фон Неймана (слиянием)
- •Двумерные массивы
- •Обработка строк
- •Процедуры и функции
- •Рекурсия
- •Работа с графикой
- •Классы программного обеспечения
- •Компиляция и интерпретация
- •Текстовый редактор
- •Электронные таблицы
- •Системы управления базами данных (субд)
- •Пример решения экзаменационного билета
- •Контрольные работы
- •Контрольная работа №1
- •Контрольная работа № 2
- •Контрольная работа № 3
- •Контрольная работа № 4
- •Контрольная работа № 5
- •Библиографический список
Сортировка массивов
Часто удобно иметь данные (особенно, если их много), расположенные в порядке возрастания или убывания. Такое упорядочивание в программировании называется сортировкой. Цель сортировки - облегчить поиск элементов в отсортированном массиве. Как правило, при сортировке выдвигается требование экономии памяти, поэтому сортировка осуществляется без использования вспомогательного массива. Сортировать можно любые данные. Важно только, чтобы их можно было тем или иным способом сравнивать. Существует множество различных алгоритмов сортировки. Одни из них простые, но более медленные, другие - быстрые, но более сложные. Одни сортируют массив каждый раз заново, другие - распознают уже упорядоченные части массива и поэтому работают быстрее. В рамках данного пособия будут рассмотрены следующие алгоритмы сортировки:
-
вставки;
-
пузырька;
-
выбора;
-
фон Неймана.
Сортировка вставками
Алгоритм. Последовательность чисел разбивают на отсортированную и не отсортированную. Пусть первые k элементов массива уже упорядочены, для определенности, по не убыванию. Берется k+1-й элемент и размещается среди первых k элементов так, чтобы упорядоченными оказались уже k+1 первых элементов. Этот метод применяется при изменяющемся k от 1 до n-1, где n - количество элементов в заданной последовательности.
Пример. Пусть дан массив {4, 5, 2, 3, 9, 1}, который необходимо упорядочить по возрастанию, используя метод вставок.
ш1 4 | 5 2 3 9 1 5 остается на месте.
ш2 4 5 | 2 3 9 1 2 встает в начало массива.
ш3 2 4 5 | 3 9 1 3 встает за 2.
ш4 2 3 4 5 | 9 1 9 остается на месте.
ш5 2 3 4 5 9 | 1 1 встает на первое место.
1 2 3 4 5 9 результат.
Из примера видно, что при поиске подходящего места очередного элемента х из не отсортированного множества, необходимо этот элемент сравнивать с очередным элементом aj в отсортированном множестве и либо вставлять х, либо продвигаться влево. Таким образом, этот процесс может закончиться при двух различных условиях:
1. найден элемент aj, меньший, чем х;
2. достигнут левый конец готовой последовательности.
Реализация таких циклов была рассмотрена ранее. Здесь рассмотрим хорошо известный прием фиктивного элемента или барьера. Суть которого состоит в том, что вводится еще один элемент массива с индексом 0, величина которого равна значению элемента из не отсортированной части х, который пытаемся разместить в отсортированном множестве, т.е. а0 = х, для чего необходимо расширить диапазон индексов в описании массива от 0 до n. И пока х < aj, продолжаем двигаться по отсортированной части массива.
program sort_insert;
const n = 30;
var a: array [0..n] of integer;
x, i, j: integer;
begin
for i := 1 to n do
read(a[i]); {формирование массива}
for i := 2 to n do
begin
x := a[i]; a[0] := x; j := i-1;
while x < a[j] do {поиск места элемента в упорядоченной части}
begin
a[j + 1] := a[j]; {продвижение по массиву}
j := j - 1
end;
a[j + 1] := x {вставка элемента в нужное место}
end;
for i := 1 to n do
writeln (a[i]);
end.