Файл: Алгоритмы сортировки данных, блочная сортировка.pdf

ВВЕДЕНИЕ

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

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

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

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

Задачи:

1. Изучение свойств алгоритмов.
2. Изучение способа оценки алгоритмов.
3. Сгруппировать алгоритмы по быстродействию.
4. Описать результаты работы.
5. Сделать вывод.

1. Свойства и оценка алгоритмов сортировки

Для сравнения и анализа алгоритмов сортировки существуют следующие свойства:

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

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

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

Время – основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O(n log(n)) и плохое поведение – это O(). Идеальное поведение для упорядочения – O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в сравнениях.;

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

1.1 Оптимальность O(n log(n))

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

Пусть по ходу работы алгоритмом производится k сравнений. Ответом на сравнение двух элементов a и b может быть один из двух вариантов a<b или a>b. Значит, всего возможно вариантов комбинаций ответов на k вопросов.

Количество перестановок из n элементов равно n!. Для того, чтобы можно было провести сюръекцию из множества ответов на сравнения на множество перестановок, количество сравнений должно быть не меньше, чем .

Прологарифмировав формулу Стирлинга, можно обнаружить, что .

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

2. Алгоритмы O()

Алгоритмы O() являются относительно медленными, зато простыми. Последнее качество позволяет им иногда превосходить сравнительно быстрые, но более сложные алгоритмы для очень малых массивов.

2.1 Сортировка вставкой

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

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

Листинг 1 – Псевдокод сортировки вставками

Insertionsort(Data: values[])

For i = 0 To <количество значений> - 1

// Перемещаем элемент i в соответствующую позицию

// в отсортированной части массива.

<Находим первый индекс j, при котором j < i

и values[j] > values[i].>

<Помещаем элемент в позицию j.>

Next i

End Insertionsort

При циклическом прохождении по элементам массива на основе индекса i наблюдается следующее разделение: элементы с индексом менее i признаются отсортированными, а с индексом более или равным i — неотсортированными. После того как код пересмотрит все индексы массива (от 0 до последнего), он перемещает элемент с индексом i в соответствующую позицию во второй части массива. Чтобы обнаружить эту позицию, перебираются уже отсортированные элементы и находится первый элемент, который больше, чем values[i]. Перемещение может занять какое-то время. Ведь если новый индекс элемента должен быть j, код должен сдвинуть все элементы между индексами j и i на одну позицию вправо, чтобы освободить место.

На рисунке 1 показаны основные шаги алгоритма. Верхний фрагмент представляет собой исходный не отсортированный массив. На среднем фрагменте первые четыре элемента (они обведены толстой линией) уже отсортированы, а алгоритм готовится добавить к ним следующий со значением 3. Код пересматривает отсортированные элементы, пока не определит, что число 3 нужно вставить перед числом 4. На нижнем фрагменте видно, что алгоритм передвинул значения 5, 6 и 7 вправо, чтобы освободить место для значения 3. Вставив его, он продолжит цикл For, чтобы упорядочить следующий элемент со значением 2.

Рисунок 1 – Основные шаги алгоритма сортировки вставками

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

Суть этого алгоритма сортировки состоит в том, чтобы найти в списке ввода наибольший элемент и добавить его в конец отсортированного списка. Как вариант, можно искать наименьший элемент и перемещать его в начало отсортированного списка. В следующем псевдокоде представлен алгоритм, работающий с массивами.

Листинг 2 – Псевдокод сортировки выбором

Selectionsort(Data: values[])

For i = 0 To <количество значений> - 1

// Находим элемент, принадлежащий позиции i.

<Находим наименьший элемент, у которого индекс j >= i.>

<Меняем местами values[i] и values[j].>

Next i

End Selectionsort

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

