Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Метод Шелла.

Цей метод запропонував Donald Lewis Shell в 1959 p. Спочатку треба усунути масовий безлад в масиві, порівнюючи елементи, які далеко стоять один від одного. Далі інтервал між елементами, які порівнюються, поступово зменшується до одиниці. На останніх стадіях сортування зводиться до перестановки сусідніх елементів.

Весь масив розбивається на частини. Візьмемо деяке число t і розглянемо тільки ті елементи початкового набору, індекс яких буде кратний t: i=t, 2t,3t, ....

Розглянемо наступний набір даних:

-6,5,0,13,-9,4,8,-15,9,9,3,1

Порівнювати будемо за таким набором t=9, 5,3,2, 1.

 

Таблиця 4.1. Таблиця сортування за методом Шелла

 

і
t=9 -6 -9 -15
  -6 -9 -15
  -6 -9 -15
t=5 -6 -9 -15
  -6 -9 -15
  -6 -9 -15
  -6 -15 -9
  -6 -15 -9
  -6 -15 -9
  -6 -15 -9
t=3 -6 -15 -9
  -6 -15 -9
  -6 -9 -15
  -6 -9 -15
t=2 -6 -9 -15
  -15 -9 -6
t=l -15 -9 -6
  -15 ' -9 -6

Єдиною характеристикою сортування Шелла є приріст - відстань між елементами, що впорядковують, в залежності від проходження. В кінці приріст завжди дорівнює одиниці - метод завершується звичайним сортуванням вставками, але саме послідовність приростів визначає ріст ефективності.

Одним з найкращим є послідовність, яка була представлена Р.Седжвіком. Його послідовшсть має вид

 

 

inc[S] =

9*2s -9*2+1 якщо s парне

8*2s-6*2+1 якщо s непарне

При використанні такого приросту середня кількість операцій O(n7/6 ), найгіршому випадку - порядку O(n4/3).

Приведемо один з варіантів програм реалізації метода Шелла.

int increment (long inc[], long size)

{

intpl,p2,p3,s;

Pl=p2=p3=l;

s=-l;

do

{ if (++s%2)

inc[s]=8*pl-6*p2 + l;

else

inc[s]=9*pl-9*p3+l;

p2*=2;

p3*=2;

pl*=2;

} while (3*inc[s]<size);

return s>0? -s: 0;

}

template <class T>

void shellSort(T a[], long size){

long inc, i,j, seg[40];

int s;

// обчислення послідовності прирісту

s= increment(seg, size);

while (s>=0)

{//сортування включенням з інкрементами іпс[]

inc=seg[s--];

for (i=inc; i<size; i++)

{Ttemp=a[i];

for (j=i-inc; (j>=0)&&(a[j]>temp); j-=inc)

a[j+inc] = a[j];

a[j+inc]=temp;

}

}

}

 


Читайте також:

  1. D) методу мозкового штурму.
  2. H) інноваційний менеджмент – це сукупність організаційно-економічних методів управління всіма стадіями інноваційного процесу.
  3. I Метод Шеннона-Фано
  4. I. Метод рiвних вiдрiзкiв.
  5. VII. Нахождение общего решения методом характеристик
  6. А. науковий факт, b. гіпотеза, с. метод
  7. Автоматизація водорозподілу на відкритих зрошувальних системах. Методи керування водорозподілом. Вимірювання рівня води. Вимірювання витрати.
  8. Агрегативна стійкість, коагуляція суспензій. Методи отримання.
  9. АгротехнІЧНИЙ метод
  10. Адаптовані й специфічні методи дослідження у журналістикознавстві
  11. Адміністративні (прямі) методи регулювання.
  12. Адміністративні методи - це сукупність прийомів, впливів, заснованих на використанні об'єктивних організаційних відносин між людьми та загальноорганізаційних принципів управління.




Переглядів: 662

<== попередня сторінка | наступна сторінка ==>
Сортування - це процес, який дозволяє впорядкувати множину подібних даних у порядку зростання або убування. | Сортування злиттям.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.014 сек.