Алгоритам за сортирање у месту
У компјутерској технологији, алгоритам за сортирање у месту је алгоритам који трансформише улаз користећи структуру података са малом,константном количином додатног простора.Улаз је најчешће замењен излазом како се алгоритам извршава.Алгоритам који не сортира у месту понекад се зове изван места или не у месту.
Алгоритам се понекад, неформално, зове у месту док год врши замену улаза излазом.У стварности, ово није довољно , нити је потребно; излазни простор може бити константан, или не мора чак ни да се узима у обзир, на пример ако се излаз исписује на ток.Са друге стране, понекад може бити практично да се узме у обзир излазни простор како би се одредило да ли је алгоритам у месту, као што је у првом примеру испод; ово отежава да стриктно дефинишемо алгоритме у месту.У теоријској примени, као што је смањење лог простора, типично је да ес увек игнорише излазни простор(у оваквим случајевима је од веће вазности да је излаз само за писање).
Примери уреди
Дат је низ а до н елемената, претпоставимо да хоћемо низ који садржи исте елементе у обрнутом редоследу и да хоћемо да се ослободимо првобитног низа.Један, како се чини, једноставан начин да се ово уради је да се креира нови низ једнаке величине, напуни копијама елемената првобитног низа у одређеном редоследу, и да се избрише првобитни низ.
function reverse(a[0..n - 1])
allocate b[0..n - 1]
for i from 0 to n - 1
b[n − 1 − i] := a[i]
return b
Нажалост ово захтева О(н) додатног простора како би смо имали низове а и б доступне истовремено.Такође алокација и деалокација су често споре операције.Пошто нам висе не треба низ а, можемо да га заменимо са његовим елементима, поређаним у супротном поредку, користећи овај алгоритам у месту коме ће само требати константан додатни простор за помоћне променљиве и и тмп, без обзира на величину низа.
function reverse_in_place(a[0..n])
for i from 0 to floor(n/2)
tmp := a[i]
a[i] := a[n − 1 − i]
a[n − 1 − i] := tmp
Постоји велики број алгоритама за сортирање, који могу да преуреде низ у сортираном редоследу, без коришћења додатног низа.У те алгоритме спадају: Мехур сортирање,Чешаљ сортирање,сортирање Селекцијом,сортирање Уметањем, Хип сортирање,Шкољка сортирање.
Брзо сортирање сортира податке у месту , како увек врши замену само два елемента низа.Међутим, већина имплементација захтева О(лог н) простора како би водило евиденцију о рекурзивним позивима функције као део подели и владај стратегије; па Брзо сортирање није алгоритам који сортира у месту.
Већина алгоритама који сортирају селекцијом су такође у месту, мада неки знатно преуређују улазни низ у процесу проналажења коначног резултата константне величине.
Неки алгоритми за обраду текста, као сто су трим и реверсе могу бити урађени у месту.
уреди
У теорији израчунавања сложености, алгоритми у месту укључују све алгоритме са О(1) просторном сложеношћу, класе ДСПАЦЕ(1).Ова класа је веома ограничена; једнака је регуларним језицима.Заправо, не укључује примере наведене изнад.
Због овог разлога, узимамо у обзир алгоритме у L класи, класа проблема која захтева О(лог н) додатног простора, да би били у месту.Иако ово изгледа супротно нашој ранијој дефиницији, морамо узети у обзир да у апстрактном свеу наш улаз може бити произвољно велик.На правом рачунару, показивач захтева малу, фиксну количину простора, јер је количина физичке меморије ограничена, али генерално О(лог н) битова је потребно да се одреди индекс у листи величине н.
Да ли ово значи да је брзо сортирање алгоритам који ради у месту? Нимално – технички, захтева О(лог2 н) простора, пошто свако од О(лог н) стек оквира садржи константан број показивача(свако величине О(лог н)).
Одређивање алгоритама у месту, који припадају класи L, има веома занимљиве последице; на пример, то значи да постоји алгоритам у месту(прилично сложен) помоћу којег мозе да се утврди да ли постоји путања између два чвора у неусмереном графу, проблем који захтева О(н) додатног простора користећи стандардне алгоритме као сто је што је алгоритам за претрагу графа у дубину.Ово заузврат даје алгоритме у месту за проблеме као што су одређивање да ли је граф бипартитиван или тестирање да ли два графа имају исти број компоненти.Погледајте СЛ за више информација.
Улога насумичности уреди
У доста случајева, простор потребан за алгоритам може драстично бити смањен корстићи алгоритам за рандомизацију.На пример,рецимо да хоћемо да знамо да ли су два темена у графу, од н темена, у истој повезаној компоненти графа.Нема једноставног, детерминистичког, у месту алгоритма да се ово одреди, али ако почнемо од једног темена и вршимо случајну шетњу од око 20*н3 корака, шанса да ћемо да наиђемо на темен, под претпоставком да је у истој компоненти, је веома велика.Слично, постоје једноставни алгоритми у месту који користе рандомизацију за просто теситрање, као што је Миллер-Рабин прост тест,а ту су I једноставни алгоритми у месту који користе насумично факторисање, као што је Поллард'с рхо алгоритхм.Погледајте РЛ I БПЛ за дискусију овог феномена.
У функционалном програмирању уреди
Језици функционалног програмирања често обесхрабрују или не подржавају алгоритме у место које преписују преко података, јер је ово тип споредног ефекта; уместо тога, они само дозвољавају да се нови подаци изграде.Међутим, добри компајлери функционалних језика често ће препознати када је објекат сличан постојећем креиран I онда се стари одбацује, I онда ће оптимизовати ово у једноставну мутацију “испод-хаубе”.
Приметити да је могуће ,у принципу ,да се пажљиво конструише алгоритам у месту које не мења податке(осим ако се подаци више не користе), али ово је ретко рађено у пракси.Погледајте чисто функционалне структуре података.