В.Д. Валединский - Краткий конспект курса лекций «Работа на ЭВМ и программирование» (1119512), страница 8
Текст из файла (страница 8)
Несложнопроверяется, что при этом действительно осуществляется биекция. Отсюда понятно ипонятие заполнения пирамиды – оно соответствует заполнению массива.Пример пирамиды и соответствующего массива:Лекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год2652345324Перейдем теперь непосредственно к алгоритму сортировки.
Он состоит из двух частей –сборке и разборке пирамиды.Вначале происходит т.н. сборка пирамиды. Исходный массив представляют в видепирамиды и упорядочивают её. Производится это следующим образом: берем по очередиэлементы массива, начиная с последнего и заставляем их «тонуть» в пирамиде следующимобразом: спускаем элемент вниз по дереву, пока это возможно, обменивая его смаксимальным из текущих потомков. Легко видеть, что при этом в той ветке, по которойспустился элемент, установится упорядоченность вида: левый и правый потомки не большеродителя.
Поскольку мы пройдемся по всем элементам массива, то упорядоченностьустановится во всей пирамиде. Трудоемкость данной операции - O n log 2 n (для nэлементов выполняем операцию спуска трудоемкости O log 2 n ).Затем происходит т.н. разборка пирамиды. Очевидно, что в вершине пирамиды оказалсямаксимальный элемент (он не меньше своих потомков, эти потомки – не меньше своихпотомков и т.д., отсюда вершина не меньше всех элементов пирамиды). Переставим теперьэтот элемент в конец массива, а на его место – поставим элемент, ранее бывший последним.Теперь выкидываем этот последний элемент из рассмотрения – он уже занял свое законноеместо.
В оставшейся пирамиде может нарушиться упорядоченность – для ее восстановлениядостаточно «спустить» новый корень пирамиды – переставлять местами этот элемент смаксимальным из потомков до тех пор, пока этот потомок больше нашего элемента. Этозаймет время порядка O log 2 n , при этом упорядоченность пирамиды будет восстановленаи мы снова можем применить к ней алгоритм разборки. На каждом шагу (а их будет n) насвое место встает один элемент, значит за O n log 2 n мы разберем пирамиду полностью иполучим отсортированный массив.Общее время на сортировку таким образом, не превосходит O n log 2 n , дополнительнаяпамять не используется совсем (точнее, используется под служебные переменные, O(1)).Тем самым heapsort – эффективная сортировка.
Однако обойти quicksort ей удается нечасто,в среднем она работает несколько медленнее.Как было замечено выше, ни одна сортировка, использующая попарные сравненияэлементов, не может работать быстрее. Однако можно предложить сортировку, неиспользующую попарные сравнения. Рассмотрим например, такую сортировку,сортирующую массив элементов, по хэш-значениям. Пусть хэш-функция отображаетсортируемые элементы в целые числа 0…n-1.Сортировка подсчетом: Пусть требуется отсортировать массив A из N элементов похэш-значениям.
Возьмем дополнительный массив A из n элементов и еще дополнительныймассив B, равный по длине исходному – в него мы будем записывать результат. За линейноевремя проходим по массиву и считаем количество хэш-значениям 0,…, n-1, используя этотмассив в качестве счетчика (A[i] – число встреч элемента с значением хэш-функции i вмассиве (в дальнейшем в описании алгоритма будем просто говорить – элемента «i»). На этоЛекции по ЭВМ. Конспект. Лектор В.Д.
Валединский.Группа 208, 3 семестр, 2002 год27уйдет O(N) операций. Очевидно, что в отсортированном массиве будет A[0] «нолей», A[1]«единиц», … A[n-1] «n-1». Соответственно, «ноли» будут начинаться с 0, «единицы» – с A[0], «двойки» – с A[0]+A[1], «тройки» – с A[0]+A[1]+A[2], … «n-1» – с A[0]+A[1]+…+A[n2]. Теперь проводим несложную вещь – пересчитываем A так, чтобы вместо A[0], A[1], A[2], … A[n-1] в массиве A будет A[0], A[0]+A[1], ….
Пересчет этот производится очевиднымобразом – проходим по массиву, с i=1 до n-1, вычисляя A[i] = A[i] + A[i-1] опять-таки за O(N) операций. Теперь идем с конца по массиву A. Если встретился элемент «j», тозаписываем этот элемент в B[A[j]-1] и уменьшаем A[j] на единицу. Это – снова O(N)операций.
Принцип понятен – A[j]-1 на каждом шаге – это последнее свободное место, кудаеще можно запихнуть элемент «j», поскольку A[j] изначально – начало элементов «j+1»,значит A[j]-1 – конец элементов «j», ну а по мере добавления элементов в конец, очевидно,нам нужно смещать этот указатель на предыдущую позицию. Пример работы сортировки:хэш012132011элементabcdefghkПодсчет дает намi0123A[i]2421Соответственно в отсортированном массиве у нас будут значения хэша: 2 ноля, 4единицы, 2 двойки, 1 тройка:хэш001111223Позиции элементов, соответственноA[i]268(9)Теперь будем проходить с конца:I012345678элементabcdefghkхэш012132011A[i]2689B[i]элементхэшA[i]B[i]a02элементхэшA[i]B[i]a02элементхэшA[i]B[i]a01элементхэшA[i]B[i]a01элементхэшA[i]B[i]a01b15c28d19e3f2g0h1kb14c28b14gc28b14gc27b14gc27d19d19d19e3f2hke3f2hkg0e3hkfhkfd18eЛекции по ЭВМ. Конспект.
Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год28элементхэшA[i]B[i]a01элементхэшA[i]B[i]a01элементхэшA[i]B[i]a01b13gb13g2gc2766b8dhk8dhk8dhkfecfecfeэлементхэшA[i]0268B[i]agbdhkcfeХэши в полученной последовательности B получились 0,0,1,1,1,1,2,2,3, что итребовалосьИтак, полученная сортировка работает за линейное время, причем константа перед n неочень велика (пропорциональна n).
Если n мало, а N велико (то есть у наспоследовательность из очень большого числа повторяющихся элементов), то такаясортировка работает быстрее любой другой. Но главное ее достоинство не в этом, а в том,что на ее основе легко строить более сложные сортировки, работающие за линейное время.Для дальнейшего понимания нам понадобится понятие регулярной сортировки:Сортировка называется регулярной, если она сохраняет порядок одинаковых элементовв отсортированном массиве. Например, сортировки поиском максимума / минимума,сортировку вставкой, сортировку пузырьком несложно реализовать так, чтобы они былирегулярными, а вот quicksort и hypsort – не являются регулярными сортировками. Так вот, вописанной реализации сортировка подсчетом – очевидно регулярная, а это для сортировкипо хэш-значениям довольно важно.
В частности, можно реализовать улучшеннуюсортировку подсчетом – арифметическую сортировку. В ней сортируются элементы с pбитными хэш-значениями. Сортировку будем проводить следующим образом: на k-м шагеалгоритма применим сортировку подсчетом с хэш-функцией, равной k-му биту хэшзначения элемента. Здесь хэш-множество состоит всего из 2х элементов (0 и 1), поэтомусортировка проходит очень быстро. А в силу регулярности сортировки после p проходовалгоритма (начиная с k=p и заканчивая с k=1) получится массив, отсортированный в первуюочередь по первому биту, при равенстве первых битов – по второму, при равенстве и вторых– по третьему и так далее.
Легко видеть, что такой массив отсортирован по хэш-значениям.Соответственно, получился алгоритм, работающий за время Cpn, где p – число битов в хэшзначениях множества, n – число элементов множества.Заметим, что такой алгоритм, будучи применен на множестве из разных элементов, даеттакую же оценку, как и эффективный алгоритм сортировки – то есть O n log 2 n . Но нанебольших множествах элементов такой алгоритм работает заметно медленнее quicksort иheapsort. Эффективность его проявляется только на очень больших массивах с большимчислом повторяющихся элементов.Лекции по ЭВМ. Конспект.
Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год292.2. Сжатие данныхРассмотрим последовательность AAAAAAAA….AAAA (n символов A). На ее запись впамяти тратится n байт, хотя информации такая последовательность несет всего log 2 n 1байт – что за байт и сколько раз он повторяется – налицо большая избыточность храненияинформации. При «идеальном» кодировании каждый следующий бит последовательностиравновероятен – только тогда он несет в себе 1 бит реальной информации (по определению1 бит информации (а это не то же самое, что 1 машинный бит) – количество информации,уменьшающее неопределенность ровно в 2 раза). Во всех остальных случаяхпоследовательность избыточна.
Для устранения избыточности применяются алгоритмысжатия данных.Избавиться от избыточности описанного выше рода («групповой») помогает алгоритмгруппового кодирования (RLE, Run-Length Encoding). Рассмотрим вначале наиболеепростой вариант: пусть мы кодируем некоторую последовательность. Выбираем в этойпоследовательности наименее часто встречающийся элемент (в идеале – отсутствующий вэтой последовательности) и помечаем его как спецсимвол (обозначим его, например, $).Теперь если у нас в последовательности встретятся четыре и более подряд стоящиеодинаковые элемента, скажем, B, то мы заменим эту последовательность на $(числоэлементов)B.
Это дает нам выигрыш в n-3 байт для последовательности длины n. Проблемавозникнет, например, тогда, когда в нашей последовательности возникнет элемент $. Вданном случае, например, можно записать после $ число 0 – программа это должна будетвоспринять именно как один символ $.Например, такой алгоритм закодирует AAAAABBB$$F$CCCCCDDDD в $(5)ABBB$(0)$(0)F$(0)$(5)C$(4)D – из 21 байта в 19. В данном примере сжатие получилось небольшоепотому что мы рассматривали небольшой алфавит.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
