1. Основни понятия. Варианти на алгоритми. Влияние върху производителността. Въведение в анализа Алгоритъм

void selection (Item a[], int l, int r)

{ int i, j;

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

{ int min = i;

for (j = i+l; j <= r; j++)

if (less(a[j], a[min])) min = j;

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

}}

Вътр. цикъл представлява само сравнение, за да провери текущия елем. с намер. наи малък. Вънщният цик. разменя елем. Броят на размените е N -1. Времето на изпълн. се доминира от бр. на размен. Този брой е пропорц на N квадр.Недостатък на сорт. е че вр. за изпълн зависи съвсем малко от вече подредените елем. Методът е добър за сортир. на фаилове с огромни елем. и малки ключове.

Този метод работи по сл. начин: елем. се разглеждат един по един вмъкв. всеки от тях на подходящ. място. сред вече сортир.(запазваики ги по този начин сортирани). Необходимо е да се направи място за вмъквания елем., като преместв. по – гол. елем с 1 поз надясно и после вмъкв. елем. във вакантната. поз.

void insertion(Item a[], int l, int r)

{ int i;

for (i = r; i >l; i--) compexch (a[i-1], a[i]);

for (i = l+2; l<=r; i++)

{ int j = i; Item v = a[i];

while (less(v, a[j-1]))

{ a[j] = a[j-1]; j--; )

a[j]= v; }}

Програмата първо поставя най – малкият елем.на мас. на 1 –ва поз. , така че този елем. да служи като ограничител. Във бтр цикъл тя прави просто присвояване в место размяна. Прогр. завърщ. втр. цикъл., корато вмъкв. елем. е в същата позиция. За всяко i тя сортира елем. a[i]…..a[i-1], които са по – гол. от а[i], след което поставя a[i] в подходяща позиция.

Преминава се през файла като разменяме съседните елем. които не са подредени,. Деиствието продължава докато фаила не се сортира. Главн. предимство на тази сорт. е лесното и реализиране. Но тя е по – бавна от селективната сорт. и сорт. чрез вмъкване.

Сортировк се извърщва на N паса.

Пример с числа.



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

void bubble (Item a[], int l, int r)

