Алгоритмы сортировки.
Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Классификация алгоритмов сортировки
Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.
Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n log n), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.
Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:
Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат.
В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.
Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т. е. в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.
Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
Объём данных не позволяет им разместиться в ОЗУ.
Также алгоритмы классифицируются по:
потребности в дополнительной памяти или её отсутствии
потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствии таковой.
-
Содержание
- Основные понятия информатики: информационные технологии, информатизация общества, информационные ресурсы. Информатика как наука и как прикладная дисциплина
- Федеральный закон Об информации, информационных технологиях и о защите информации от 8 июля 2006 года
- История развития компьютерной техники.
- Понятие информации, ее классификация, свойства информации, представление информации, единицы измерения информации.
- Формулы измерения информации Чартли и Шеннона, примеры вычислений.
- Системы счисления. Позиционные системы счисления, их представление.
- Двоичная, восьмеричная, шестнадцатеричная системы счисления.
- Правила преобразования чисел из одной системы счисления в другую.
- Примеры
- 2. Из двоичной и шестнадцатеричной систем счисления - в десятичную.
- 4. Из шестнадцатеричной системы счисления в двоичную:
- Правила перевода правильных дробей
- 1. Из десятичной системы счисления - в двоичную и шестнадцатеричную:
- 2. Из двоичной и шестнадцатеричной систем счисления - в десятичную.
- 3. Из двоичной системы счисления в шестнадцатеричную:
- 4. Из шестнадцатеричной системы счисления в двоичную:
- Понятие информационной системы. Структура ис.
- Процессы, обеспечивающие работу ис.
- Классификация информационных систем, свойства ис. Классификация по архитектуре
- Классификация по степени автоматизации
- Классификация по характеру обработки данных
- Классификация по сфере применения
- Классификация по охвату задач (масштабности)
- Типы информационных процедур.
- 1. Поиск.
- 2. Сбор и хранение.
- 3. Передача.
- 4. Обработка.
- 5. Использование.
- 6. Защита.
- Классификация ис по направлению деятельности
- Направления анализа функционирования корпоративной сети
- Экспертные системы их классификация
- Базовые функции экспертных систем
- Приобретение знаний
- Представление знаний
- Управление процессом поиска решения
- Разъяснение принятого решения
- Представление знаний. Классификация модеклей представления знаний.
- Понятие операционной системы. История развития ос.
- 1946 Г. – eniac (Electronic Numerical Integrator and Computer) – полное отсутствие какого-либо по, программирование путем коммутации устройств.
- 1952 Г. – Первая ос создана исследовательской лабораторией фирмы General Motors для ibm-701.
- 1955 Г. – ос для ibm-704. Конец 50-х годов: язык управления заданиями и пакетная обработка заданий.
- Основные принципы построения операционных систем.
- Классификация по компьютерной системы.
- Состав компонентов и функций ос
- Особенности алгоритмов управления ресурсами.(см. 27).
- Классификация ос Классификация ос
- Особенности алгоритмов управления ресурсами
- Особенности аппаратных платформ
- Особенности областей использования
- Особенности методов построения
- Сетевые ос. Варианты построения сетевых ос.
- Основные принципы построения системы информационной безопасности.
- Перечень и содержание огрганизационно-распорядительных документов иб.
- Основные механизмы доступа к информационным ресурсам.
- Способы и методы аутентификации.
- Средства защиты ис от потери информации.
- Брандмауэры и антивирусные пакеты.
- Базы и банки данных.
- Информационные сети. История развития информационных сетей.
- Классификация сетей
- Основные топологии лвс
- Понятие логической структуры сети. Элементы логической структуры.
- Основные понятия: интернет, провайдер, хост, сетевой протокол, ip-адрес, домен.
- Архитектура клиент-сервер, одноранговые сети и сети с выделенным сервером, их преимущества и недостатки.
- Понятие сервис ориентированной архитектуры.
- Алгоритм, свойства алгоритма, формы записи алгоритма, скорость выполнения алгоритма.
- Рекурсивные алгоритмы. Сущность рекурсии
- Алгоритмы сортировки.
- Понятие модели, численного метода. Подходы к реализации численных методов
- Этапы реализации решения численных задач. Методы решения численных задач.
- Алгоритмы решения задачи нахождения корней полинома: шаговый метод, метод половинного деления, метод Ньютона, метод простой итерации.
- Численные методы решения задач аппроксимации.
- Методы численного интегрирования.
- Методы одномерной оптимизации.