Algoritam spajanja — разлика између измена
Садржај обрисан Садржај додат
Нова страница: {{МАТФ052013}} '''Algoritmi spajanja''' su grupe algoritama koji rade sekvencijalno sa više sortiranih nizova i obično proizvode više sortiranih nizova kao izl… |
м Bot: formatiranje referenci; козметичке измене |
||
Ред 7:
Sve dok neki od pokazivača p<sub>0..n</sub> pokazuje na podatke u nizovima L<sub>0..n</sub>:
# uradi nešto sa podacima
# pronađi koji od pokazivača pokazuje na najmanji element; preusmeri pokazivač na sledeći element
== Analiza ==
Za rad ovih algoritama obično je potrebno vreme proporcionalno sumi dužina nizova. Oni algoritmi koji istovremeno rade sa velikim brojem nizova množe sumu dužina nizova sa vremenom da bi pronašli pokazivač na najmanji element, što se može postići pomoću reda sa prioritetom koji je baziran na hipu za [[Big O notation|O]](log ''n'') vremena, za O(''m'' log ''n'') vremena, gde je ''n'' broj nizova koji se spajaju a ''m'' je suma dužina nizova. Kada se spajaju dva niza dužine ''m'', donja granica poređenja u najgorem slučaju je 2''m'' − 1.
Klasično spajanje (koje se koristi u sortiranju spajanjem) kao izlaz vraća najmanji element; ako na ulazu ima sortirane nizove, kao izlaz vraća sortirani niz koji sadrži sortirane elemente bilo kog niza sa ulaza, i to čini u vremenu proporcionalnom sumi dužina nizova sa ulaza.
== Jezička podrška ==
Standardna [[C++]] biblioteka sadrži funkciju <code>std::merge</code>, koja spaja dva sortirana niza i <code>std::inplace_merge</code>, koja spaja dva uzastopno sortirana niza ''u mestu''. Klasa <code>std::list</code> ima svoj metod <code>merge()</code> koji sebi pripaja drugu listu. Tipovi spojenih elemenata moraju da sadrže operator manje (<) ili se mora obezbediti proizvoljan komparator.
Standardna [[Python]] biblioteka (od verzije 2.6) takođe ima funkciju <code>merge()</code> u <code>heapq</code> modulu, koja uzima više sortiranih nizova i spaja ih u jedan.<ref>[http://docs.python.org/library/heapq.html#heapq.merge 8.4. heapq — Heap queue algorithm — Python v2.7.5 documentation<!-- Bot generated title -->]</ref>
== Paralelno spajanje ==
Kod multiprogramiranja, nizovi sortiranih vrednosti se mogu efikasno spojiti pomoću problema svih najbližih najmanjih vrednosti.<ref>{{citation |first1=Omer |last1=Berkman |first2=Baruch |last2=Schieber |first3=Uzi |last3=Vishkin |author3-link=Uzi Vishkin |title=Optimal double logarithmic parallel algorithms based on finding all nearest smaller values |journal=Journal of Algorithms |volume=14 |pages=344–370 |year=1993 |issue=3 |doi=10.1006/jagm.1993.1018}}</ref>
Ред 30:
== Reference ==
* [[Donald Knuth]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 158–160 of section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging, pp. 197–207.
* {{Citation |first1=Thomas |last1=Cormen |authorlink1=Thomas H. Cormen |first2=Charles |last2=Leiserson |authorlink2=Charles E. Leiserson |first3=Ronald |last3=Rivest |authorlink3=Ronald L. Rivest |first4=Clifford |last4=Stein |authorlink4=Clifford Stein |title=[[Introduction to Algorithms]] |edition=Third Edition |publisher=MIT Press and McGraw-Hill |year=2009 |isbn=978-0-262-03384-8 |chapter=Section 27.3: Multithreaded merge sort |pages=797–804 }}
{{reflist}}
| |||