Сортировка чрез вмъкване Същност на алгоритъма

Сортировка чрез вмъкване

Същност на алгоритъма

Анализ на алгоритъма

Сортировка чрез селекция

Същност на алгоритъма

Анализ на алгоритъма

Сортировка по метода на мехурчето

Същност на алгоритъма

Анализ на алгоритъма

Сортировка на Шел

Същност на алгоритъма

Анализ на алгоритъма

Сортировка чрез сливане

Същност на алгоритъма

Анализ на алгоритъма

Бърза сортировка

Анализ на алгоритъма

Избор на разделящ елемент

Избор на стартегия за разделяне

Малки масиви

Програмна реализация

Най-лош случай

Най-добър случай

Среден случай

Изтегляне 359.1 Kb.

Дата	31.12.2017
Размер	359.1 Kb.
	#38445

Един от най-опростените алгоритми за сортиране е сортировката чрез вмъкване. Тя се изпълнява на N – 1 паса, при което на всеки пас с индекс p елементите на позиции от 0 до p са в сортиран ред.

Фигурата по-долу илюстрира подредбата на елементите след всеки пас при сортировката чрез вмъкване.

Първоначална подредба	34	8	64	51	32	21	Позиции на преместване
p = 1	8	34	64	51	32	21	1
p = 2	8	34	64	51	32	21	0
p = 3	8	34	51	64	32	21	1
p = 4	8	32	34	51	64	21	3
p = 5	8	21	32	34	51	64	4

На пас с индекс p елементът на позиция p се премества на ляво, докато заеме правилно място. Кодът по-долу реализира тази стратегия.

...

int j;

/*1*/ for( int p = 1; p < N; p++)

{

/*2*/ tmp = a[p];

/*3*/ for ( j = p; j > 0 && tmp < a[j – 1]; j--)

/*4*/ a[j] = a[j – 1];

/*5*/ a[j] = tmp;

}

...

Кодът между втория и петия ред премества елементите без да ги разменя. Елементът от позиция p се съхранява в променлива tmp и всички по-големи елементи, които го предшестват се преместват една позиция на дясно. След това съхраненият в променливата tmp елемент се поставя на освободената позиция.

От кодът по-горе се вижда, че за всяка стойност на p вложеният цикъл се изпълнява p + 1 пъти, т.е.:

Ако елементите са сортирани в обратен ред времето за сортиране ще бъде O(N), тъй като вложеният цикъл ще приключва незабавно. Действително, ако елементите са почти сортирани, сортировката чрез вмъкване ще се изпълни бързо.

Инверсия в един масив от числа е всяка наредена двойка (i, j), имаща свойството i < j и a[i] > a[j]. В разгледания пример масивът има девет инверсии – (34, 8), (34, 32), (34, 21), (64, 32), (64, 21), (51, 32), (51, 21) и (32, 21). Всъщност това е броят на размените, които трябва да се реализират при сортировката чрез вмъкване. Размяната на два съседни елемента премахва точно една инверсия.

За да се определи средното време, необходимо за сортировката чрез вмъкване, може да се използва средният брой инверсии за една пермутация. Нека предположим, че входящият масив не съдържа дублиращи се елементи и представлява пермутация на първите N цели числа.

Средният брой на инверсиите в масив от N елемента е N(N – 1)/4.

*За всеки списък L от елементи, разглеждаме списъка L_r, който съдържа същите елементи, но подредени в обратен ред. За разглеждания пример списъкът L_r включва елементите 21, 32, 51, 64, 8, 34. Разглеждаме също така всяка двойка елементи (x, y) в списъка, за която y>x. Такива двойки елементи представят инверсиите. Общият им брой за двата списъка L и L_r e N(N-1)/2. Следователно средния брой на инверсиите е N(N-1)/4.*

Всеки алгоритъм, който разменя съседни елементи изисква средно O(N²) време за изпълнение.

*Доказахме, че средния брой на инверсиите е N(N-1)/4 = O(N²). Тъй като всяка размяна премахва точно една инверсия, то са необходими O(N²) размени.*

Този извод може да се направи и за други алгоритми, които разменят близки един до друг елементи, като например сортиране по метода на мехурчето и сортиране чрез селекция.

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

