- •Методические указания
- •Операционные системы пк
- •Часть 1
- •Севастополь
- •Требования к оформлению отчета к лабораторной работе
- •Введение
- •Лабораторная работа № 1 Тема: «Основы работы с ос Windows»
- •1.1 Окна ос Windows
- •1.2 Панель задач
- •1.3 Главное меню
- •1.4 Значок Мой компьютер
- •1.5 Контекстное меню
- •1.6 Создание папок и ярлыков
- •1.7 Работа с панелью управления
- •1.8 Завершение работы Windows
- •Лабораторная работа № 2 Тема: «Работа с файловой системой Windows. Стандартные программы Windows»
- •2.1 Папки, ярлыки, файлы
- •2.2 Создание объектов
- •2.3 Запуск программ
- •Лабораторная работа № 3 Тема: «Основы работы с пакетами ms Word и ms Excel»
- •3.1 Панель инструментов и режимы просмотра Microsoft Word
- •3.2 Форматирование текста в редакторе ms Word
- •3.3. Редактор формул в ms Word
- •3.3 Окна редактора, меню и панели инструментов в Excel
- •3.4 Типы данных и форматы представления в Excel
- •3.5 Основные приемы работы в ячейках Excel
- •3.6 Работа с формулами в Excel
- •3.7 Создание диаграмм средствами Excel
- •Часть I 1) Открыть новый документ ms Word
- •Часть II 1) Создать новую книгу ms Excel
- •Лабораторная работа № 4 Тема: «Системы счисления. Формы представления чисел»
- •4.1 Системы счисления
- •4.2 Правила перевода целых чисел
- •4.3 Арифметические операции
- •Лабораторная работа № 5 Тема: «Создание блок-схем алгоритмов в пакете ms Visio»
- •5.1 Основное понятие алгоритма
- •5.2 Блок-схемы алгоритма
- •5.4 Правила применения символов
- •5.4 Создание алгоритмов средствами ms Visio
- •5.5 Создание текстового документа ms Word со схемой алгоритма
- •Лабораторная работа № 6 Тема: «Исследование алгоритмов линейной структуры»
- •6.1 Виды алгоритмических структур
- •6.2 Линейный алгоритмический процесс
- •Лабораторная работа № 7 Тема: «Исследование разветвляющихся алгоритмов»
- •7.1 Разветвляющийся вычислительный процесс
- •7.2 Переключательные алгоритмические процессы
- •Лабораторная работа № 8 Тема: «Исследование алгоритмов циклической структуры»
- •8.1 Цикл с постусловием и с предусловием
- •8.2 Цикл с заданным количеством повторений
- •8.3 Алгоритмы программ с накапливанием
- •Лабораторная работа № 9 Тема: «Разработка алгоритмов, использующих структуру данных массив»
- •Лабораторная работа № 10 Тема: «Разработка алгоритмов, использующих подпрограммы»
- •Лабораторная работа № 11 Тема: «Определение функции сложности алгоритмов»
- •11.1 Функция сложности алгоритма
- •11.2 Виды функции сложности алгоритмов o(I)
- •11.3 Анализ функции сложности по программе
- •Лабораторная работа № 12 Тема: «Исследование рекурсивных и итерационных алгоритмов»
- •12.1 Рекурсия
- •12.2 Итерационные циклы
- •Лабораторная работа № 13 Тема: «Исследование основных алгоритмов сортировок»
- •13.1 Задача сортировки элементов массива
- •13.2 Линейный выбор
- •13.3 Линейный выбор с обменом
- •13.4 Стандартный обмен (метод "пузырька")
- •13.5 Челночная сортировка
- •13.6 Сортировка Шелла
- •13.7 Линейная вставка
- •3.8 Центрированная и двоичная вставки
- •13.9 Быстрая сортировка (метод Хоара)
- •Лабораторная работа № 14 Тема: «Исследование основных алгоритмов поиска»
- •14.1 Последовательный поиск
- •14.2 Бинарный (двоичный) поиск
- •14.3 Интерполяционный поиск
- •Библиографический список
13.1 Задача сортировки элементов массива
В общем случае сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определённом порядке. Цель сортировки - облегчить поиск элементов в таком упорядоченном множестве.
Пусть надо упорядочить n элементов которые назовём записями. Каждая запись имеет свой ключ который и управляет процессом сортировки. Помимо ключа, запись может содержать дополнительную "сопутствующую информацию", которая не влияет на сортировку, но всегда остается в этой записи.
Задача сортировки - найти такую перестановку записей после которой ключи расположились бы в неубывающем порядке:
Основное требование к методам сортировки - экономное использование времени процессора и памяти. Хорошие алгоритмы затрачивают на сортировку n записей время порядка
Существующие методы сортировки обычно разбивают на три класса, в зависимости от лежащего в их основе приема:
а) сортировка выбором,
б) сортировка обменами,
в) сортировка включениями (вставками).
Рассмотрим основные алгоритмы сортировки на примере сортировки целочисленного массива.
13.2 Линейный выбор
Метод предполагает использование рабочего массива, в который помещается отсортированный массив. Количество просмотров определяется количеством элементов массива. Сортировка посредством линейного выбора сводится к следующему:
1) Найти наименьший элемент, переслать его в рабочий массив и заменить его в исходном массиве величиной, которая больше любого реального элемента.
2) Повторить шаг (1). На этот раз будет выбран наименьший из оставшихся элементов.
3) Повторять шаг (1) до тех пор, пока не будут выбраны все n элементов.
13.3 Линейный выбор с обменом
Общая схема алгоритма следующая.
Просмотрим элементы , найдем среди них минимальный элемент и переставим его на первое место. Теперь просмотрим элементы , найдем среди них минимальный элемент и поставим его на второе место. И так до тех пор, пока не останется один элемент.
13.4 Стандартный обмен (метод "пузырька")
Просматриваем элементы и попутно меняем местами те соседние элементы, для которых выполнено неравенство В результате первого просмотра максимальный элемент станет последним ("он вниз - пузыри вверх"). На следующем просмотре аналогичную процедуру проведем над элементами и т.д. Сортировку необходимо закончить, если будет выполнено одно из двух условий:
- после очередного прохода не сделано ни одного обмена;
- сделан проход для элементов
13.5 Челночная сортировка
Челночная сортировка, называемая также "сортировкой просеиванием" или "линейной вставкой с обменом" является наиболее эффективной из всех рассмотренных выше методов и отличается от сортировки обменом тем, что не сохраняет фиксированной последовательности сравнений.
Алгоритм челночной сортировки действует точно так же, как стандартный обмен до тех пор, пока не возникает необходимость перестановки элементов исходного массива. Сравниваемый меньший элемент поднимается, насколько это возможно, вверх. Этот элемент сравнивается в обратном порядке со своими предшественниками по направлению к первой позиции. Если он меньше предшественника, то выполняется обмен и начинается очередное сравнение. Когда элемент, передвигаемый вверх, встречает меньший элемент, этот процесс прекращается и нисходящее сравнение возобновляется с той позиции, с которой выполнялся первый обмен.
Сортировка заканчивается, когда нисходящее сравнение выходит на границу массива.
Процесс челночной сортировки можно проследить на следующем примере:
Исходный массив: 2 7 9 5 4
Нисходящие сравнения: 2 7; 7 9; 9 5;
После перестановки: 2 7 5 9 4
Восходящие сравнения и обмен : 7 5 -> 5 7; 2 5 - конец восходящего сравнения; получен массив : 2 5 7 9 4
Нисходящие сравнения: 9 4
После перестановки: 2 5 7 4 9
Восходящие сравнения и обмен : 7 4 -> 4 7; 5 4 -> 4 5; 2 4 - конец восходящего сравнения; получен массив : 2 4 5 7 9 .