53463

Оптимизация процедуры Shell_sort, особенности

Доклад

Информатика, кибернетика и программирование

Сортировка Шелла — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга.

Русский

2014-04-01

26.29 KB

0 чел.

Оптимизация процедуры Shell_sort, особенности.

Сортировка Шелла — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.

При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии . После этого процедура повторяется для некоторых меньших значений , а завершается сортировка Шелла упорядочиванием элементов при . Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

  1. отсутствие потребности в памяти под стек;
  2. отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

Сортировка Шелла была названа в честь её изобретателя — Дональда Шелла, который опубликовал этот алгоритм в 1959 году.

Среднее время работы алгоритма зависит от длин промежутков — , на которых будут находиться сортируемые элементы исходного массива ёмкостью на каждом шаге алгоритма. Существует несколько подходов к выбору этих значений:

  1. первоначально используемая Шеллом последовательность длин промежутков:  
  2.  значения
  3. последовательность: , если i четное и , если i нечетное
  4.  все значения

 


 

А также другие работы, которые могут Вас заинтересовать

33756. Договор о снабжении энергетическими и другими ресурсами 15.89 KB
  Договор о снабжении энергетическими и другими ресурсами. По договору энергоснабжения энергоснабжающая организация обязуется подавать потребителю абоненту энергию через присоединенную сеть а потребитель абонент обязуется оплачивать принятую энергию а также соблюдать предусмотренный договором режим ее потребления. Договор энергоснабжения является разновидностью договора куплипродажи и по своей природе двусторонний и возмездный. Особенности договора энергоснабжения: необычность электроэнергии как объекта: электроэнергию нельзя...
33757. Institute on Mathematics and Mechanics, Urals Branch of Russian Academy of Science 16.5 KB
  Semiotics, dealing with sign systems and with practice of their functioning, may be considered as tools for descriptions of theories of HCI and Computer Visualization just as Mathematics is tools for descriptions of Physics Theories.
33758. Договор дарения 16.24 KB
  Договор дарения. Договор дарения договор по которому одна сторона даритель безвозмездно передает или обязуется передать другой стороне одаряемому вещь в собственность либо имущественное право требование к себе или третьему лицу либо освобождает или обязуется освободить ее от имущественной обязанности перед собой или третьим лицом. Разновидностью договора дарения является пожертвование дарение сделанное в отношении неопределенного круга лиц в общеполезных целях. Договор дарения может быть как консенсуальным так и...
33759. Договор ренты (понятие, виды) 14.34 KB
  Договор ренты понятие виды. По договору ренты одна сторона получатель ренты передает другой стороне плательщику ренты в собственность имущество а плательщик ренты обязуется в обмен на полученное имущество периодически выплачивать получателю определенную денежную сумму либо предоставить средства на его содержание в иной форме. Виды договора ренты: постоянная рента; пожизненная рента; пожизненное содержание с иждивением. Эти виды договора ренты имеют ряд общих признаков но различаются: формой предоставления содержания...
33760. Исполнение, новация и другие способы прекращения обязательств 17.24 KB
  Наиболее частым и нормальным способом прекращения обязательства является его исполнение Однако это имеет место если произведенное исполнение является надлежащим т. соответствует всем условиям самого обязательства и требованиям законодательства установленным для данного вида обязательств. Факт исполнения обязательства во взаимоотношениях предпринимателей обычно подтверждается составлением двустороннего акта приемки. Возможно частичное исполнение обязательства по предмету или сроку и тогда обязательство в соответствующей части...
33761. Понятие, значение и виды договоров 15.69 KB
  Понятие значение и виды договоров. Договор это соглашение двух или нескольких лиц об установлении изменении или прекращении гражданских прав и обязанностей. Значение договоров: договор одно из оснований возникновения гражданских прав и обязанностей; часто под договором понимается не просто юридический факт а само правоотношение возникающее из соглашения сторон; договор основной способ оформления отношений участников гражданского оборота; договоры опосрвдуют движение объектов гражданских прав от одних субъектов к...
33762. Содержание и форма договора 15.1 KB
  Содержание и форма договора. Содержание договора составляет совокупность согласованных сторонами условий. Среди условий договора необходимо выделять существенные условия. Существенными являются условия о предмете договора условия которые названы в законе или иных правовых актах как существенные или необходимые для договоров данного вида а также все те условия относительно которых по заявлению одной из сторон должно быть достигнуто соглашение ч.
33763. Основные и предварительные договоры. Договор присоединения 15.35 KB
  Основные и предварительные договоры. Договор присоединения. Основной договор непосредственно порождает права и обязанности сторон связанные с перемещением материальных благ: передачей имущества выполнением работ оказанием услуг и т. Предварительный договор это соглашение сторон о заключении основного договора в будущем.
33764. Свободные и обязательные договоры. Характеристика публичного договора 15.02 KB
  Заключение же обязательных договоров как это следует из самого их названия является обязательным для одной или обеих сторон. Обязательным участником публичного договора является коммерческая организация. При отсутствии хотя бы одного из указанных признаков договор не является публичным и рассматривается как свободный договор. Так если предприятие розничной торговли заключает с гражданином договор куплипродажи канцелярских товаров которыми торгует это предприятие то данный договор является публичным.