53463

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

Доклад

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

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

Русский

2014-04-01

26.29 KB

0 чел.

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

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

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

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

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

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

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

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

 


 

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

34115. Психоанализ и психоаналитическая терапия, основные принципы 67.5 KB
  Основные принципы классического психоанализа разработанного в наследие З. Основные отличия внешние организационные и методологические основы клинического психоанализа психоаналитической терапии. Обратить особое внимание на основные принципы классического психоанализа разработанного З. Предлагаю обсудить вопрос который постоянно в той или иной форме возникает в ходе как профессиональных так и студенческих обсуждений отголоски этой дискуссии звучат и в раздающихся все чаще и чаще утверждениях о том что под брендом психоанализа скрывается...
34116. Показание и противопоказания психоаналитической терапии 62 KB
  Некоторые особенности российского пациента. Так же следует обратить особое внимание на особенности российского пациента и особенности построения терапии в зависимости от психологической конституции. Фрейд полагал что последние две силы связаны между собой и что существует некоторое соответствие внешней реальности и психологической предрасположенности самого пациента Тем самым предполагалось наличие патогенных компонентов в прошлом которые должны предопределять повышенную чувствительность по отношению к определенным обстоятельствам в...
34117. Сеттинг. Определение, взаимозависимость терапевтической задачи и сеттинга 46.5 KB
  Роль сеттинга в построение переходного пространства в рамках котрого происходит развертывание фантазий пациента и осуществляется работа с переносом и сопротивлением. Следует разобраться в ключевой роли сеттинга для формирования у пациента способности восприимать и продуцировать символическую организацию мира. Пациент лежит на кушетке или софе а психоаналитик сидит позади него оставаясь большей частью вне поля зрения пациента стараясь вмешиваться в процесс мышления пациента настолько мало насколько это возможно и не иначе как посредством...
34118. Структурные изменения, как основная цель психоанализа и психоаналитической терапии 62.5 KB
  Еще в 1894 году в работе âНевропсихозы защитыâ он показывает что абсисивный симптом является компромиссом между неприемлемым сексуальным желанием защитой против удовлетворения этого желания и раскаянием или самонаказанием. Давайте попробуем понять фразу: Каждый симптом и каждая невротическая черта характера является компромиссным образованием И попробуенм в связи с этим ответить на два вопроса. Компромиссное образование является патологическим когда оно характеризуется любой комбинацией следующих черт: слишком большое ограничение...
34119. Терапевтические отношения. Форма и содержание 61 KB
  Именно в этом взаимодействие пациент продуцирует материал для анализа а аналитик создает условия для его интеграции в психики пациента что и будет являться основой для терапевтических изменений. Процесс ассимиляции связан с позитивной реакцией пациента на тот способ при помощи которого терапевт испоьзует полученный материал с тем как их усваивает Эго и с теми изменениями которые мы назвали âлечебными факторамиâ. он представляет собой решающее звено между использованным способом действия терапевта и реальным эффектом для пациента...
34120. Ответы на экзаменационные вопросы Эго-психология 470.5 KB
  Положение ЭГОпсихологии в современной психоаналитической теории. ЭгоПсихология направление в психоаналитической теории развитие которого как считалось началось с работы З. В какойто степени это теория конкурирующая с теорией влечений и теорией объектных отношений хотя существует другая точка зрения определяющая Эгопсихологию как интегрирующую концепцию.
34121. Психоаналитическая терапия. Ответы на экзаменационные вопросы 325.5 KB
  Такой подход значительно сужает взгляд на проблему так как из вида упускается важнейший момент содержания терапевтического процесса которое образуется благодаря живому творческому взаимодействию его непосредственных участников пациента и терапевта их влиянию друг на друга и на ход терапии в целом. Первоначально основатель психоанализа просто использует медицинскую однонаправленную модель в которой значение имеет только личность пациента катарсический метод. В дальнейшем обосновывая и развивая идею переноса Фрейд хотя и вводит в...
34122. Психодиагностика. Ответы на экзаменационные вопросы 501.5 KB
  Именно это и явилось основной предпосылкой возникновения психодиагностики как отдельной области научных знаний и системы методов исследования. Причиной этому послужили успехи в области исследования хромосомных болезней человека. Основным в исследованиях XIX века является то что психическое становилось особой областью экспериментального исследования отличной от физиологии. наибольшее влияние на становление психологической диагностики оказали экспериментальная психология диффференцальная психология прикладная психология и тестология;...
34123. Возрастная психология. Ответы на экзаменационные вопросы 811 KB
  Возрастная психология или психология развития направлена на исследование особенностей проявления и развития психики человека в различные возрастные периоды. Системное рассмотрение всего жизненного цикла позволяет выявить общие закономерности индивидуального развития человека и использовать их для решения таких существенных задач возрастной психологии как: Научное обоснование возрастных норм психофизиологических функций. Научное прогнозирование развития человека развертывание психических ресурсов человека. Определение наиболее...