Главная
страница 1
Министерство образования и науки Российской Федерации

федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Санкт-Петербургский государственный технологический институт (технический университет)

Профиль: Системный Анализ в Химической Промышленности

Факультет Информационных технологий и управления

Кафедра Системного Анализа

Учебная дисциплина Основы процедурно-структурного программирования задач системного анализа объектов химической технологии

Пояснительная записка к курсовому проекту

Тема проекта: Сортировка данных. Обзор. Анализ. Реализация.

Исполнитель

Студент гр.426 (подпись, дата) Антоненко В.Н,

Руководитель

Доцент каф. СФПР и У (подпись, дата) Рогов А.Ю.

(оценка)

Содержание Санкт-Петербургский государственный технологический институт (технический университет)

Кафедра систем автоматизированного проектирования и управления

ЗАДАНИЕ

По изученному курсу Основ Процедурно-Структурного Программирования

«Разработка программного обеспечения для сортировки данных на языке программирования С++»

Направление подготовки 220000 «Автоматика и управление»

Уровень подготовки

Направление подготовки 220100 «Системный Анализ и Управление»



Студент Антоненко Василь Николаевич

Курс: I

Группа 426

Тема: Сортировка данных. Обзор. Анализ. Реализация.

Перечень вопросов, подлежащих разработке:

1 Аналитический обзор

1.1Общая постановка задачи линейного программирования

1.2Математическая модель задачи линейного программирования

1.3Каноническая форма задачи линейного программирования

2 Основная часть.

2.1Постановка задачи

2.2Составление математической модели задачи

2.3Алгоритмы решения задачи симплексным методом

2.4Построение начального опорного решения методом Гаусса

2.5Решение задачи
Перечень программного обеспечения: Microsoft Windows 7, Microsoft Office 2007, Microsoft Visual Studio 2010

Исходные данные к проекту(источники):

Intuit.ru

Wikipedia.org


Введение.

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



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

  •  алгоритмы сортировки находят очень широкое применение

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

  •  используются несовершенные алгоритмы сортировки

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

    1. Классы методов сортировки

1.1 Основные классы методов сортировки

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

Все методы можно разделить на четыре основных класса:


  •  Сортировка вставками

  •  Сортировка подсчетом

  •  Обменная сортировка

  •  Сортировка посредством выбора

Эти классы включают в себя все множество методов внутренней сортировки, а также все множество всех известных на сегодняшний день  их усовершенствований. Причем стоит отметить, что нельзя провести четкую грань между этими классами: методы сортировки очень тесно взаимосвязаны и похожи друг на друга, что создает определенные связи между классами методов.  Остановимся более подробно на этих классах.
1.2 Сортировка вставками

Массив делится на две части - отсортированную и неотсортированную. В начале работы в отсортированную часть входит только один первый элемент. Алгоритм выполняетn-1 проход, на каждом из которых поочередно выбираются элементы из неотсортированной части и вставляются в отсортированную часть таким образом, чтобы не нарушить в ней упорядоченность элементов.
На некотором i-м проходе элементы a1, a2, ..., ai составляют отсортированную часть, а элементы ai+1, ai+2, …, an - неотсортированную. Если f(ai) ≤ f(ai+1), то элемент ai+1включается в отсортированную часть. В противном случае значение ai+1 временно сохраняется в переменной s = ai+1, а элемент ai сдвигается на одну позицию вправо.
Далее ключ f(s) поочередно сравнивается с ключами следующих элементов из отсортированной части справа налево, т.е. с ключами f(ak), k = i-1, i-2, ..., 1. Если f(S) < f(ak), то элемент ak сдвигается на одну позицию, вправо. В противном случае элемент S записывается в k+1-ю позицию.
Скорость сортировки простыми вставками можно увеличить, если для поиска позиции элемента ai+1 в отсортированной части использовать метод бинарного поиска, так как элементы упорядочены. Это уменьшает общее число сравнений от O(n2) до O(n log2n), но количество перестановок элементов при этом не уменьшается и имеет порядок O(n2).

1.3 Сортировка подсчетом

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

Для описания данного и других методов сортировки введем некоторые определения. Пусть дано Nэлементов, которые необходимо упорядочить:

                     

 Назовем их записями. Также каждая запись   имеет свой ключ , который и управляет процессом сортировки. На множестве элементов abc вводится соотношение “ < ”, таки образом, что выполняется:


  1.  справедливо только одно из соотношений: a < ba = bb < a

  2.  если a < b и b < c то a < c

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

                  

