53463

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

Доклад

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

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

Русский

2014-04-01

26.29 KB

0 чел.

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

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

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

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

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

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

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

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

 


 

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

53206. Інтелектуальна гра «Розумники і розумниці» 146 KB
  У кімнату заходять ведучі Ведучий1: Добрий день дорогі друзі Ведучий2: Добрий день шановні гості Ми раді бачити Вас на нашій фізичній інтелектуальній грі яка називається Розумники і розумниці. Ведучий1: Ми розпочнемо з легенди. Ведучий2: А для цього проведемо невелике змагання. Привітаємо наших учасників У кімнату входять команди і займають свої місця за двома столами Ведучий1: А хто стане переможцем вирішить наше компетентне журі.
53207. ІНТЕЛЕКТУАЛЬНА ГРА «НАРОД СКАЖЕ – ЯК ЗАВ’ЯЖЕ» 320 KB
  Недарма сказано що без будьякої іншої науки ще можна обійтися а без знання рідної мови аж ніяк. Ним можна клювати як дзьобом. На ньому можна зарубати як на пні. Його можна нагострити як ніж.
53208. Все про злочин і покарання (Правова гра для учнів 10 – 11 класів) 93 KB
  Свій варіант озвучує команда якщо має відповідь. Відповідь: 2001 р. Відповідь: 18 років. Відповідь: матеріальна або дисциплінарна два варіанта відповіді 4.
53209. Інтелектуальна гра «Ми - українці» 63 KB
  Доброго дня всім присутнім у нашій залі Вітаю вас на інтелектуальній грі Ми українці слайд 1 Звучить пісня Ти моя Україна у виконанні М. Конкурс 1 Київщина: із минулого в майбутнє слайд 3 Ведучий. Аеропорт у місті Борисполі Скільки районів входить до складу Київської області 25 Підсумки конкурсу оголошує журі Конкурс 2 Народознавче лото слайд 4 Ведучий. Вболівальники пригадують найвідоміші свята українців слайд 5 Питання конкурсу: Саме на це свято чоловіки за старовинним звичаєм варили пиво.
53210. Інтелектуальна гра-шоу для старшокласників «Любіть свою мову й ніколи її не забудьте в житті…» 153.5 KB
  Сьогодні у міжнародний день рідної мови свято української мови одного з найцінніших надбань які створили й залишили нам наші попередники. Пізнати історію рідної сторони і рідної мови нам допомагають книги і самобутня творчість нашого народу: мелодійні пісні та думи барвисті коломийки та ліричні хороводи чарівний фантастичний світ казок. Хай же сьогоднішнє свято відкриє перед вами дорогі друзі шанувальники української мови розум мудрість гумор нашого талановитого народу.
53211. Ділова гра «Міжнародна конференція «Здоровими бути класно!» з проблем шкідливих звичок» 109.5 KB
  Виступ дітей із дорожніми знаками у руках які вони демонструють під час виступу. Дбати про здоровя знак інвалід потрібно з самого народження з першого крику дитини знак U. Друже не поспішай знак 1.33 зануритися у круговерть знак 4.
53212. ІНТЕЛЕКТУАЛЬНА ГРА “НАЙРОЗУМНІШИЙ” 244 KB
  На роздуми вам дається 15 секунд за які ви повинні вибрати правильну відповідь. Правильна відповідь: в пташка Спеціальність лікаря Айболита: а хірург; б ветеринар; в санітар; г окуліст. Правильна відповідь: б ветеринар 3. Правильна відповідь: в33 4.
53213. ГРА-МАНДРІВКА «СВІТ ПРОФЕССІЙ» 985 KB
  На дошці записані слова Вольтера: Жити значить працювати Праця є життя людини. Життя ― це праця і бережливість. Хліб ― праця багатьох людей. І їхня праця потрібна завжди і скрізь.
53214. Ділова гра для педагогічних працівників «Вплив сюжетно-рольової гри на формування партнерських взаємин дошкільників» 60 KB
  Час відведений для гри заповнюється читанням книг підготовкою до свят організаційними видами діяльності. Виникає питання: чому вихователі і батьки спокійно жертвують часом для гри на користь будьякої іншої діяльності Чому дорослі позбавляють малюків можливості грати з однолітками Педагогічна дискусія. Вихователь зобов'язаний направляти гру не руйнуючи її зберігаючи самостійний і творчий характер ігрової діяльності дітей безпосередність переживань віру в правду гри.