Фигурата по-долу показва начина, по който се обхождат елементите на първия пас от сортирането на масив с елементи 37, 19, 47, 15, 40, 41.

Фигурата по-долу илюстрира подредбата на елементите след всеки пас при сортировката чрез селекция.

Кодът по-долу реализира алгоритъма чрез селекция.

...

int p, j;

for(p = 1; p < N; i++)

{ int min = p;

for(j = p+1; j < N; j++)

if (a[j] < a[min]) min = j;

exch(a[p], a[min]);

}

...

За всяко p от 1 до N-1 разменяме a[p] с минималния елемент от a[p], …, a[N]. Тъй като индексът p преминава от ляво на дясно, елементите отляво на него са в техните крайни позиции. Ето защо масивът е напълно сортиран, когато p достигне десния край.

Недостатък: Времето за изпълнение на селективната сортировка зависи съвсем малко от количеството на вече подреденото във файла. Процесът за намиране на минималния елемент за един пас през файла не носи информация за това къде би могъл да се открие следващия минимален елемент. Например тази сортировка заема почти същото време за вече сортиран файл или за файл, при който елементите са с еднакви ключове.

Приложение: Селективната сортировка се препоръчва за сортиране на файлове с огромни елементи и малки ключове, тъй като времето за преместване на елементите доминира над времето за извършване на сравнения.

Броят на пасовете и общият брой сравнения при селективната сортировка е строго фиксиран дори и ако масивът е вече сортиран или е подреден в низходящ ред. На първия пас за масив с N елемента се правят N-1 сравнения. На втория пас се правят N-2 сравнения, защото един от елементите вече е разположен правилно и не участва в сравненията. На третия пас се правят N-3 сравнения и т.н. Общият брой сравнения се изчислява по следния начин:

(N – 1) + (N – 2) + (N – 3) + … + (N – (N – 1)) =

Следователно селективната сортировка използва около N²/2 сравнения. Броят на размените за масив с N елемента е N-1, тъй като за всеки елемент с изключение на последния се прави по една размяна.

Сортировката по метода на мехурчето е подходяща с масиви (файлове), които са почти сортирани. При нея последователно се преминава през файла, при което съседните елементи, които не са сортирани, се разменят. Да предположим, че винаги преминаваме отдясно наляво през файла. На всеки пас открития минимален елемент се разменя с елементите отляво на него, при което той се поставя на своята крайна позиция. Ето защо за сортирането на N елемента са достатъчни N-1 паса през файла.

Фигурата по-долу показва начина, по който се разменят елементите на първия пас от сортирането на масив с елементи 37, 19, 47, 15, 40, 41.

Фигурата по-долу илюстрира подредбата на елементите след всеки пас при сортировката по метода на мехурчето.

Кодът по-долу реализира алгоритъма.

...

int i, j;

for (i = 1; i <= N; i++)

for (j = N; j > i; j--)

if (a[j] < a[j-1])

exch(a[j-1], a[j])

...

За всяко i от 1 до N-1 вътрешният цикъл намира минималния елемент сред елементите a[i], …, a[N]. През елементите a[i], …, a[N] се преминава от дясно на ляво. Те се сравняват и при необходимост се разменят, при което текущия минимален елемент се поставя в позиция a[i].

Сортировката по метода на мехурчето е неадаптивна. Тя може да се подобри чрез проверка дали въобще са правени размени при някой от пасовете, при което външния цикъл да се прекъсне чрез break.

В общия случай сортировката по метода на мехурчето е по-бавна от селективната сортировка и сортировката чрез вмъкване.

Сортировката по метода на мехурчето използва около N²/2 сравнения и N²/2 размени за средния и най-лошия случай. i-тият пас на сортировката по метода на мехурчето изисква N-i операции за сравнения-размени, така че доказателството е като за селективната сортировка. Когато алгоритмът се модифицира така, че да свърши, когато файлът е сортиран, времето за изпълнение зависи от входа. Ако файлът е вече подреден се изисква само един пас. Ако файлът, обаче е подреден в обратен ред i-тият пас изисква N-i сравнения и размени.

Сортировката на Шел носи името на своя откривател – Donald Shell. Това е един от първите алгоритми, които преодолява квадратичното време за изпълнение. Той работи, сравнявайки елементи, които се намират на определено разстояние един от друг. Разстоянието между елементите намалява, като при последната фаза се сравняват близи помежду си елементи. Ето защо този алгоритъм понякога прилича на инкрементално намаляващо сортиране.

