Файл: Алгоритмы сортировки данных (Понятие алгоритма сортировки).pdf

ВВЕДЕНИЕ

Успешное выполнение большинством специалистов своих функциональных обязанностей в настоящее время во многом определяется умелым использованием персональных компьютеров, средств коммуникаций, профессиональных пакетов прикладных программ, различного рода интеллектуальных информационных технологий. Процессы информатизации общества обусловили необходимость формирования у студентов знаний в области информатики и компьютеризации управленческих процессов.

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

Сам термин «информатика» (informatique) возник в 60-х годах во Франции для определения области исследований, связанных с автоматизацией обработки информации с помощью электронных вычислительных машин (ЭВМ). Этот термин был образован слиянием слов information (информация) и automatique (автоматика) для обозначения информационной автоматики или автоматизированной переработки информации.

Данная курсовая работа состоит из двух частей: теоретической и практической.

Целью теоретической части курсовой работы является ознакомление с алгоритмами сортировки, попытка проанализировать их и осветить каждый из них.

В практической части курсовой работы с помощью пакетов прикладных программ (ППП) будут решены и описаны следующие задачи:

• 1. создание таблиц и заполнение таблиц данными;
  2. применение математических формул для выполнения запросов в ППП;
  3. построение графиков.

Краткие характеристики ПК и программного обеспечения, использованных для выполнения и оформления курсовой работы:

• Процессор: Inter Core i7-3612QM 2.10GHz;
• Оперативная память: RAM 8,0Gb;
• Жесткий диск: SDD 126Gb;
• Видеокарта: Intel HD Graphics 4000;
• Клавиатура: Logitech G15;
• Мышь: Logitech G9.

Программные средства: операционная система Windows 10, пакет прикладных программ – MS Office 2019 (из него использованы для выполнения курсовой работы: текстовый процессор MS Word 2019, табличный процессор MS Excel 2019).

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1. Понятие алгоритма сортировки

Алгоритм – это точно определенная последовательность действий, которую необходимо выполнить над исходными данными для достижения решения задачи.

---

Слово «алгоритм» происходит от имени узбекского математика девятого века Аль-Харезми, который сформулировал правило четырёх арифметических действий над многозначными числами. В дальнейшем это слово стало использоваться не только в математике, а фактически любую последовательность действий, приводящих к конечному результату, стали называть алгоритмом, а каждое действие шагом алгоритма. Алгоритм обладает рядом свойств, связанных с необходимостью выполнения определенных требований к процессу вычисления. Это следующие свойства: определённость, массовость, результативность, дискретность.

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

Массовость заключается в том, что алгоритм предназначен для решения целого класса задач, которые отличаются только своими входными условиями.

Результативность означает, что пошаговый процесс решения задачи в соответствии с алгоритмом должен заканчиваться через определенное конечное число шагов.

Формы представления алгоритма:

1. Словесная форма;
2. Словесно-аналитическая форма;
3. В виде блок-схемы (графическое изображение алгоритма);
4. В виде программы на алгоритмическом языке программирования.

Виды алгоритмических структур:

• 1. Линейный алгоритм, в которой все команды выполняются последовательно одна за другой.
  2. Разветвляющийся, в которой в зависимости от условия выполнения либо одна серия команд, либо другая.
  3. Циклический, в которой многократно повторяется некоторый участок алгоритма.

Первое поколение алгоритмических языков - конец 1950-х начало 1960-х. Совершенствовались ассемблерные языки. В настоящее время они применяются для создания драйверов оборудования ПК.

Второе поколение – 60-е годы. В это время появляются универсальные языки высшего уровня: фортран, алгол, кобол, обеспечивающие создание программ для решения задач различного класса.

Третье поколение. С начала 1970-х годов начался переход на создание больших программных комплексов. Они в основном применяются для проектирования приложений баз данных и средств визуального программирования.

В середине 1990-х – четвертое поколение языков программирования, назначение которых для образования инструкции текст программ на универсальном языке программирования. Система четвертого поколения имеет открытую архитектуру и поддерживает значительное число программных продуктов.

---

Языки программирования:

1. Бейсик отличается встроенными математическими функциями и простыми языковыми конструкциями.
2. Паскаль предназначен для решения вычислительных и информационно-логических задач.
3. Си ++ был разработан для облегчения процесса переноса программного обеспечения с одной ЭВМ на другую.
4. Ада ориентирован для применения в системах реального времени и предназначен для разработки программного обеспечения встроенных вычислительных систем.
5. Java (джава) предназначен для создания надёжных, переносимых, распределённых сетевых программных приложений, работающих в архитектуре клиент–сервер, а также удобен для администраторов сети.
6. Другим объектно-ориентировочным языком является язык Delphi (дельпхи). Обеспечивает взаимодействие с базами данных, создание различных видов баз, а также работу экономических программ и сети интернет.
   1. Характеристика основных видов алгоритма сортировки

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле по которому производится сортировка, называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