{ int i, j;

for (i = l; i

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

comexch(a[j-1], a[j]);

}

За всяко i от l до r-1 вътр. цикъл намира мин елем. сред елем a[i],…, a[r] чрез преминаване през тях от дясно на ляво, сравнявайки и евентуално разменяики последоват елем. и така го поставя в поз. a[i]. Най – малкият елем. минава през всички – така тои изплува като мехурче в началото на масива.

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

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

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

Деф. Инверсия е дв. ключове, които не са в необходим ред в файла.

Св. Сорт. чрез вмъкване и по метода на мехурчето изискват линеен брои сравнения и размени за фаилове с най – мн. константен. брой инверсии, съответни на всеки елемент.

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

Сорт. на Шел е разшир на селект. сорт, к-то печели скорост, като позволява. размяна на елем, далеч един от др. Идеята е да пренаред. фаил, за да му дад св., че вземаики всеки h елем.(като започнем от някъде), пораждаме сортиран фаил. Такъв фаил се казва че е h сортиран. h сорт. фаил представлява h независ сорт фаилове. поставени последов.

Пример: В сл. стъпката е N/2 = 4; След 1 -вата. итерация пак. сорт. с стъпка 2. и после с стъпка 1.



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

void shellsort (Item a[], int l, int n)

{ int i, j, h;

for ( h =1; h<=(r-l)/9; h = 3*h+1);

for (; h>0;h /=3)

for (i = l+h); i <=r; i++)

{ int j = i; Item v = a[i];

while (j > = l+h) && less(v, a[j - h]))

{ a[j] = a[j-h]; j -=h;}

a[j] = v;

Използват се ограничители и после се заменя всяко срещане на l с h в сортиров. чрез вмъкване, прог. прави h сорт. на фаил.

Един от наи сложните въпроси при Шел сортировката е каква редица на нарастване да се използва. В п-ката обикнов.се използ. редици, които намал. геометрично

Св: Резултата от h – сортир на фаил, к-то е k - нареден, е фаил, к-то e и h и k нареден.

Св: Сортировката на Шел прави по – малк от 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 и повече пъти.

Сортир. на Шел работи приемливо добре в/у разнообразие от типове файлове, а не само в/у файлове от случайни числа

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

22 . Сортиране на свързани списъци. Индексно и указателно сортиране.

Свързаните списъци са едни от осн.н-ни за структуриране на данни.След.прог.дава ин-терфейс за тип данни за свърз.списък(изпо-лзваме Item за тип данни на елем.Ф-ята init изгражда списъка,вкл.задел.на необх.па-мет.Ф-ята show отпеч.ключовете в списъ-ка.Прог.за сорт.използ.less,за да сравн.елем и манипул.указ.,за да пренарежд.елем.)

typedef struct node = link;

struct node { Item item; link next; };

link NEW ( Item, link);

link init (int);

void show (link);

link sort (link);

Мд се адаптира селект.сорт.или сорт.по ме-тода на мех.или вмък.за реализ.на свърз. списъци.Селект.сорт.е проста:поддържаме вход.списък(първонач.съд.данн)и изх.спи-сък(събира сорт.резулт.)и просто четем 2-я списък,за да намерим max елем.,махаме го от вход.списък и го добавяме към нач.на изх.списък.

1 стъпка от селект.сорт на свързан списък.

link listselection(link h)

{ link max, t, out = NULL;

while (h ->next !=NULL)

{ max = findmax(h);

t = max -> next; max ->next = t->next;

t-> next = out; out = t; }

h->next = out

return (h);

Поддържа се вх. списък( сочен от h->next) и изходен списък (сочен от Out).

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

# include

# include

# include

# include “Item.h”

static char buf [100000];

static int cnt = 0;

int ITEM scan (char **x)

{ int t;

t = scanf (“%s”, *x); cnt+ = strlen (*x)

return t; }

void ITEMshow (char *x)

{ printf (“%s”, x); }

1 прост подход за сорт.без мест.на елем.е да поддържаме индексен масив с ключове-те в елем.,достъпни само за сравн.Нека сорт.елем. са в масива data[0],…,data[N-1] и не искаме да ги местим.За да постигнем ефекта на сорт.,използ.втори масив а от ин-дексите на елем.Започ.с иниц.на a[i]=i, за i=0,…,N-1.Целта на сорт.е да пренаредим индекс.масив а,така че а[0] да дава индекса на елем.данни с най-малък ключ,и т.н.Така манипулираме индексите вместо записите.

Др.възмож.е да използ.указатели,т.е.реализ указателна сорт.За сорт.на масив от елем. указ.сорт.е на индексната но с адресите на масива,добавени към вс.индекс.Указ. сорт обаче е по-обща,защото указ.мд сочат навсякъде,а сорт.елем.не е необх.да са фик-сирани по размер.Ако а е масив от указ. към ключове,тогава викането на сорт.ф-я ще доведе до това,че указ.ще се пренаредят така че ако се обръщаме към тях последов., ще достигнем до ключовете в сорт.ред. Ре-ализ.сравн.като следваме указ.,а размените релиз.чрез размяна на указ.

Глав.причина да използ.индекси или указ. е да избегнем вмешателство в сорт.данни. Мд сорт.файл даже ако всичко което имаме е достъп до него само за четене.Даже с ня-колко масива от индекси или указ.мд сорт. 1 файл по няколко ключа.

работят поетапно. На всеки етап се взима изглеждащото за най-добро решение, независимо от последиците. Т.е.локален оптимум. Или стратегията е “take what you can get now”.В края на алг.приемаме, че ло-кал.съвпада с глобал.оптимум. Пр.за това е стратегията на връщане на монети: връща на всеки етап монета с мак. възможна ст-ст

Този алгоритъм не работи във всички монетарни системи. Друг пример: авт. трафик.

имаме дадени задачи j1 …jN с времена на изпълнение t1…tN и 1 процесор. Искаме разпределяне с цел мин. средно време на завъшване на задача (т.е. на коя мин. средно завършва задача). (няма прекъсване на задача).

Първата завършва след 15, втората след 23, третата след 26, след 36 à общо 100 мин/4 = 25 средно ще завършва задача.

Друга подредба е показана по-долу:ср.време 17.75

Стратегията е най-късата задача – най-напред(тя участва най-много във формиране времената на следв.зад).

I член не зависи от подредбата, а само втория (“к”).

задача време

едно решение (започваме с къси задачи и циклим по процесори):

Общо време на завършване 165. Средно 165/9 = 18.33. Друга стратегия (когато Р дели N точно) е: за всеки 0 <= I < N/P поставяме последоват. следващите Р задачи на различен процесор.

минимизация на крайното време на завършване на всички задачи по-горе това е 40 или 38. Ето подредба с t = 34:

10 –a; 15 e; 12 I; 3 s; 4 t; 13 blanks; 1 ML. Нужни са 174 бита за съхраняване на поредицата

ната на кода за разл символи. Най-честите à с най-къс код.При едн. честота – няма значение кой.Ето дърво, даващо н-н за кодировка на азбука от 7 символа:

Данни има само в листата.Кодировката е еднозначна

Общата цена става 173, което изобщо не е подобрение.

първо обединение ( няма значение кое е ляво, така че реализиращата процедура няма да прави връщания назад). Теглото на новополученото д-во е сума:

Реализацията в прог. е лесна: правим нов възел,устано-вяваме 2 указателя и изчисл. тегло.продължаваме:

краят ( след обединението) беше вече показан

Накратко за доказателството, че Хофмановия алгоритъм води до оптимален код:
1. полученото д-во е пълно, така че не може да се подобрява с местене възли нагоре.
2. 2 букви “а, б” с мин. честота са най-долу. Доказваме с използване на обратно твърдение: ако това не е така , (поне едното от а и б не е в най-дълбоко листо), то има някакво г (дървото е пълно) което е там. Но щом а е по-рядко срещано от г, то най-лесно ще подобрим общата цена като разменим а и г .
3. Очевидно, 2 символа във възли с еднаква дълбочина могат да се разместват без променяне на оптималния избор. Отчитаме, че може да сливаме символ – дърво с слято вече. Тогава очевидно азбуката ни се е проме-нила (напр. е,Т4,Т3). Но крайните символи изгражда-щи напр Т3 са по-дълбоко,но и по-рядко срещани от е.
Алг.е greedy,защото на всеки етап правим сливане без оглед на глобал.оптимиз., а само в локален оптимум.
**Разбира се кодиращата инф.следва да се изпрати в началото на файла при трансмисия за да е възможно декодиране.За малки файлове това е лошо(много добавена инф.).
***Алгоритъмът е двупасов – първо се събират данни за честотата, после се кодира. За големи файлове това не е добре – има подходи за обединяване задачите.

30.Проблемът пакетиране.Метод FirstFit
Тези алгоритми са бързи, но не винаги дават оптимално решение. Имаме N пакета с размери s1….s N (0 <= s i <1). Искаме да ги пакетираме в min брой торби, като всяка торба има обем 1. Ето пример:

Съществуват 2 версии на решения:on-line всяка единица се поставя преди следваща (няма връщане назад). Off-line – първо изследваме всички, тогава започваме пакетирване.

Тъй като се сканират предходните торби, à О(N ). Може да се сведе до O(N log N) – ако сканираме както при бинар. търсене.

Елемент с тегло 0.3 е поставен в В3, а не в В2. Има подобрение, но не и за лошите поредици.