Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
3. Методы упорядочивания данных со статическими связями. Алгоритмы сортировок
3.1 Характеристики сортировок
Время сортировки.
Дополнительная память, необходимая для сортировки.
Устойчивость. Устойчивой сортировкой является та, которая не меняет взаимного расположения одинаковых элементов.
Естественность поведения. Под этим понятием понимается эффективность работы алгоритма в случае отсортированных или частично отсортированных данных. Естественный - учитывает этот факт и работает быстрее. Неестественный метод этот факт не учитывает, либо бывает, что работает даже хуже.
3.2 Оценка времени исполнения алгоритмов. Символ O()
Для оценки производительности алгоритма можно использовать различные подходы. Самый простой из них - это запустить алгоритм и сравнить время его выполнения на разных задачах. Более научный подход заключается в оценке с использованием символа О(). Этот символ зависит от числа n, где n - это число обработанных чисел. Такую оценку называют асимптотикой, так как она обозначает асимптотическое поведение алгоритма при n→∞. Когда используют данную оценку, имеют в виду не точное время исполнения, а только его предел сверху с точностью до постоянного множителя.
Например, когда алгоритму требуется времени О(n^2), имеется в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов.
Таблица 1 иллюстрирует скорость роста для различных функций О:
Таблица 1. Скорость роста для различных функций O
|
N |
log (n) |
n * log (n) |
n^2 |
|
16 |
4 |
64 |
256 |
|
256 |
8 |
2`048 |
65`536 |
|
4`096 |
12 |
49`152 |
16`777`216 |
|
65`536 |
16 |
1`048`565 |
4`294`967`296 |
|
1`048`476 |
20 |
20`969`520 |
1`099`301`922`576 |
|
16`775`616 |
24 |
402`614`784 |
281`421`292`179`456 |
Если считать, что числа в таблице соответствуют микросекундам, то для сортировки 1 миллиона элементов алгоритму, обладающему эффективностью O(log(n)) потребуется 20 микросекунд, а алгоритму с эффективностью O(n^2), - более 12 дней.
Если оба алгоритма имеют оценки эффективности O(n*log(n)), это не значит, что они одинаково эффективны, так как оценка O не учитывает константу, то есть первый алгоритм может быть эффективнее в 1000 раз, чем второй.
За функцию берется количество операций, возрастающее быстрее всего. То есть если в программе одна функция выполняется O(n) раз - например, умножение, а сложение - O(n^2) раз, то общая сложность - O(n^2), так как n^2 возрастает быстрее. Практический смысл этого такой: при увеличении n более быстрые (в определенное, константное число раз) сложения станут выполняться настолько часто, что будут влиять на производительность много сильнее, нежели медленные, но редкие умножения
Кроме символа O() используются также оценки Omega() - нижняя оценка, Theta() - комбинация O() и Omega(): точная оценка асимптотики.
Интуитивный смысл оценок:
f = O(g), f растет не быстрее, чем g, при n→∞.
f = Omega(g), f растет не медленнее ,чем g при n→∞.
f = Theta(g), а растет примерно также, как g при n→∞.
3.3 Пузырьковая сортировка
Общее быстродействие O(n^2), поэтому на практике практически не используется.
Дополнительные затраты на память. Сортировка происходит на месте.
Устойчивая.
Поведение неестественное.
Идея метода:
Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами. После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом, второй по величине элемент поднимается на правильную позицию. Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент.
3.4 Сортировка выбором.
Общее быстродействие O(n^2).
Сортировка происходит на месте.
Неустойчивая.
Поведение неестественное.
Идея метода:
Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке.
A[1..N] - сортируемый массив из n элементов.
for ( i=1; i<N; i++) Hайти наименьший из элементов i..N и поменять его местами с i-м.
3.5 Сортировка вставками.
Общее быстродействие O(n^2). Но ввиду простоты реализации, является самой быстрой для малых массивов и списков (менее 20 элементов). В виду своих особенностей, алгоритм хорош для частично отсортированных данных.
Сортировка происходит на месте.
Устойчивая.
Поведение естественное.
Идея метода:
Сортировка простыми вставками в чем-то похожа на "пузырек" или "выбор". Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале "вырастает" отсортированная последовательность. Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же хотя последовательность a[0]...a[i] упорядочена, но по ходу алгоритма в нее могут вставляться новые элементы.
3.6 Быстрая сортировка
Общее быстродействие O(n*log(n)). Наиболее быстрая сортировка для неупорядоченных массивов с 50 и более элементами.
Требует дополнительной памяти.
Неустойчивая.
Поведение неестественное.
Метод основан на подходе "Разделяй и властвуй".
Быструю сортировку нетрудно реализовать, она хорошо работает на различных видах входных данных и во многих случаях требует меньше затрат ресурсов по сравнению с другими методами сортировки. На выполнение сортировки N элементов в среднем затрачивается время, пропорциональное N log N и для него характерны исключительно короткие внутренние циклы.
Его недостатком является то, что он неустойчив, для его выполнения в наихудшем случае требуется N2 операций.
Наиболее быстрой является сортировка для неупорядоченных массивов с 50 и более элементами.
Идея метода:
В массиве выбирается опорный элемент a[i], затем сортируемый массив делится на две части, которые затем сортируются независимо друг от друга. Точное положение точки деления зависит от исходного порядка элементов в исходном массиве. Основная идея метода заключается в процессе разбиения массива, который переупорядочивает массив таким образом, что выполняются следующие условия:
Элемент a[i] для некоторого i занимает свою окончательную позицию в массиве.
Ни один из элементов a[i],..., a[i-l] не превышает a[i].
Ни один из элементов a[i+l],..., а[r] не является меньшим a[i].
Разбиение осуществляется с использованием следующей стратегии:
Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент а[r] — он сразу займет свою окончательную позицию. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент. Затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами. Процесс продолжается до тех пор, пока слева от левого указателя не останется ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента.
Несмотря на все ее ценные качества, базовая программа быстрой сортировки обладает определенным недостатком, который заключается в том, что она исключительно неэффективна на некоторых простых массивах, которые могут встретиться на практике. Например, если она применяется для сортировки массива размером N, который уже отсортирован, то все имеющиеся разделения вырождаются, и программа вызовет сама себя N раз, перемещая за каждый вызов всего лишь один элемент.
3.7 Сортировка методом Шелла
Общее быстродействие O(n^2).
Сортировка происходит на месте.
Неустойчивая.
Поведение неестественное.
Сортировка вставками не относится к категории быстродействующих, поскольку единственный вид операции обмена, который она использует, выполняется над двумя соседними элементами, в связи с чем элемент может передвигаться вдоль массива лишь на одно место за один раз. Например, если наибольший элемент оказывается в конце массива, потребуется сделать N шагов, чтобы поместить его в надлежащее место. Сортировка методом Шелла представляет собой простейшее расширение метода вставок, быстродействие которого выше за счет обеспечения возможности обмена местами элементов, которые находятся далеко один от другого (элементы перемещаются большими скачками).
Идея метода:
В исходном массиве выделяю группы элементов. Каждая группа сортируется методом вставки. По ходу работы алгоритма размеры таких групп увеличиваются, пока все элементы массива не войдут в одну группу. Группой массива называется последовательность элементов, номера которых образуют арифметическую прогрессию с разностью h, которая называется шагом группы.
Основной вопрос - это выбор последовательности шагов. Существует достаточное количество исследований этого вопроса, и предложено большое количество методик выбора этой последовательности для разного числа элементов. Самый простой способ: h = n/2-1.
Один из способов реализации сортировки методом Шелла заключается в том, что для каждой выделенной группы элементов независимо используется сортировка вставками на каждом из h подмассивов. Несмотря на очевидную простоту этого процесса, возможен еще более простой подход именно благодаря тому, что подмассивы независимы. В процессе h-сортировки массива мы просто вставляем элемент среди предшествующих ему элементов в соответствующем h-подмассиве, перемещая большие по значению элементы вправо. Эта задача решается путем использования программы сортировки вставками, при которой каждый шаг перемещения по массиву в сторону увеличения или уменьшения равен h, но не равен 1. С учетом данного обстоятельства программная реализация сортировки методом Шелла сводится всего лишь к тому, что для каждого значения шага осуществляется проход по массиву, характерный для сортировки вставками.
3.8 Пирамидальная сортировка
Общее быстродействие O(n*log(n)). Быстрая сортировка.
Сортировка на месте.
Неустойчивая.
Поведение неестественное.
Назовем пирамидой бинарное дерево высотой k, в котором все узлы имеют максимальный уровень k или k-1, то есть дерево является сбалансированным. При этом уровень k-1 заполнен полностью, а уровень k заполнен слева направо.
Для пирамиды выполняется свойство: каждый элемент меньше либо равен родителю. Самым простым способом хранения пирамиды является массив. Соответствие между графическим представлением пирамиды и массивом осуществляется по правилам: в a[0] помещается корень дерева. Левый и правый сыновья элемента a[i]-го хранятся в ячейках, a[2*i+1] и a[2*i+2]. Таким образом, для массива, хранящего в себе пирамиду, выполняется свойство, что a[i]>=a[2*i+1] и a[i]>=a[2*i+2].
Такой способ хранения имеет следующие преимущества:
Для организации не используется дополнительная память.
Узлы хранятся от вершины и далее вниз уровень за уровнем. Узлы одного уровня хранятся в массиве слева направо.
Чтобы воспользоваться пирамидальной сортировкой, необходимо выполнить 2 действия:
по исходному массиву построить пирамиду,
произвести сортировку.
Построение пирамиды
Возьмем исходный массив.
44_55_12_42_94_18_06_67
Построение пирамиды начнется с элементов a[k] и a[n], где n - количество элементов в массиве, а k =n/2, так ка эта часть массива удовлетворяет свойству пирамиды (родитель больше или равен ребенку) по той причине, что эти элементы просто не имеют детей.
Далее будем расширять часть массива, обладающую свойством пирамиды. Для этого используется следующая процедура:
начинаем двигаться от элемента k-1 до 0,
смотрим на сыновей i-го элемента и выбираем наибольшего из них,
если выбранный элемент больше чем a[i], то меняем его с a[i] местами, после чего опять переходим к шагу 3, рассматривая новое положение a[i]-го в массиве.
Пример построения пирамиды приведен на рисунке 1. Закрашенные элементы показывают, что данный элемент удовлетворяет правилу пирамиды.
Рисунок 1. Построение пирамиды.
Сортировка
Как видно из свойств пирамиды, в корне всегда находится максимальный элемент. Отсюда следует алгоритм:
Берем максимальный элемент в корне и меняем его местами с последним неотсортированным элементом. После этого он находится на правильной позиции, и в дальнейшем алгоритме уже не участвует.
Берем элемент, находящийся в вершине и для него выполняем алгоритм по построению пирамиды.
Выполняем шаги 1 и 2, пока не останется неотсортированных элементов.
3.9 Сортировка слиянием
Общее быстродействие O= Theta(n*log(n)).
Использует дополнительную память, объем которой равен Theta(n).
Устойчивая.
Естественность зависит от реализации.
Под названием "сортировка слиянием" подразумевается широкий класс сортировок, основанных на принципе слияния. Так же, как и быстрая сортировка, этот метод основан на принципе "разделяй и властвуй", однако реализует его иначе. Вместо разделения по опорному элементу, массив просто делится пополам. В сортировке используется функция слияния двух упорядоченных массивов, которая создает единый упорядоченный массив.
Выборка и слияние — это вспомогательные операции в том смысле, что выборка разбивает файл на два независимых массива, в то время как слияние объединяет два независимых массива в один.
Сортировка слиянием (mergesort) является дополнением быстрой сортировки в том, что она состоит из двух рекурсивных вызовов с последующей процедурой слияния.
В процессе сортировки происходит деление массива до единственного элемента. Такой массив можно считать опорным. Значит, составление алгоритма сортировки заключается в написании одной единственной функции слияния.
Например, разбиваем исходный неупорядоченный массив на два массива: a[lb] ... a[split] и a[split+1] ... a[ub].
В результате сортировки мы получим: a[lb] ... a[ub].
3 7 8 2 | 4 6 1 5
3 7 | 8 2 | 4 6 | 1 5
3 | 7 | 8 | 2 | 4 | 6 | 1 | 5
3 7 | 2 8 | 4 6 | 1 5
2 3 7 8 | 1 4 5 6
1 2 3 4 5 6 7 8
В сортировке происходит деление до единственного элемента, такой массив можно считать упорядоченным, значит, написанный алгоритм сортировки заключается в написании одной единственно функции слияния.
Одним из способов слияния двух упорядоченных массивов является добавление вспомогательного буфера, равного общему количеству упорядоченных элементов.
Поразрядная сортировка (RadixSort)
Поразрядная сортировка существенно отличается от описанных ранее.
Во-первых, он совсем не использует сравнений сортируемых элементов.
Во-вторых ключ, по которому идет сортировка разбивается на части (разряды). Например, при сортировке слов, слова можно разделить на буквы, при сортировке чисел, их можно поделить на цифры.
Для сортировки необходимо задать два дополнительных параметра:
k – количество разрядов в самом длинном ключе
m – разрядность данных (количество возможных значений для каждого разряда ключа).
Например, при сортировке русских слов m=33 (количество букв русского алфавита), k – количество букв в самом длинном слове.
При сортировке десятичных чисел m=10 (10 цифр от 0 до 9), k – максимальное количество цифр в числах участвующих в сортировке, для диапазона от 0 до 5000 k=4.
Основная идея заключается в выделении m счетчиков, которые ведут подсчет сколько чисел из исходного массива имеют в соответствующем разряде одинаковое значение.
Сортировка двухпроходная.
На первом этапе подсчитываются количество чисел имеющих, одинаковые значения в разряде.
На втором этапе на основании информации полученной на первом этапе строится новый массив, отсортированный по разряду.
Аналогичные действия производятся над следующим разрядом. Всего потребуется k таких проходов.
Поразрядная сортировка (Десятичные числа) m=10 k=3
PAGE 1
Распределение памяти
Массив после 1 итерации
0 – 0
1 – 1
2 - 2
3 – 3
4 – 5
5 – 7
6 – 8
7 – 9
8 – 9
9 – 12
090
761
012
303
823
184
294
005
346
268
398
578
четчики мл. разрядов
Исходный массив
0 – 1
1 – 1
2 - 1
3 – 2
4 – 2
5 – 1
6 – 1
7 – 0
8 – 3
9 – 0
268
346
012
303
184
294
005
761
578
823
090
398
Распределение памяти
Массив после 2 итерации
0 – 0
1 – 2
2 - 3
3 – 4
4 – 4
5 – 5
6 – 5
7 – 7
8 – 8
9 – 9
303
005
012
823
346
761
268
578
184
090
398
294
Счетчики сред разрядов. разрядов
Массив после 1 итерации
0 – 2
1 – 1
2 - 1
3 – 0
4 – 1
5 – 0
6 – 2
7 – 1
8 – 1
9 – 3
090
761
012
303
823
184
294
005
346
268
398
578
005
012
090
184
268
294
303
346
398
578
823
761
Распределение памяти
Массив после 3 итерации
0 – 0
1 – 3
2 - 4
3 – 6
4 – 9
5 – 9
6 – 10
7 – 10
8 – 11
9 – 12
Счетчики старш . разр
Массив после 2 итерации
0 – 3
1 – 1
2 - 2
3 – 3
4 – 0
5 – 1
6 – 0
7 – 1
8 – 1
9 – 0
303
005
012
823
346
761
268
578
184
090
398
294