Св:Сортировката на Шел прави по – малк от N(h-1)(k-1) /q сравнения за g – сортиран фаил, к-то е h и k подреден, ако h и k са взаимно прости числа.
Св: Сортиров на Шел прави по – малко от O(N³'²) сравн. за нарастването 1 4 13 40 121 364 и т.н. Св. Сортиров. на Шел прави по – малко от O(N) на степен 4/3 срав. за нараст 1 8 23 77 281 1073 ... Св: Сорт. на Шел прави по – малко от О(N(logN)²)
сравн. за нараст 1 2 3 4 6 9 8 12 18 27 16 24 36 54 81.
Сортировката на Шел е много по – бърза от елементарните сортировки. Даже когато нарастванията са степени на 2., но някой редици на нарастване могат да я ускорят 5 и повече пъти.
Сортир. на Шел работи приемливо добре в/у разнообразие от типове файлове, а не само в/у файлове от случайни числа
Сорт. на Шел е избраният метод за много сортиращи приложения защото има прием-ливо време за изпълнение даже за умерено големи файлове и изисква малко кол. код, който е лесно да се пусне в действие.
Бързо сортиране.Стратегии за разделяне.Избор за разделящ елемент.Анализ
Сортиранечрезсливане.Анализ
В информатиката сортиранеточрезсливане е алгоритъм за сортиране, базиран на сравняване, който има сложност Θ(nlogn). Алгоритъмът се гради на принципа „разделяй и владей“. Създаден е от Джон фон Нойман през 1945.
Принцип на действие.
Несортирания списък по произволен начин се разделя на два подсписъка с приблизително обща дължина (за линейно време)
Сливат се два подсписъка в нов сортиран списък (за линейно време)
Пример:
Процесът на съчетаване на две сортирани редици в една се нарича сливане.
Ако имаме сортираните списъци l1 и l2 и искаме да ги слеем в трети списък l, който също да бъде сортиран, можем да направим следното: 1.Докато има елементи в l1 и има елементи в l2:
Ако l1.pStart->data < l2.pStart->data
премахваме първия елемент на l1 и го поставяме в края на l
Иначе
премахваме първия елемент на l2 и го поставяме в края на l 5.Като излезем от горния цикъл или l1 или l2 е празен
6.Ако l1 е празен долепяме l2 към l1 7.Ако l2 е празен долепяме l1 към l2 8.Край.
За да сортираме един списък чрез сливане:
Ако списъкът има 0 или 1 елемент, то той е сортиран - Край
Иначе го разделяме на 2 части
Сортираме първата част - като използваме отново тази функция 4.Сортираме втората част - като използваме отново тази функция 5.Сливаме двете части в стария списък.
6.Край
Недостатъкът на този алгоритъм е, че не сортира на място и ако сортирахме масив щеше да ни е нужна допълнителна памет за още един масив. Разпределението на паметта за новия масив е бавна операция. Това обаче не важи за свързаните списъци. Също така при тях намирането на оста нужна при бързото сортиране (quick sort) не е толкова лесно. Затова за сортиране на списъци ще използваме сортирането чрез сливане.
