Классификация задач сортировки и поиска

Пусть задано некое огромное количество частей а1 а2, а3, . . ., аn и требуется выстроить эти элементы по порядку в согласовании с данной функцией предпочтения (к примеру, по алфавиту). Очень нередко значения функции предпочтения очевидно хранятся в начальных элементах в виде специального главного поля целого либо строкового типа.

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

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

Все методы сортировки основаны на неоднократном повторении 2-ух базисных операций: сопоставление ключей у 2-ух Классификация задач сортировки и поиска частей и перестановка 2-ух частей. Подсчет конкретно этих операций лежит в базе способов оценивания трудозатратности алгоритмов сортировки.

Способы сортировки массивов можно поделить на две огромные группы:

· Универсальные способы, не требующие никакой дополнительной инфы об начальных данных и выполняющие сортировку “на месте”, т.е. без использования огромных объемов дополнительной памяти (к примеру – для размещения копии Классификация задач сортировки и поиска начального массива); такие способы в наилучшем случае дают оценку трудозатратности порядка O(n*log 2 n)

· Особые способы, которые или за счет некой дополнительной инфы об начальных данных, или за счет использования большой дополнительной памяти позволяют получить более высшую производительность сортировки порядка O(n) (примеры – карманная и поразрядная сортировка Классификация задач сортировки и поиска)

В свою очередь, универсальные способы сортировки делятся на две подгруппы:

· Простые способы с трудозатратностью порядка O(n2): сортировка обменом, сортировка выбором и сортировка вставками

· Усовершенствованные способы с трудозатратностью O(n*log 2 n): способ Шелла, пирамидальная сортировка, стремительная сортировка

Появляется справедливый вопрос: для чего необходимы простые способы, если есть более резвые усовершенствованные способы? Как ни Классификация задач сортировки и поиска удивительно, вероятны ситуации, когда простые способы оказываются лучше усовершенствованных. Подобные ситуации уже были упомянуты выше: если нужно сильно много (сотки тыщ либо миллионы) раз повторить сортировку очень маленьких массивов (несколько 10-ов частей), то внедрение простых способов может дать некий выигрыш, так как компонента n2 оценочной функции при малых n Классификация задач сортировки и поиска не оказывает решающего воздействия на общий итог. Не считая того, простые способы сортировки имеют только ординарную и понятную программную реализацию, что далековато не всегда можно сказать об усовершенствованных способах.

Общая систематизация способов сортировки приводится на схеме. Описание всех способов приводится дальше в пособии.


Аналогично можно провести систематизацию способов Классификация задач сортировки и поиска поиска. Сначала – внутренний поиск и наружный поиск. Внутренний поиск – универсальный и особый. Универсальный – поиск в упорядоченном либо неупорядоченном наборе данных. Неупорядоченный набор – способ обычного перебора (массив, перечень, время от времени – дерево), упорядоченный – способ двоичного поиска в массиве либо дереве. Особый способ поиска в массиве (хеш-поиск) подразумевает необыкновенную его компанию и применяется при определенных ограничениях (правда, при выполнении этих ограничений данный Классификация задач сортировки и поиска способ дает потрясающую производительность – одно сопоставление для поиска Хоть какого элемента, независимо от объема входных данных!). Наружный поиск реализуется для сверхбольших объемов данных, которые нельзя сразу расположить в основной памяти и просит использования наружных файлов (один из самых узнаваемых способов основан на использовании так именуемых B-деревьев). Универсальные способы Классификация задач сортировки и поиска поиска подверглись рассмотрению ранее, а другие рассматриваются ниже, после описания способов сортировки.


klassifikaciya-termobelya.html
klassifikaciya-testov-po-predmetu-diagnostirovaniya-4-glava.html
klassifikaciya-testov-po-predmetu-diagnostirovaniya-9-glava.html