Сортировката на Шел използва редица от числа h₁, h₂, …, h_t, която се нарича редица на нарастването. Всички редици на нарастването започват с h₁ = 1, но няко са по-ефективни от други. На определена фаза от сортирането, при стойност на h = h_k, за всяко i е изпълнено условието:

Това означава, че всички елементи които са на разстояние h_k един от друг са сортирани. Такъв масив, респективно файл от елементи се нарича h_k сортиран. Фигурата по-долу показва масив, сортиран посредством сортировка на Шел.

Първоначална подредба	81	94	11	96	12	35	17	95	28	58	41	75	15
h = 5	35	17	11	28	12	41	75	15	96	58	81	94	95
h = 3	28	12	11	35	15	41	58	17	94	75	81	96	95
h = 1	11	12	15	17	28	35	41	58	75	81	94	95	96

При сортировката на Шел за всяка позиция i при редица на нарастването h_k, h_k+1, …, N-1, елементът се поставя на правилната позиция в рамките на i, i-h_k, i-2h_k и т.н. Всъщност всяко h_k сортиране представлява сортиране чрез вмъкване на h_k независими подмасиви.

Предложената от Шел редица на нарастването не дава много добри резултати. Тя се изчислява по следния начин:

h_t=[N/2] h_k=[h_k₊_i/2]

Кодът по-долу реализира сортировката на Шел с предложената от негo редица на нарастването.

...

int j;

/*1*/ for ( int gap = N/2; gap > 0; gap /= 2 )

/*2*/ for ( int i = gap; i < N; i++)

{

/*3*/ tmp = a[i];

/*4*/ for (j = i; j >= gap && tmp < a{j-gap]; j-= gap)

/*5*/ a[j] = a[j-gap];

/*6*/ a[j] = temp;

}

...

Вермето за изпълнение на сортировката на Шел зависи от редицата на нарастването.

T:

В най-лошия случай сортировката на Шел изисква време за изпълнение O(N²) при предложената от Шел редица на нарастването.