Теперь вернемся к нашему методу. Его смысл заключается в том, чтобы подсчитать количество ключей меньших каждого из ключей сортируемых элементов. То есть, если меньше ключа  имеется j ключей, то его положение в таблице ключей должно быть j+1. Очевидно, такой подсчет можно выполнить путем сравнений:

 

Но очевидно, что в этом алгоритме половина сравнений излишне, и его можно реализовать так:



 

Для реализации данного алгоритма целесообразно использовать дополнительную таблицу count[n]. В результате окончательное положение записи будет определено значением count[j] + 1. Итак, алгоритм (А) сортировки методом подсчета выглядит так:

    А_1. Установить count[1] .. count[N] равными 0

 А_2. [цикл по i] Выполнить шаг А_3 при i = N .. 2

 А_3. [цикл по j] Выполнить шаг А_4 при j = N .. 1

 А_4. если , то увеличить count[j] на 1; иначе увеличить count[i]

Отметим, что данный алгоритм не предусматривает перестановку самих записей. В чем то этот алгоритм похож на сортировку таблицы адресов, но в отличие от последней элемент  count[j] указывает куда нужно отправить элемент , а не элемент, который нужно отправить на место . Стоит отметить, что этот алгоритм дает верно упорядоченный файл записей независимо от числа одинаковых ключей.

Скорость работы такого алгоритма выражается формулой.



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

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:



  • Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшеесреднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n2). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в Ω(n log n) сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью O(n log log n log log log n), использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О - обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за O(log2 n) операций. При этом число n должно быть заранее известно;

  • Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют O(log n) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляетO(1)). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

Свойства и классификация.

  • Устойчивость (англ. stability) — устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами[3].

  • Естественность поведения — эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

  • Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n log n), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

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

    • В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.

  • Внешняя сортировка оперирует запоминающими устройствами большого объёма, но не с произвольным доступом, а последовательным (упорядочение файлов), т. е. в данный момент «виден» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным во внешней памяти производится намного медленнее, чем операции с оперативной памятью.

    • Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.

    • Объём данных не позволяет им разместиться в ОЗУ.

Также алгоритмы классифицируются по:

  • потребности в дополнительной памяти или её отсутствию

  • потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствию таковой

Список алгоритмов сортировки.