Пожалуй, никакая другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Существует ли некий «универсальный», наилучший алгоритм? Вообще говоря, нет. Однако, имея приблизительные характеристики входных данных, можно подобрать метод, работающий оптимальным образом.

Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы.

Практически каждый алгоритм сортировки можно разбить на три части:

1. сравнение, определяющее упорядоченность пары элементов;
2. перестановку, меняющую местами пару элементов;
3. собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.

Подобными свойствами обладают и те алгоритмы сортировки, которые рассмотрены ниже. Они отобраны из множества алгоритмов, потому что, во-первых, наиболее часто используются, а во-вторых, потому что большинство остальных алгоритмов является различными модификациями описанных здесь.

Основные виды сортировок:

Сортировка пузырьком (англ. bubble sort) — простой алгоритм сортировки. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.

---

Сортировка методом пузырька имеет сложность O(n2). Для понимания и реализации это — простейший алгоритм сортировки, но эффективен он лишь для небольших массивов.

Пример реализации алгоритма (язык Pascal):

for i := n - 1 downto 1 do

for j := 1 to i do

if a[j] > a[j+1] then

begin

t := a[j];

a[j] := a[j+1];

a[j+1] := t;

end;

Сортировка перемешиванием (шейкер-сортировка) — разновидность пузырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а маленькие — к началу.

Лучший случай для этой сортировки — отсортированный массив (О(n)), худший — отсортированный в обратном порядке (O(n²)).

Сортировка методом вставок (англ. insertion sort) — простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

• прост в реализации
• эффективен на небольших наборах данных
• эффективен на наборах данных, которые уже частично отсортированы
• это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)
• может сортировать список по мере его получения

На каждом шаге алгоритма, мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Выбор очередного элемента, выбираемого из исходного массива — произволен, может использоваться практически любой алгоритм выбора.

Сортировка подсчётом — алгоритм сортировки массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы.

Описание алгоритма. Идея сортировки указана в её названии — нужно подсчитывать число элементов, а затем выстраивать массив. Пусть, к примеру, имеется массив A из миллиона натуральных чисел, меньших 100. Тогда можно создать вспомогательный массив B из 99 (1..99) элементов, «пробежать» весь исходный массив и вычислять частоту встречаемости каждого элемента — то есть если A[i]=a, то B[a] следует увеличить на единицу. Затем «пробежать» счетчиком i массив B, записывая в массив A число i B[i] раз.

Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй».

---

Алгоритм был изобретён Джоном фон Нейманом в 1945 году.

Цифровая сортировка (англ. pigeonhole sort) обладает линейной вычислительной сложностью (О(n)), что является лучшей возможной производительностью для алгоритма сортировки, так как в любом таком алгоритме каждый сортируемый элемент необходимо просмотреть хотя бы однажды. Однако, применение алгоритма цифровой сортировки целесообразно лишь тогда, когда сортируемые предметы имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым списком. Эффективность алгоритма падает всякий раз, когда несколько различных элементов попадает в одну ячейку. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза. Так что, для простоты и с целью отличить «классическую» цифровую сортировку от её многочисленных вариантов, укажем, что подсчёт должен быть обратимым: если два элемента попадают в одну ячейку, то они должны иметь одинаковое значение. Несколько элементов с одним значением в одной ячейке не портят картину — их можно просто вставить в отсортированный список рядом, один за другим (это позволяет применять цифровую сортировку в качестве устойчивой).

Алгоритм цифровой сортировки действует следующим образом:

1. Создаём массив изначально пустых «ячеек», по одной для каждой величины из диапазона ключей.
2. Просматриваем изначальный массив, помещая каждый его элемент в свою ячейку.
3. Проходим по массиву ячеек в нужном порядке и переносим элементы из непустых ячеек обратно в первоначальный массив.

Эффективность этого алгоритма сильно зависит от плотности элементов в массиве ячеек. Если элементов этого массива намного больше, чем сортируемых предметов, то шаги 1 и 3 будут относительно медленными.

Сортировку подсчётом применяют редко, потому что её требования редко удовлетворяются, и часто бывает проще применить другие, более гибкие и почти такие же быстрые алгоритмы сортировки. В особенности, блочная сортировка является более практичным вариантом сортировки подсчётом. В некотором роде, быстрая сортировка представляет собой обобщённую сортировку подсчётом (всего с двумя ячейками в каждый момент времени).

Поразрядная сортировка — быстрая устойчивая сортировка за линейное время, использовалась в устройствах для сортировки перфокарт. Пригодна для сортировки любых элементов, состоящих из цепочек над фиксированным алфавитом, на котором задано отношение сравнения. Для сортировки следует применять любой устойчивый алгоритм, используя в качестве ключа сначала младшую букву, затем повторять этот процесс для старших букв.

---