Основные шаги алгоритма представлены на рисунке 2. На верхнем фрагменте виден исходный не отсортированный массив. На среднем первые три элемента уже отсортированы (они обведены толстой линией), а алгоритм готовится поменять позицию следующего элемента. Он ищет не отсортированные элементы, чтобы выявить среди них тот, который имеет наименьшее значение, – в данном случае это 3. Найденное число перемещается в следующую не отсортированную позицию. На нижнем фрагменте показан массив после того, как новый элемент был добавлен в отсортированную часть. Цикл For приступает к следующему элементу со значением 5.

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

Если в массиве содержится N элементов, алгоритм изучает каждый из них. Для начала он должен пересмотреть N – i еще не отсортированных элементов, чтобы найти принадлежащий позиции i, а затем передвинуть сортируемый элемент на последнюю позицию за малое количестве шагов. Таким образом, для перемещения всех элементов потребуется (n – 1) + (n – 2) + ... + 2 + 1 = (+ n)/2 шагов. Это значит, что алгоритм обладает временем работы O(), как и алгоритм сортировки вставкой.

Рисунок 2 – Пример сортировки выбором

Сортировка выбором также является достаточно быстрой для относительно малых массивов (менее 10 000 элементов). Кроме того, она проста и если элементов совсем немного (от 5 до 10), работает эффективнее, чем более сложные алгоритмы

2.3 Пузырьковая сортировка

Пузырьковая сортировка предполагает следующее: если массив не отсортирован, любые два смежных элемента в нем находятся в неправильном положении. Из-за этого алгоритм должен проходить по массиву несколько раз, меняя местами все неправильные пары.

Листинг 3 – Псевдокод пузырьковой сортировки

Bubblesort(Data: values[])

// Повторяем, пока не отсортируем массив.

Boolean: not_sorted = True

While (not_sorted)

// Предполагаем, что неправильных пар нет.

not_sorted = False

// Ищем смежные элементы массива, стоящие в неправильном порядке.

For i = 0 To <количество значений> - 1

// Проверяем, стоят ли элементы i и i – 1

// в правильном порядке.

If (values[i] < values[i - 1]) Then

// Меняем их местами.

Data: temp = values[i]

values[i] = values[i - 1]

values[i - 1] = temp

// Массив еще не отсортирован.

not_sorted = True

End If

Next i

End While

End Bubblesort

В коде используется булевская переменная not_sorted, которая отслеживает перемещение элементов при прохождении через массив. Пока она истинна, цикл работает — ищет неправильные пары элементов и перестраивает их. Иллюстрацией этого алгоритма может служить рисунок 3. Первый массив выглядит по большей части отсортированным, но, пройдясь по нему, алгоритм выявит, что пара 6 – 3 находится в неправильном положении (число 6 должно следовать после 3). Код поменяет найденные элементы местами и получит второй массив, в котором в неправильном положении окажется пара 5 – 3. После ее исправления образуется третий массив, где неверна пара 4 – 3. Поменяв ее элементы местами, алгоритм сформирует четвертый массив, совершит еще один конечный проход и, не найдя пар, стоящих в неправильном положении, остановится.

Рисунок 3 – Пузырьковая сортировка

В пузырьковой сортировке неупорядоченный элемент 3 как бы медленно «всплывает» на правильную позицию, отсюда и специфическое название метода. Каждое прохождение через массив ставит на нужное место как минимум один элемент. В массиве, приведенном на рисунке 3, при первом прохождении на правильной позиции оказывается число 6, при втором — 5, при третьем — 3 и 4.

Если предположить, что в массиве содержится N элементов и хотя бы один из них занимает свое место в результате однократного пересмотра значений, то алгоритм может совершить не более N прохождений. (Все N понадобятся, когда массив изначально отсортирован в обратном порядке.) Каждое такое прохождение включает N шагов, отсюда общее время работы алгоритма — O(N2).

Как и две предыдущие сортировки, пузырьковая является довольно медленной, но может показать приемлемую производительность в малых списках (менее 1000 элементов). Она также быстрее, чем более сложные алгоритмы для очень малых списков (около 5 элементов).

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