|
||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() ![]() ![]() ![]() ![]() ![]() ![]() последовательностях ![]() Компиляторы и интерпретаторы ![]() Хранение информации ![]() ![]() ![]() ![]() ![]() Софт: просмотр PS и PDF файлов ![]() Написать веб-мастеру Почитать историю сайта |
Алгоритмы сортировки.Данный класс алгоритмов делится на два основных подкласса: Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно сортируются на том же месте, без дополнительных затрат. Внешняя сортировка оперирует с запоминающими устройствами большого объема, но с доступом не произвольным, а последовательным (сортировка файлов), т.е в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики . Это приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство. Кроме того, существует топологическая сортировка, оперерующая с ориентированными графами без циклов. Она приводит их представление в ЭВМ к виду, при котором все ребра направлены в одну сторону. С циклами такой фокус, естественно, не пройдет. Обычная сортировка сравнениями.
Распределяющая и ее вариации.Этот тип сортировок зачастую много быстрее обычных, но применим лишь к ключам, принимающим известное число значений.Прекрасный пример - строки: там каждая буква - одна из 33-х. Или целые числа от нуля до 65535. В современных ЭВМ все ключи, даже дробные представлены в памяти через конкретные целые числа, поэтому, в принципе, дискретную сортировку можно использовать везде, однако когда возможных значений ключей много больше, чем самих ключей, она невыгодна. Пусть далее имеем k байт в каждом ключе ( хотя, за единицу измерения вполне можно принять и что-либо другое. В том числе и 2 байта ; - ) ). Разрядность данных - m
Информацию о решении родственных сортировке задач можно также найти в разделе: Олимпиадные задачи: сортировки и последовательности. Архив статей.
Разные алгоритмы поиска и сортировки, описанные на серьезном теоретическом уровне. ![]() |