Алгоритмы устойчивой сортировки


  • Сортировка выбором (Selection sort) — Сложность алгоритма: O(n2); поиск наименьшего или наибольшего элемента и помещение его в начало или конец упорядоченного списка

  • Сортировка пузырьком (англ. Bubble sort ) — сложность алгоритма: O(n2); для каждой пары индексов производится обмен, если элементы расположены не по порядку.

  • Сортировка перемешиванием (Шейкерная, Cocktail sort, bidirectional bubble sort) — Сложность алгоритма: O(n2)

  • Гномья сортировка — имеет общее с сортировкой пузырьком и сортировкой вставками. Сложность алгоритма — O(n2).

  • Сортировка вставками (Insertion sort) — Сложность алгоритма: O(n2); определяем где текущий элемент должен находиться в упорядоченном списке и вставляем его туда

  • Сортировка слиянием (Merge sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; выстраиваем первую и вторую половину списка отдельно, а затем — сливаем упорядоченные списки

  • Сортировка с помощью двоичного дерева (англ. Tree sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти

  • Алгоритм сортировки Timsort (англ. Timsort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; Комбинированный алгоритм (используется сортировка вставками и сортировка слиянием. Разработан для использования в языке Python[4]

  • Сортировка подсчётом (Counting sort) — Сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти (рассмотрено 3 варианта)

  • Блочная сортировка (Корзинная сортировка, Bucket sort) — Сложность алгоритма: O(n); требуется O(k) дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций "переставить" и "сравнить".


Сортировка выбором


Сортировка выбором (Selection sort) — алгоритм сортировки. Может быть реализован и как устойчивый и как неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное время.

Шаги алгоритма:



  1. находим номер минимального значения в текущем списке

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

  3. теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы

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

Пример неустойчивой реализации:

template

void selection(Item a[], int len) {



/* внешний цикл. i – позиция первого неотсортированного элемента на данной итерации */

for (int i = 0; i < len - 1; i++) {

int min = i; /* min – позиция минимального элемента */

/* внутренний цикл. если найден элемент строго меньший текущего минимального, записываем его индекс как минимальный */

for(int j = i + 1; j < len; j++) {

if(a[j] < a[min])

min = j;


}

if(min != i) /* минимальный элемент не является первым неотсортированным, обмен нужен */

exch(a[i], a[min]);

}

}



Покажем, почему данная реализация является неустойчивой.
Рассмотрим следующий массив из элементов, каждый из которых имеет два поля. Сортировка идет по первому полю.
Массив до сортировки:
{ (2, a), (2, b), (1, a) }
Уже после первой итерации внешнего цикла будем иметь отсортированную последовательность:
{ (1, a), (2, b), (2, a) }
Теперь заметим, что взаимное расположение элементов (2, a) и (2, b) изменилось. Таким образом, рассматриваемая реализация является неустойчивой.

Так как после каждого прохода по внутреннему циклу делается только один обмен, то общее число обменов равно N-1, что в N/2 раз меньше, чем в сортировке пузырьком.


Число проходов по внутреннему циклу равно N-1 даже в случае сортировки частично или полностью отсортированного массива.
Наихудший случай:
Число сравнений в теле цикла равно (N-1)*N/2.
Число сравнений в заголовках циклов (N-1)*N/2.
Число сравнений перед операцией обмена N-1.
Суммарное число сравнений N2−1.
Число обменов N-1.
Наилучший случай:

Время сортировки 10000 коротких целых чисел на одном и том же программно-аппаратном комплексе сортировкой выбором составило ≈40сек., а ещё более улучшенной сортировкой пузырьком ≈30сек.

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

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


Сортировка пузырьком


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

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


Алгоритм


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

Псевдокод

Псевдокод улучшенного алгоритма (устойчивая реализация) с почти вдвое уменьшенным числом проходов.

На входе: массив A[N], состоящий из N элементов, с нумерацией от A[1] до A[N]

ЦИКЛ ДЛЯ J=1 ДО N-1 ШАГ 1 FOR J=1 TO N-1 STEP 1

ЦИКЛ ДЛЯ I=1 ДО N-J ШАГ 1 FOR I=1 TO N-J STEP 1

ЕСЛИ A[I]>A[I+1] ТО ОБМЕН A[I],A[I+1] IF A[I]>A[I+1] THEN SWAP A[I],A[I+1]

СЛЕДУЮЩЕЕ I NEXT I

СЛЕДУЮЩЕЕ J NEXT J

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

Если нет функции обмена (SWAP A[I],A[I+1]), то её можно заменить тремя операторами присваивания:

TEMP=A[I]

A[I]=A[I+1]

A[I+1]=TEMP

Cложность: O(n·n), не уменьшается.

Наихудший случай:



  • Число сравнений в теле цикла равно (N-1)*N/2.

  • Число сравнений в заголовках циклов равно (N-1)*N/2.

  • Суммарное число сравнений равно (N-1)*N.

  • Число присваиваний в заголовках циклов равно (N-1)*N/2.

  • Число обменов равно (N-1)*N/2, что в N/2 раз больше, чем в сортировке выбором.

Наилучший случай (на вход подаётся уже отсортированный массив):

  • Число сравнений в теле цикла равно (N-1)*N/2.

  • Число сравнений в заголовках циклов равно (N-1)*N/2.

  • Суммарное число сравнений равно (N-1)*N.

  • Число обменов равно 0.

Особенность данного алгоритма заключается в следующем: после первого завершения внутреннего цикла максимальный элемент массива всегда находится на N-ой позиции. При втором проходе, следующий по значению максимальный элемент находится на N-1 месте. И так далее. Таким образом, на каждом следующем проходе число обрабатываемых элементов уменьшается на 1 и нет необходимости «обходить» весь массив от начала до конца каждый раз.

Так как подмассив из одного элемента не нуждается в сортировке, то для сортировки требуется делать не более N-1 итераций внешнего цикла. Поэтому в некоторых реализациях внешний цикл всегда выполняется ровно N-1 и не отслеживается, были или не были обмены на каждой итерации.

Введение индикатора (флажка F) действительно произошедших во внутреннем цикле обменов уменьшает число лишних проходов в случаях с частично отсортированными массивами на входе. Перед каждым проходом по внутреннему циклу флажок сбрасывается в 0, а после действительно произошедшего обмена устанавливается в 1. Если после выхода из внутреннего цикла флажок равен 0, то обменов не было, то есть массив отсортирован и можно досрочно выйти из программы сортировки.

Псевдокод ещё более улучшенного алгоритма с проверкой действительно произошедших обменов во внутреннем цикле.

Нв входе: массив A[N], состоящий из N элементов, с нумерацией от A[1] до A[N]

ЦИКЛ ДЛЯ J=1 ДО N-1 ШАГ 1 FOR J=1 TO N-1 STEP 1

F=0 F=0

ЦИКЛ ДЛЯ I=1 ДО N-J ШАГ 1 FOR I=1 TO N-J STEP 1

ЕСЛИ A[I] > A[I+1] ТО ОБМЕН A[I],A[I+1]:F=1 IF A[I]>A[I+1] THEN SWAP A[I],A[I+1]:F=1

СЛЕДУЮЩЕЕ I NEXT I

ЕСЛИ F=0 ТО ВЫХОД ИЗ ЦИКЛА IF F=0 THEN EXIT FOR

СЛЕДУЮЩЕЕ J NEXT J

В случае досрочного выхода из сортировки в этом алгоритме делается один избыточный проход без обменов.

Наихудший случай (не улучшается):



  • Число сравнений в теле цикла равно (N-1)*N/2.

  • Число сравнений в заголовках циклов (N-1)*N/2.

  • Суммарное число сравнений равно (N-1)*N.

  • Число присваиваний в заголовках циклов равно (N-1)*N/2.

  • Число обменов равно (N-1)*N/2.

Наилучший случай (улучшается):

  • Число сравнений в теле цикла равно (N-1).

  • Число сравнений в заголовках циклов (N-1).

  • Суммарное число сравнений равно 2*(N-1).

  • Число обменов равно 0.

Время сортировки 10000 коротких целых чисел на одном и том же программно-аппаратном комплексе (операция сравнения ≈3.4мкс, обмена ≈2.3мкс) сортировкой выбором составило ≈40сек., ещё более улучшенной сортировкой пузырьком ≈30сек, а быстрой сортировкой ≈0,027сек.

O(n·n) больше, чем O(n·log(n)) у сортировки слиянием, но при малых n разница не очень большая, а программный код очень прост, поэтому вполне допустимо применение сортировки пузырьком для множества задач с массивами малой размерности на простаивающих и малозагруженных машинах.

Алгоритм можно немного улучшить, сделав следующее:


  • Внутренний цикл можно модифицировать так, чтобы он поочерёдно просматривал массив то с начала, то с конца. Модифицированный таким образом алгоритм называетсясортировкой перемешиванием или шейкерной сортировкой. Сложность при этом O(n·n) не уменьшается.

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

Псевдокод объединённого алгоритма сортировки пузырьком и сортировки выбором (устойчивая реализация):

FOR J=1 TO N-1 STEP 1

F=0


MIN=J

FOR I=J TO N-J STEP 1

IF Y[I]>Y[I+1] THEN SWAP Y[I],Y[I+1]:F=1

IF Y[I]

NEXT I

IF F=0 THEN EXIT FOR



IF MIN<>J THEN SWAP Y[J],Y[MIN]

NEXT J


[править]Пример работы алгоритма

Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

Первый проход:

(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.

(1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как 5 > 4

(1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как 5 > 2

(1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах (8 > 5), алгоритм не меняет их местами.

Второй проход:

(1 4 2 5 8) (1 4 2 5 8)

(1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как 4 > 2

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

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

Третий проход:

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

Теперь массив отсортирован и алгоритм может быть завершён.


Сортировка перемешиванием


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

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

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

Наименьшее число сравнений в алгоритме Шейкер-сортировки C=N-1. Это соответствует единственному проходу по упорядоченному массиву (лучший случай)

Код программы на языке программирования С++

#include

#include

#include

#pragma hdrstop

#pragma argsused

// Шейкер-сортировка

int main(int argc, TCHAR* argv[])

{

const int Count = 10;



int TestArr[Count] = {3,1,5,8,1,0,6,4,6,7};

ShakerSort(TestArr,1,Count);

ArrayOutput(TestArr,0,Count);

return 0;

}

//Поменять местами i-й и i-1-й элементы массива Arr



void Swap(int Arr[], int i)

{

int temp; //буфер



temp = Arr[i];

Arr[i] = Arr[i-1];

Arr[i-1] = temp;

}

void ShakerSort(int Arr[], int Start, int N)



{

int Left,Right; //границы сортировки

int Last; //место последней перестановки

Left=Start;

Right = N-1;

Last = N-1;

do

{

//Сдвигаем к концу массива "легкие элементы"



for (int i =Right; i >= Left; i--)

{

if (Arr[i-1]>Arr[i])



{

Swap(Arr, i);

Last = i; //Запомнить место последней перестановки

}

}



Left = Last + 1;

//Сдвигаем к началу массива "тяжелые элементы"

for (int i =Left; i <= Right; i++)

{

if (Arr[i-1]>Arr[i])



{

Swap(Arr, i);

Last = i; //Запомнить место последней перестановки

}

}



Right = Last - 1;

}

while (Left<=Right);



}

//Вывод элементов массива на консоль

void ArrayOutput(int* Arr, int Start, int N)

{

for (int i = 0; i < N; i++)



{

cout << Arr[i] << '\n';

}

getch();


}

Трассировка программы



3 1 5 8 1 0 4 6 6 7

3 1 5 8 0 1 4 6 6 7

3 1 5 0 8 1 4 6 6 7

3 1 0 5 8 1 4 6 6 7

3 0 1 5 8 1 4 6 6 7

0 3 1 5 8 1 4 6 6 7 Left=1

0 1 3 5 8 1 4 6 6 7

0 1 3 5 1 8 4 6 6 7

0 1 3 5 1 4 8 6 6 7

0 1 3 5 1 4 6 8 6 7

0 1 3 5 1 4 6 6 8 7

0 1 3 5 1 4 6 6 7 8 Right=8

0 1 3 1 5 4 6 6 7 8

0 1 1 3 5 4 6 6 7 8 Left=3

0 1 1 3 4 5 6 6 7 8


Алгоритмы неустойчивой сортировки


  • Сортировка выбором (Selection sort) — Сложность алгоритма: O(n2); поиск наименьшего или наибольшего элемента и помещение его в начало или конец упорядоченного списка

  • Сортировка Шелла (Shell sort) — Сложность алгоритма: O(n log2 n); попытка улучшить сортировку вставками

  • Сортировка расчёской (Comb sort) — Сложность алгоритма: O(n log n)

  • Пирамидальная сортировка (Сортировка кучи, Heapsort) — Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка

  • Плавная сортировка (Smoothsort) — Сложность алгоритма: O(n log n)

  • Быстрая сортировка (Quicksort), в варианте с минимальными затратами памяти — Сложность алгоритма: O(n log n) — среднее время, O(n2) — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине. При использовании O(n) дополнительной памяти, можно сделать сортировку устойчивой.

  • Introsort — Сложность алгоритма: O(n log n), сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает log(n).

  • Patience sorting — Сложность алгоритма: O(n log n) — наихудший случай, требует дополнительно O(n) памяти, также находит самую длинную увеличивающуюся подпоследовательность

  • Stooge sort — рекурсивный алгоритм сортировки с временной сложностью o(n^{\log_{1{,}5}{3}}) \approx o(n^{2.71}).

  • Поразрядная сортировка — Сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти.

  • Цифровая сортировка — то же, что и Поразрядная сортировка.


Сортировка Шелла


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

При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии d (о выборе значения d см. ниже). После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d=1 (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:


  • отсутствие потребности в памяти под стек;

  • отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

Пример

shellsort-ru.svg

Пусть дан список 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 позиции элементов.

Процесс завершается обычной сортировкой вставками получившегося списка.

Выбор длины промежутков



Среднее время работы алгоритма зависит от длин промежутков — d, на которых будут находиться сортируемые элементы исходного массива ёмкостью n на каждом шаге алгоритма. Существует несколько подходов к выбору этих значений:

  • первоначально используемая Шеллом последовательность длин промежутков: ~d_1 = n/2, d_i = d_{i-1} / 2, d_k = 1 в худшем случае, сложность алгоритма составит o( n^2 );

  • предложенная Хиббардом последовательность: все значения ~2^i-1 \le n, i \in \mathbb n; такая последовательность шагов приводит к алгоритму сложностью o(n^{3/2});

  • предложенная Седжвиком последовательность: ~d_i = 9\cdot2^i - 9\cdot2^{i/2} + 1, если i четное и ~d_i = 8\cdot2^i - 6\cdot2^{(i+1)/2} + 1, если i нечетное. При использовании таких приращений средняя сложность алгоритма составляет: o(n^{7/6}), а в худшем случае порядка o(n^{4/3}). При использовании формулы Седжвика следует остановиться на значении inc[s-1], если 3*inc[s] > size.[1];

  • предложенная Праттом последовательность: все значения ~2^i\cdot3^j \le n/2, i, j \in \mathbb n; в таком случае сложность алгоритма составляет o(n (log n)^2);

  • эмпирическая последовательность Марцина Циура (последовательность A102549 в OEIS): ~d \in \left\{1, 4, 10, 23, 57, 132, 301, 701, 1750\right\}; является одной из лучших для сортировки массива ёмкостью приблизительно до 4000 элементов.[2];

  • эмпирическая последовательность, основанная на числах Фибоначчи: ~d \in \left\{f_n\right\};

  • все значения ~(3^j-1)/2 \le n/2 j \in \mathbb n; такая последовательность шагов приводит к алгоритму сложностью o(n^{3/2}).


Сортировка расчёской


Сортировка расчёской (англ. comb sort) — это довольно упрощённый алгоритм сортировки, изначально спроектированный Влодзимежом Добосиевичем в 1980 г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine в апреле 1991 г[1]. Сортировка расчёской улучшает сортировку пузырьком, и конкурирует с алгоритмами, подобными быстрой сортировке. Основная идея — устранить черепах, или маленькие значения в конце списка, которые крайне замедляют сортировку пузырьком (кролики, большие значения в начале списка, не представляют проблемы для сортировки пузырьком).

В сортировке пузырьком, когда сравниваются два элемента, промежуток (расстояние друг от друга) равен 1. Основная идея сортировки расчёской в том, что этот промежуток может быть гораздо больше, чем единица (сортировка Шелла также основана на этой идее, но она является модификацией сортировки вставками, а не сортировки пузырьком).


Реализация на C++


void sort( data *array, dword size )

{

if (!array || !size)



return;

dword jump = size;

bool swapped = true;

while (jump > 1 || swapped)

{

if (jump > 1)



jump = (dword)(jump / 1.25);

swapped = false;

for (dword i = 0; i + jump < size; i++)

if (array[i] > array[i + jump])

swap(array, i, i + jump), swapped = true;

}

}












Быстрая сортировка


Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известныйалгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром в МГУ в 1960 году. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.

Краткое описание алгоритма



  • выбрать элемент, называемый опорным.

  • сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.

  • повторить рекурсивно для «меньших» и «больших».

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

[править]Алгоритм

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:


  1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.

  2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:

    1. Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.

    2. Вычисляется индекс опорного элемента m.

    3. Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.

    4. Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.

    5. Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.

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

  3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

  4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

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

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



//алгоритм на языке java

public static void qSort(int[] A, int low, int high) {

int i = low;

int j = high;

int x = A[(low+high)/2];

do {

while(A[i] < x) ++i;

while(A[j] > x) --j;

if(i <= j){

int temp = A[i];

A[i] = A[j];

A[j] = temp;

i++; j--;

}

} while(i < j);


if(low < j) qSort(A, low, j);

if(i < high) qSort(A, i, high);

}





//алгоритм на языке pascal

//при первом вызове 2-ой аргумент должен быть равен 1

//3-ий аргумент должен быть равен числу элементов массива

procedure qSort(var ar:array of real; low,high:integer);

var i,j:integer;

m,wsp:real;



begin

i:=low;


j:=high;

m:=ar[(i+j) div 2];



repeat

while(ar[i]do i:=i+1;

while(ar[j]>m) do j:=j-1;

if(i<=j) then begin

wsp:=ar[i];

ar[i]:=ar[j];

ar[j]:=wsp;

i:=i+1;

j:=j-1;


end;

until (i > j);

if(lowthen qSort(ar,low,j);

if(ithen qSort(ar,i,high);

end;



//алгоритм на языке Visual Basic

//при первом вызове 2-ой аргумент должен быть равен 1

//3-ий аргумент должен быть равен числу элементов массива

Sub qSort(ByVal ar() As double,ByVal low As Integer, ByVal high As Integer)

Dim i, j As Integer

Dim m, wsp As double

i = low

j = high


m = ar((i + j) \ 2)

Do Until i > j

Do While ar(i) < m

i += 1


Loop
Do While ar(j) > m

j -= 1


Loop

If (i <= j) Then

wsp = ar(i)

ar(i) = ar(j)

ar(j) = wsp

i += 1

j -= 1


End If

Loop


If (low < j) Then qSort(ar,low, j)

If (i < high) Then qSort(ar,i, high)

End Sub

Оценка эффективности

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате эффективный улучшенный метод.



  • Лучший случай. Для этого алгоритма самый лучший случай — если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения CN = 2CN/2+N, что в явном выражении дает примерно N lg N сравнений. Это дало бы наименьшее время сортировки.

  • Среднее. Даёт в среднем O(n log n) обменов при упорядочении n элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.
    На практике (в случае, когда обмены являются более затратной операцией, чем сравнения) быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n lg n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. 2CN/2 покрывает расходы по сортировке двух полученных подмассивов; N — это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно CN = N lg N.

  • Худший случай. Худшим случаем, очевидно, будет такой, при котором на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.
    Худший случай даёт O(n²) обменов. Но количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.

Улучшения

  • При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки — O(n lg n).

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

  • Во избежание достижения опасной глубины рекурсии в худшем случае (или при приближении к нему) возможна модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит log2n, а в худшем случае вырожденного разделения она вообще будет не более 2 — вся обработка пройдёт в цикле первого уровня рекурсии.

  • Разбивать массив не на две, а на три части (см. Dual Pivot Quicksort).

Достоинства и недостатки

Достоинства:



  • Один из самых быстродействующих (на практике) из алгоритмов внутренней сортировки общего назначения.

  • Прост в реализации.

  • Требует лишь o(\lg n) дополнительной памяти для своей работы. (Не улучшенный рекурсивный алгоритм в худшем случае o(n) памяти)

  • Хорошо сочетается с механизмами кэширования и виртуальной памяти.

  • Существует эффективная модификация (алгоритм Седжвика) для сортировки строк — сначала сравнение с опорным элементом только по нулевому символу строки, далее применение аналогичной сортировки для «большего» и «меньшего» массивов тоже по нулевому символу, и для «равного» массива по уже первому символу.

  • Работает на связанных списках и других структурах с последовательным доступом.

Недостатки:

  • Сильно деградирует по скорости (до \theta(n^2)) при неудачных выборах опорных элементов, что может случиться при неудачных входных данных. Этого можно избежать, используя такие модификации алгоритма, как Introsort, или вероятностно, выбирая опорный элемент случайно, а не фиксированным образом.

  • Наивная реализация алгоритма может привести к ошибке переполнения стека, так как ей может потребоваться сделать o(n) вложенных рекурсивных вызовов. В улучшенных реализациях, в которых рекурсивный вызов происходит только для сортировки меньшей из двух частей массива, глубина рекурсии гарантированно не превысит o(\lg n).

  • Неустойчив — если требуется устойчивость, приходится расширять ключ.

Вывод.

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

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

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

- сравнение, определяющее упорядоченность пары элементов;

-перестановку, меняющую местами пару элементов;



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

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


Смотрите также:
Антоненко Василь Николаевич Курс: I группа 426 Тема: Сортировка данных. Обзор. Анализ. Реализация. Перечень вопросов, подлежащих разработке: 1 аналитический обзор
409.16kb.
1 стр.
Научно-аналитический обзор деятельности правоохранительных организаций великобритании
196.5kb.
1 стр.
Выпускная квалификационная работа на соискание квалификации инженер
22.98kb.
1 стр.
Аналитический обзор литературы Аллергенная флора и заболеваемость поллинозом в различных странах мира
166.88kb.
1 стр.
Аналитический обзор) Санкт-Петербург Март 2004 г. Транспортная система Северо-Западного федерального округа(сзфо).
141.48kb.
1 стр.
Аналитический обзор Новосибирск, 2001 ббк
2396.59kb.
20 стр.
Урока Тема параграфа Тема урока Грамматический материал Лексические единицы
135.24kb.
1 стр.
Краткий обзор gsm-смартфона Nokia 6681
145.82kb.
1 стр.
Краткий обзор результатов Двадцать восьмой Сессии вспомогательных органов ркик ООН
130.97kb.
1 стр.
Программа дисциплины «Энергетика в мировой политике»
118.87kb.
1 стр.
1. обзор 2 положение ортодоксии 7
299.58kb.
1 стр.
Аналитический обзор по курсу «Современные проблемы информатики и вычислительной техники»
376.03kb.
1 стр.