 |
Быстрая сортировка (метод хоара)
|
|
|
|
Введение
Успешное выполнение большинством специалистов своих функциональных обязанностей в настоящее время во многом определяется умелым использованием персональных компьютеров, средств коммуникаций, профессиональных пакетов прикладных программ, различного рода интеллектуальных информационных технологий. Процессы информатизации общества обусловили необходимость формирования у студентов знаний в области информатики и компьютеризации управленческих процессов.
Одно из широко используемых понятий информатики определяет ее как науку, изучающую общие свойства информации, а также методы, процессы, технические и программные средства для ее автоматизированной обработки.
Сам термин «информатика» (informatique) возник в 60-х годах во Франции для определения области исследований, связанных с автоматизацией обработки информации с помощью электронных вычислительных машин (ЭВМ). Этот термин был образован слиянием слов information (информация) и automatique (автоматика) для обозначения информационной автоматики или автоматизированной переработки информации.
Даннаякурсовая работа состоит из двух частей: теоретической и практической.
В теоретической части рассматривается тема «Алгоритмы сортировки».
В практической части курсовой работы с помощью пакетов прикладных программ (ППП) будут решены и описаны следующие задачи:
1. создание таблиц и заполнение таблиц данными;
2. применение математических формул для выполнения запросов в ППП;
Понятие алгоритма
Алгоритм – это точно определенная последовательность действий, которую необходимо выполнить над исходными данными для достижения решения задачи.
Слово «алгоритм» происходит от имени узбекского математика девятого века Аль-Харезми, который сформулировал правило четырёх арифметических действий над многозначными числами. В дальнейшем это слово стало использоваться не только в математике, а фактически любую последовательность действий, приводящих к конечному результату, стали называть алгоритмом, а каждое действие шагом алгоритма. Алгоритм обладает рядом свойств, связанных с необходимостью выполнения определенных требований к процессу вычисления. Это следующие свойства: 1) определённость; 2) массовость; 3) результативность; 4) дискретность. Определённость алгоритма означает, что каждый шаг алгоритма должен быть точен, общепонятен, и исключать возможность различного толкования, другими словами алгоритм должен быть таким, чтобы его мог повторить любой пользователь. Массовость заключается в том, что алгоритм предназначен для решения целого класса задач, которые отличаются только своими входными условиями. Результативность означает, что пошаговый процесс решения задачи в соответствии с алгоритмом должен заканчиваться через определенное конечное число шагов.
|
|
|
Формы представления алгоритма:
1. словесная форма
2. формульно-словесная
3. в виде блок-схемы (графическое изображение алгоритма)
4. в виде программы на алгоритмическом языке программирования.
Виды алгоритмических структур:
1. Линейный алгоритм, в которой все команды выполняются последовательно одна за другой.
2. Разветвляющийся, в которой в зависимости от условия выполнения либо одна серия команд, либо другая.
3. Циклический, в которой многократно повторяется некоторый участок алгоритма.
1 поколение алгоритмических языков – конец 1950-х начало 1960-х. Совершенствовались ассемблерные языки. В настоящее время они применяются для создания драйверов оборудования ПК.
2 поколение – 60-е годы. В это время появляются универсальные языки высшего уровня: ФОРТРАН, АЛГОЛ, КОБОЛ, обеспечивающие создание программ для решения задач различного класса.
|
|
|
3 поколение. С начала 1970-х годов начался переход на создание больших программных комплексов. Они в основном применяются для проектирования приложений баз данных и средств визуального программирования.
В середине 1990-х – 4 поколение языков программирования, назначение которых для образования инструкции текст программ на универсальном языке программирования. Система 4 поколения имеет открытую архитектуру и поддерживает значительное число программных продуктов.
Языки программирования:
1. Бейсик отличается встроенными математическими функциями и простыми языковыми конструкциями.
2. Паскаль предназначен для решения вычислительных и информационно-логических задач.
3. Си + + был разработан для облегчения процесса переноса программного обеспечения с одной ЭВМ на другую.
4. Ада ориентирован для применения в системах реального времени и предназначен для разработки программного обеспечения встроенных вычислительных систем.
5. Java (джава) предназначен для создания надёжных, переносимых, распределённых сетевых программных приложений, работающих в архитектуре клиент–сервер, а также удобен для администраторов сети.
6. другим объектно-ориентировочным языком является язык Delphi (дельпхи). Обеспечивает взаимодействие с базами данных, создание различных видов баз, а также работу экономических программ и сети интернет.
Алгоритмы сортировки
Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы.
Практически каждый алгоритм сортировки можно разбить на три части:
1) сравнение, определяющее упорядоченность пары элементов;
2) перестановку, меняющую местами пару элементов;
3) собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.
Подобными свойствами обладают и те алгоритмы сортировки, которые рассмотрены ниже. Они отобраны из множества алгоритмов, потому что, во-первых, наиболее часто используются, а во-вторых, потому что большинство остальных алгоритмов является различными модификациями описанных здесь.
|
|
|
Быстрая сортировка (метод хоара)
Этот метод, называемый также быстрой сортировкой(QuickSort), был Разработан в 1962 г. (его разработал Charles Antony Richard Hoare).
Суть метода заключается в том, чтобы найти такой элемент множества, подлежащего сортировке, который разобьет его на два подмножества: те элементы, что меньше делящего элемента, и те, что не меньше его. Эту идею можно реализовать многими способами.
Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:
Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного – справа от него. Обычный алгоритм операции:
два индекса – l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно;
вычисляется опорный элемент m;
индекс l последовательно увеличивается до m или до тех пор, пока l‑й элемент не превысит опорный;
индекс r последовательно уменьшается до m или до тех пор, пока r‑й элемент не окажется меньше опорного;
если r = l – найдена середина массива – операция разделения закончена, оба индекса указывают на опорный элемент;
если l < r – найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r или l соответственно.
|
|
|
Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно завершится.
Метод Шелла
Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея этого алгоритма заключается в устранении массового беспорядка в массиве, сравнивая далеко стоящие друг от друга элементы. Интервал между сравниваемыми элементами постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).
Сортировка Шелла (англ. Shell sort) – алгоритм сортировки, идея которого состоит в сравнении элементов, стоящих не только рядом, но и на расстоянии друг от друга. Иными словами – сортировка вставками с предварительными «грубыми» проходами.
При сортировке Шелла сначала сравниваются и сортируются между собой ключи, отстоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть, обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки вставками или пузырьком (но она не предпочтительна, так как все равно остается медленной) каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, при сортировке Шелла же это число может быть больше).
Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
отсутствие потребности в памяти под стек
отсутствие деградации при неудачных наборах данных – qsort легко деградирует до O (n²), что хуже, чем худшее гарантированное время для сортировки Шелла.
Пример
Пусть дан список A = (32,95,16,82,24,66,35,19,75,54,40,43,93,68) и выполняется его сортировка методом Шелла, а в качестве значений d выбраны 5,3,1.
На первом шаге сортируются подсписки A, составленные из всех элементов A, различающихся на 5 позиций, то есть подсписки A 5,1 = (32,66,40), A 5,2 = (95,35,43), A 5,3 = (16,19,93), A 5,4 = (82,75,68), A 5,5 = (24,54).
|
|
|
В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.
Процесс завершается обычной сортировкой вставками получившегося списка.
|
|
|