*Нека N е степен на 2. Така всички нараствания ще бъдат четни, с изключение на последното, което е 1. Нека входния масив има елементи по-големи от N/2 на четните позиции и елементи по-малки от N/2 на нечетните позиции. На последния пас, елементите по-големи от N/2 все още остават на своите четни позиции, а елементите по-малки от N/2 – на своите нечетни позиции. i-тият по-малък от N/2 елемент (i

Фигурата по-долу показва сравнително лош случай, за който N = 16. Броят на инверсиите преди последния пас е 1+2+3+4+5+6+7=28, поради което той ще отнеме значително време.

Първоначална подредба	1	9	2	10	3	11	4	12	5	13	6	14	7	15	8	16
h = 8	1	9	2	10	3	11	4	12	5	13	6	14	7	15	8	16
h = 4	1	9	2	10	3	11	4	12	5	13	6	14	7	15	8	16
h = 2	1	9	2	10	3	11	4	12	5	13	6	14	7	15	8	16
h = 1	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16

Пас с нарастване h_k включва h_k сортировки чрез вмъкване за N/h_k елементи. Тъй като сортировката чрез вмъкване изисква квадратично време, то съответния пас ще се изпълни за време:

O(h_k(N/h_k)²) = O(N²h_k)
Сумираме по броя на пасовете и получаваме следното:

Тъй като нарастванията формират геометрична прогресия със съотношение 2, a най-много време отнема последния пас, за който h_k = 1, то:

Следователно общото време за изпълнение на алгоритъма ще бъде O(N²).*

Оказва се, че малките нараствания нямат добър ефект. Hibbard предлага редица на нарастването, която дава по-добри резултати. Нарастванията в нея се формират по следния начин:

1, 3, 7, ..., 2^к – 1

В най-лошия случай сортировката на Шел изисква време за изпълнение O(N^3/2) при предложената от Hibbard редица на нарастването.

*Знаем, че преди да се реализира h_k сортиране, масивът вече е бил h_k₊₁ и h_k₊₂ сортиран. Нека разгледаме елементите от позиции p и p-i (i≤p) преди h_k сортирането. Ако i е кратно на h_k₊₁ или h_k₊₂, то a[p-i]k₊₁ и h_k₊₂, то a[p-i]k = 3, масивът е вече 7- и 15- сортиран. 52 може да се представи като линейна кобинация на 7 и 15, т.е. 52 = 1*7+3*15. Следователно а[100] не може да бъде по-голямо от а[152], тъй като a[100] ≤ a[107] ≤ a[122] ≤ a[137] ≤ a[152].

Тъй като h_k₊₂ = 2h_k₊₁+1, то h_k₊₁ и h_k₊₂ не могат да имат общ коефициент. В такъв случай можем да кажем, че всички цели числа, които са по-големи от

могат да се представят като линейна комбинация на h_k+1 и h_k+2.

Това означава, че тялото на вътрешния цикъл for може да се изпълни най-много 8h_k+4 = O(h_k) пъти за всяка N-h_k позиция. Тогава времето за изпълнение на един пас ще бъде O(Nh_k).

Ако допуснем, че около половината от нарастванията изпълняват условието:

и t е четно число, то времето за изпълнение на целия алгоритъм ще бъде:

Тъй като и двете суми са геометрични прогресии и

за h_k>h_t/2, то:

*
В средния случай сортировката на Шел изисква време за изпълнение O(N^5/4) при предложената от Hibbard редица на нарастването.

Sedgewick предлага няколко редици на нарастването, които дават време за изпълнение на алгоритъма O(N^4/3) в най-лошия случай. За средния случай това време е O(N^7/6). Най-добрата от редиците на нарастването на Sedgewick е 1, 5, 19, 41, 109,..., елементите на която се изчисляват както следва:

или

Основната операция, която се изпълнява при този алгоритъм е сливане на два сортирани списъка. Тъй като списъците са сортирани, елементите могат да се поставят в трети списък на един пас през двата входни списъка.

Използваме два входни масива A и В, един изходен масив С и три брояча – A_ctr, B_ctr и C_ctr, които първоначално указват началото на съответстващите им масиви. По-малкият елемент от A[A_ctr] и B[B_ctr] се копира в масива C на първата свободна позиция. След това броячите от участващите в копирането на елемента масиви се преместват една позиция на ляво. Когато един от двата входни масива се изпразни, елементите от другия се копират в масива С.

Фигурата по-долу илюстрира последователността от действия при сливането на два масива.

Масивът А съдържа елементите 1, 13, 24 и 26, а масивът В – елементите 2, 15, 27 и 38. Първоначално се сравняват елементите 1 и 2, при което 1 се добавя в масива С и се сравняват елементите 13 и 2:

2 се добавя в С и се сравняват елементите 13 и 15:

13 се добавя в С и се сравняват 24 и 15. Така процесът продължава, докао се сравнят елементите 26 и 27.

26 се добавя в С, при което масивът А остава празен.

Останалите в масива В елементи се добавят в масива С.

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

Сортировката чрез сливане е лесна за описание. При N=1 има само един елемент, който трябва да се сортира и решението е готово. В противен случай рекурсивно се сортират чрез сливане лявата и дясната половина на масива. Получават се две сортирани половини, които след това се сливат по-описания по-горе начин. Например, за да се сортира масив от 8 елемента – 24, 13, 26, 1, 2, 27, 38, 15, рекурсивно се сортират първите четири и последните четири елемента. Получават се две сортирани половини от елементи – 1, 13, 24, 26 и 2, 15, 27, 38. След това сливаме двете половини, при което получаваме резултата от фигурата по-горе.

Кодът по-долу показва програмната реализация на операцията сливане.

Item aux[maxN]

merge(Item a[], int l, int m, int r)

{ int i, j, k;

for(i = m + 1; i > l; i--) aux[i-1] = a[i-1];

for(j = m; j < r; j++) aux[r+m-j] = a[j+1];

for(k = l; k <= r; k++)

if(aux[j] < aux[i])

a[k] = aux[j--]; else a[k] = aux[i++];

}

Сливането се реализира чрез копиране на двата масива в масива aux, при което вторият масив е в обратен ред – гръб в гръб с първия. Първият цикъл for копира първия масив в aux и остава i да сочи l. Вторият цикъл for копира в aux втория масив и оставя j да сочи r. Сливането се извършва от третият цикъл for.

Показаната по-горе сливаща функция може да се използва при програмната реализация на алгоритъма чрез сливане:
void mergesort(Item a[], int l, int r)

{ int m = (r + l)/2;

if (r <= l) return;

mergesort(a, l, m);

mergesort(a, m+1, r);

merge(a, l, m, r);

}

Масивът a[l], …, a[r] се сортира като се дели на две части a[l], …, a[m] и a[m+1], …, a[r]. Двете части се сортират независимо, след което се сливат.

Нека N да бъде степен на 2, така че масивът винаги да позволява разделяне на две половини с четен брой елементи. При N=1 времето за сортиране е константа. За всички останали случаи времето за сортиране на масив с N елемента е равно на сумата от времето за сортиране на два масива с N/2 елемента и времето за тяхното сливане, т.е.:

T(1) = 1

T(N) = 2T(N/2) + N

Това е стандартна рекурсивна релация, която може да се реши по няколко начина. Ние ще покажем два метода.

При първият метод двете страни на равенството се разделят на N, при което равенството се запазва.

Тъй като формулата е валидна за N, което е степен на 2, то можем да напишем следното:

...

Сумираме левите и десните страни на равенствата, при което се получава следния резултат:

Умножаваме двете страни на равенството с N и получаваме:

Т(N) = NlogN + N = O(NlogN)
Алтернативния метод извършва заместване в дясната страна на равенството, използвайки следната релационна последователност:
2T(N/2) = 2(2(T(N/4)) + N/2) = 4T(N/4) + N
Следователно получаваме:
Т(N) = 4T(N/4) + 2N
Отново извършваме заместване в дясната страна на равенството:
4T(N/4) = 4(2(T(N/8)) + N/4) = 8T(N/8) + N
Следователно получаваме:
Т(N) = 8T(N/8) + 3N
Продължавайки по този начин, получаваме:
Т(N) = 2^kT(N/2^k) + kN
Полагаме k=logN и получаваме:
Т(N) = NТ(1) + NlogN = NlogN + N

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

Ако броят на елементите в масива S е 0 или 1, то алгоритъмът приключва.
Избира се елемент v от масива S, който да бъде разделящ (pivot).
Останалите елементи от масива, без елемента v, се разделят на две групи:

За двете групи елементи се изпълнява бързата сортировка.

Възниква въпросът какво да се прави с елементите, които са равни на разделящия елемент. Интуитивното решение е половината от тях да се поставят в S₁, a другата половина в S₂.

Фигурата по-долу илюстрира бързата сортировка за множество от числа.

Разделящият елемент е 65 и е избран по случаен начин. Останалите елементи се разделят в две множества. Рекурсивно се сортират елементите от двете множества, след което се обединяват.

Очевидно е, че алгоритъмът ще сортира елементите, но не е очевидно защо работи по-бързо от сортировката чрез сливане. Подобно на нея той също рекурсивно решава две подзадачи, извършвайки допълнително работа (стъпка 3), която изисква линейно време за изпълнение. За разлика от селективната сортировка при бързото сортиране подзадачите не са с еднакъв обем, което е потенциално лощо. Все пак той е по-бърз, защото разделянето се прави на място и е много ефективно.

Както вече беше споменато от съществено значение при реализацията на алгоритъма е изборът на разделящ елемент.

Популярен, но неинформативен подход е за разделящ елемент да се използва първия елемент от масива. Това е приложимо ако елементите на входа са подредени по случаен начин. Ако елементите са вече подредени или постъпват в обрате ред, то този подход води до погрешно разделяне, тъй като всички те ще попаднат в S₁ или S₂. Още по-лошо обаче е, че това ще се случва непрекъснато при рекурсивните извиквания, което означава алгоритъмът ще отнеме квадратично време без да извърши сортиране. Компромисен вариант е да се избере по-големия от първите два елемента в масива, но това може да доведе до същите проблеми.

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

Най-добрият подход е за разделящ елемент да се избере медианата на масива. Медиана на група от числа е числото, което има [N/2]-та големина. Определянето на медианата обаче е трудно и намалява бързодействието на алгоритъма. Разумен компромис е по случаен начин да се иберат три елемента от масива и след това за тяхната медиана да се използва за разделящ елемент. Тъй като случайният избор не помага много, най-често се търси медианата на първия, средния и последния елемент в масива. Този подход е известен като разделяне с медиана на тройка. Той елиминира лошите варианти, когато на входа постъпват сортирани елементи и редуцира времето за изпълнение на бързата сортировка с 5 процента.

Съществуват различни стратегии за разделяне, но тази, която ще разгледаме е известно, че дава добри резултати. Избираме разделящ елемент да бъде последния елемент от масива. Установяваме указателя i на първа позиция, а указателя j – на съседната спрямо разделящия елемент позиция. Фигурата по-долу илюстрира тази ситуация.

8	1	4	9	0	3	5	2	7	6
↑								↑
i								j

Предполагаме, че нама повтарящи се елементи. Това, което разделящата стратегия трябва да направи, е да премести малките елементи в лявата част на масива, а големите – в дясната. Разбира се, определянето на малките и големите елементи става спрямо разделящия елемент.

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

8	1	4	9	0	3	5	2	7	6
↑							↑
i							j

След първата размяна
2	1	4	9	0	3	5	8	7	6
↑							↑
i							j

Преди втората размяна
2	1	4	9	0	3	5	8	7	6
			↑			↑
			i			j

След втората размяна
2	1	4	5	0	3	9	8	7	6
			↑			↑
			i			j

Преди третата размяна
2	1	4	5	0	3	9	2	7	6
					↑	↑
					j	i

След размяна с разделящия елемент
2	1	4	5	0	3	6	8	7	9
						↑			↑
						i			p

След като елементът от позиция i се размени с разделящия елемент на последната стъпка, можем да бъдем сигурни, че всички елементи преди позиция p – позицията на разделящия елемент, са малки, и че всички елементи след позиция p са големи.

Съществен момент е обработката на елементите, които са равни на разделящия. Въпросът е кой от двата указателя да спре сканирането на масива, когато се срещат такива елементи. Ако изберем указателят i, то всички елементи, равни на разделящия ще останат в масива S₂.

За да открием добро решение, нека разгледаме случая, когато всички елементи в масива са еднакви. Когато и двата указателя спират сканирането при достигане на елементи, равни на разделящия, ще се извършват непрекъснати размени на елементи, които имат една и съща стойност. Положителният ефект в случая е, че указателите ще се пресекат в средата на масива и след азмяната с разделящия елемент, масивът ще бъде разделен на два почти равни по големина подмасива. Времето за изпълнение на алгоритъма ще бъде O(NlogN).

Когато нито един от двата указателя не спира сканирането при достигане на елементи, равни на разделящия, размени няма да има. Въпреки, че това изглежда добре, коректната имплементация ще доведе до размяна на разделящия елемент със съседния му, предпоследен елемент. Това ще доведе до създаването на различни по големина подмасиви. Времето за изпълнение на алгоритъма ще бъде О(N²), което означава че ефектът ще е същият, както ако използваме за разделящ елемент първия елемент в подреден масив. Изразходваме квадратично време без да правим нищо!

За много малки масиви (N ≤ 20) бързата сортировка не е толкова ефективна както сортировката чрез вмъкване. Тъй като бързата сортировка е рекурсивна, малки масиви ще се появяват многократно. Общо правило е за такива масиви да се използва друг метод за сортиране. По такъв начин времето за сортиране на целия масив се редуцира с около 15 процента. Препоръчителна граница, при която бързата сортировка трябва да спре е N=10. Подобни резултати се постигат, когато N е в диапазона от 5 до 20. Използвайки описаната стратегия премахваме лоши ситуации, като например търсене медиана на три елемента, когато налични са само два.

Кодът подолу показва определянето на разделящия елемент.

...

int center = (left+right)/2;

if (a[center]<[left])

swap(a[center], [left]);

if (a[right]

swap(a[right], a[left])

if (a[right]

swap(a[right], a[center]);

swap(a[center], a[right – 1]);

...

Eлементите a[left], a[center] и a[right] се сортират на място. Така най-малкият елемент ще бъде поставен в a[left], най-големият – в a[right], а медианата в a[center]. Поставяме разделящият елемент в a[right – 1] и инициализираме i с left+1, а j с right-2. Тъй като елементът a[left] е по-малък от разделящия, то ще изпълнява ролята на ограничител за j. Така j няма да излиза извън границите на масива. Тъй като i ще спре на елемент равен на разделящия, поставянето на разделящия елемент в a[right-1] осигурява ограничител за i.

Kодът по-долу представя програмната реализация на бързата сортировка.
void quicksort(a, int left, int right)

{

if (left + 10 <= right)

{

int i = left, j = right – 1;

for( ; ; )

{

while(a[++i] < pivot) {}

while(pivot < a[--j]) {}

if (i < j)

swap(a[i], a[j]);

else

break;

}

swap(a[i], a[right – 1]);

quicksort(a, left, i – 1);

quicksort(a, i + 1, right);

}

else

insertionSort(a, left, right);

}

Кодът по-горе включва разделяне на масива и рекурсивни извиквания. Двата цикъла while показват защо бързата сортировка е толкова бърза. Вътрешния цикъл for извършва инкрементиране респективно декрементиране, проверка и размяна.

Вътрешния цикъл for би могъл да се замени със следния:
int i = left + 1, j = right – 2;

for( ; ; )

{

while(a[i] < pivot) i++;

while(pivot < a[j]) j--;

if (i < j)

swap(a[i], a[j]);

else

break;

}

Този код няма да работи, тъй като при a[i] = a[j] = pivot ще се влезе в безкраен цикъл.

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

При N=1 времето за сортиране е константа:

T(0) = T(1) = 1

Времето за изпълнение на бързата сортировка е равно на сумата от времето за изпълнение на две рекурсивни извиквания и времето за разделяне на масива, което е линейно. Времето за избиране на разделящ елемент е константа. Следователнп базовото уравнение за бързата сортировка е:

T(N) = T(i) + T(N – i – 1) + cN, където (1.1)

е броя на елементите в S₁.
Ще разгледаме три случая.

Разделящият елемент е най-малкият елемент през цялото време. Тогава i = 0 и ако игнорираме Т(0) = 1, което е пренебрежимо малко, получаваме:
T(N) = T(N – 1) + cN, N>1 (1.2)

T(N – 1) = T(N – 2) + c(N – 1) (1.3)

T(N – 2) = T(N – 3) + c(N – 2) (1.4)

...

T(2) = T(1) + c(2) (1.5)
Сумираме левите и десните страни на горните равенства и получаваме:

(1.6)

В найдобрия случай разделящият елемент е в средата. За да опростим математическите преобразувания, ще предположим, че двата подмасива са абсолютно еднакви по размер, т.е. имат размер равен на половината от размера на оригиналния масив.
T(N) = 2T(N/2) + cN (1.7)
Разделяме двете страни на горното равенство на N:

(1.8)

(1.9)

(1.10)

…

(1.11)

Сумираме левите и десните страни на равенствата от (1,7) до (1.11) и получаваме:

, т.е. (1.12)
T(N) = cNlogN + N = O(NlogN) (1.13)

Първоначална подредба

Предполагаме, че масивът S₁ има винаги един и същ размер, който е с вероятност 1/N. Следователно средната стойност на T(i), а оттук и на T(N – i – 1) ще бъде:

(1.14)

Заместваме в уравнение (1.1) и получаваме:

(1.15)
Умножаваме двете страни на равенството на N и получаваме:

(1.16)
За да опростим уравнението трябва да премахнем сумата от него:

(1.17)
Разделяме уравнение (1.17) на уравнение (1.16) и получаваме:
NT(N) – (N – 1)T(N – 1) = 2T(N – 1) + 2cN – c (1.18)
Игнорираме c от дясната страна и преобразуваме уравнението:
NT(N)= (N + 1)T(N – 1) + 2cN (1.19)
Сега притежаваме формула за T(N) във функция на T(N – 1). Разделяме уравнение (1.19) на N(N + 1):

(1.20)

(1.21)

(1.22)

…

(1.23)

Сумираме левите и десните страни на уравненията от (1.20) до (1.23):

Заместваме сумата с:

, където γ ≈ 0.577 представлява константа на Euler
Следователно:

, т.е.
T(N) = O(NlogN)

Каталог: IT%201%20kurs%20Podgotv -> 1%20sem -> SAA
SAA -> Конспект Синтез и анализ на алгоритми и програми

Изтегляне 359.1 Kb.

Сподели с приятели: