Дефиниция на Persistent_sort на Persistent_sort и синоними на Persistent_sort

От Уикипедия, свободната енциклопедия

Устойчиво (стабилно) сортиране - сортиране, което не променя относителния ред на сортираните елементи, които имат едни и същи ключове. Повечето прости методи за сортиране са стабилни, повечето сложни не са.

Стабилността е много важна характеристика на алгоритъма за сортиране, но въпреки това почти винаги може да бъде постигната чрез удължаване на оригиналните ключове за сметка на допълнителна информация за първоначалната им поръчка. Въпреки очевидната необходимост, произтичаща от името, стабилността изобщо не е необходима за правилното сортиране и най-често не се наблюдава, тъй като почти винаги се изисква допълнителна памет и време, за да се осигури това.

Съдържание

Здрави алгоритми за сортиране

Сливане на сортиране с допълнителна памет

С този алгоритъм за сортиране първоначалният масив първо се разделя рекурсивно на части, докато всяка част от масива съдържа един или нула елементи (при всяка стъпка от рекурсията разделянето се намалява наполовина). След това получените части се "сливат" по двойки. Общата сложност на алгоритъма е O (н дневник н), докато алгоритъмът изисква O (н) допълнителна памет за съхранение на обединени масиви.

Сортиране с използване на трайно разделяне

Този алгоритъм е подобен на алгоритъма за бърза сортировка. Точно както в алгоритъма за бързо сортиране, в този алгоритъм оригиналният масив е разделен на две части - в едната всички елементи са по-малки или равни на някакъв въртящ елемент, а в другата са по-големи или равни. След това разделените части на масива се сортират рекурсивно по същия начин. Разликата между този алгоритъм и алгоритъма за бърза сортировка е, че той използва стабилно разделение вместо нестабилно. По-долу е дадено изпълнение на псевдокод на този алгоритъм:

N ← a [1]; m ← StablePartition (a [1.n], N); Сортиране (a [1.m]); Сортиране (a [m + 1.n]);

m ← n/2; m1 ← StablePartition (a [1.m], N); m2 ← m + StablePartition (a [m + 1.n], N); Завъртане (a [m1.m2], m); връщане (m1 + (m2-m));

if (a [1] return (1); else return (0)

if (n> m> 1) // в масива има поне два елемента и смяната има смисъл

смяна ← m-n; // броят на позициите, чрез които ще се извърши смяната gcd ← GCD (m-1, n); // GCD е най-големият общ делител за i ← 0 до gcd-1 do head ← i + 1; headVal ← a [глава]; текущ ← глава; следващ ← глава + смяна; докато (nexthead) направете [текущ] ← a [следващ]; текущ ← следващ; следващ ← следващ + смяна; if (next> n) next ← next-n; a [текущ] ← headVal;

Отнема O (н дневник н) елементарни операции. Тъй като "дълбочината" на извършеното рекурсивно спускане е средно O (log н) тогава общата сложност на алгоритъма е O (н log² н). В този случай алгоритъмът ще се нуждае от O (log н) стекова памет, въпреки че в най-лошия случай общата сложност е O (н² дневник н) и отнема O (н) памет.

---