Միաձուլման տեսակավորում

Միաձուլման տեսակավորում O(n log n), համեմատման վրա հիմնված տեսակավորման ալգորիթմ է։ Կատարման մեծ մասն արտադրում է ստաբիլ տեսակավորում, որը նշանակում է, որ կատարումը պաշտպանում է մուտքի հրամանը տեսակավորված ելքի հավասար էլեմենտներից։ Դա անջատ և նվաճված ալգորիթմ է։ Միաձուլումը հայտնաբերվել է 1945 թ.-ին Ջոն վոն Նյումանի կողմիցGoldstine:

Միաձուլման տեսակավորում
Տեսակ	համեմատություններով դասակարգում և կայուն տեսակավորման ալգորիթմ
Դաս	տեսակավորման ալգորիթմ
Տվյալների կառուցվածք	$O(n)$
Վատագույն դեպքում կատարումը	$O(n\log n)$
Լավագույն դեպքում կատարումը	$O(n\log n)$
Օգտագործում է	զանգված և merge algorithm?
Հայտնաբերող	Ջոն ֆոն Նեյման

Ալգորիթմ

Միաձուլման տեսակավորման օրինակ։ Առաջին հերթին բաժանել էջը փոքրագույն մասնիկների, ապա համեմատել յուրաքանչյուր մասնիկ հարակից էջի հետ՝ տեսակավորելու և միավորելու երկու հարակից էջերը։ Արդյունքում բոլոր մասնիկները տեսակավորվում և միավորվում են իրար։ Միաձուլումը տեղի է ունենում հետևյալ կերպ՝ 1. Եթե էջի լայնությունը 0 – ից 1 է, այն արդեն տեսակավորված է 2. Բաժանել չտեսակավորված էջը 2 ենթաէջերի՝ կես էջի չափով 3. Տեսակավորել յուրաքանչյուր ենթաէջը ռեկուրսիվ եղանակով առաջարկելով միաձուլում 4. Վերամիավորել 2 ենթաէջերը 1 տեսակավորված էջերի մեջ։

Միաձուլումը կազմի մեջ է մտցնում 2 հիմնական գաղափարները՝ արդարացնելու իր աշխատաժամանակը։ 1. Փոքր էջն ավելի քիչ քայլեր կպահանջի միաձուլման համար, քան մեծ էջը։ 2. Քիչ քայլերը նախատեսված են կառուցելու տեսակավորված էջ 2 տեսակավորված և 2 չտեսակավորված էջերից։ Օրինակ միայն պետք է հատել յուրաքանչյուր էջը մի անգամ, եթե դրանք արդեն տեսակավորված են։ Կիրառենք միաձուլումը տեսակավորելու integer –ների էջ, որը պարունակվում է զանգվածում։ Կիրառենք միաձուլումը տեսակավորելու integer – ների էջ։

Ենթադրենք ունենք A զանգված n ինդեքսով, որը դասավորված է A0 – ից An-1։ Մենք առաջարկում ենք միաձուլումը A (A0 ... Ac-1 ) և A (Ac... An-1), որտեղ c – ն n/ 2 – ի integer մասն է։ Երբ 2 կեսերը վերադարձվում են, դրանք պետք է տեսակավորվեն։ Դրանք այժմ կարող են միաձուլվել միմյանց հետ՝ կազմելով տեսակավորված զանգված։ $An-1_{0}$ to $A_{n-1}$.

Հասարակ pseudocode ձևում ալգորիտմը կարող է ունենալ հետևյալ տեսքը՝

function merge_sort(m)

if length(m) ≤ 1
return m
var list left, right, result
var integer middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result

merge Ֆունկցիան պահանջում է և աջ և ձախ էջերի միաձուլում։ Այն ունի հետևյալ վարիացիաները՝

function merge(left, right)
var list result
while length(left) > 0 or length(right) > 0
if length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
else if length(left) > 0
append first(left) to result
left = rest(left)
else if length(right) > 0
append first(right) to result
right = rest(right)
end while
return result

Վերլուծություն

Կրկնվող միաձուլման ալգորիտմը սովորաբար տեսակավորում է 7 ինթեջեր արժողությամբ զանգված։ Միաձուլումն իրականացնելու համար պետք է հետևել հետևյալ քայլերին։

Տեսակավորման n միաձուլվող օբյեկտներն ունեն O(n log n ) – ի ներկայացման միջին և վատագույն դեպքեր։ Եթե n լայնության էջի միաձուլման ժամանակը T( n) է, T(n) = 2T(n/2) + n, որը հետևում է ալգորիթմի որոշիչին(առաջարկել սովորական էջի կեսի չափով 2էջի ալգորիթմ և ավելացնել n քայլեր, որոնք վերցված են միաձուլելու արդյունքային 2 էջերը )։ Փակ ձևը հետևում է վարպետ թեորեմից։ Տեսակավորման n միաձուլվող օբյեկտներն ունեն O(n log n ) – ի ներկայացման միջին և վատագույն դեպքեր։ Եթե n լայնության էջի միաձուլման ժամանակը T( n) է վատագույն դեպքի ներկայացում։ Վատագույն դեպքում ձեռնարկությունների թվի միաձուլումը հավասար կամ փոքր է ( n ⌈lg n⌉⌉ - 2⌈ lg n⌉+ 1), որը (n lg n- n + 1) - ի և (n lg n + n + O(lg n)) – ի միջև է։ Մեծ n- ի և հազվադեպ կարառվող մուտքի էջի համար միաձուլման ենթադրվող միջին համեմատության թիվը ավելի քիչ է մոտեցնում a n, քան վատագույն դեպքում։

Վատագույն դեպքում միաձուլումը կատարում է 39% պակաս համեմատություն, քան արագ տեսակավորումը կատարում է միջինի դեպքում։ Սակայն կան հատուկ դեպքեր, երբ նրանք սահմանափակ են, որտեղ միաձուլման վատագույն դեպքը միաժամանակ է ընթանում տեսակավորման լավագույն դեպքի հետ։ Շարժման պայմաններում միաձուլման վատագույն դեպքի բաղադրությունը՝ O(n lg n) – ը նույնն է, ինչ որ արագ տեսակավորման դեպքում, և լավագույն դեպքը խլում է կեսը, ինչպես շատ կրկնություններ վատագույն դեպքում։ Միաձուլման ռեկուրսիվ կատարումը ստիպում է 2n- 1 մեթոդը վատագույն դեպքում համեմատել արագ տեսակավորման n – ի հետ, չնայած միաձուլումն ունի մոտավորապես 2 անգամ ավել ռեկուրսիվ ավելցուկ, քան արագ տեսակավորումը։ Այնուամենայնիվ, միաձուլման կրկնվող ոչ ռեկուրսիվ կատարումները, խուսափելով ավելցուկ կոչվող մեթոդից, դժվար չէ կոդավորել։ Միաձուլման ամենատարածված կատարումը չի տեսակավորվում տեղում, դրա համար մուտքի հիշողության ծավալը պետք է առանձնացված լինի տեսակավորված ելքի տեսակավորման համար։

Միաձուլումը, ինչպես նշված է, նույնպես ունի հաճախակի վերահսկողություն, պրակտիկորեն կարևոր է լավագույն դեպքի հատկությունը։ Եթե մուտքն արդեն տեսակավորված է, դրա բարդությունն ընկնում է մինչև O(n)։ Մասնավորապես, n-1 համեմատությունները և 0 շարժումները ներկայացված են, որը նույնն է, ինչ հասարակ անցումը մուտքով, ստուգելով, արդյոք այն վերատեսակավորված է։ Տեղում տեսակավորումը հնարավոր է (օգտագործելով էջերը զանդվածների փոխարեն), բայց շատ դժվար և պրակտիկայում առաջարկում է փոքր ներկայացման ձեռքբերված նույնիսկ եթե ալգորիթմը տևում է O(n log n) ժամ։ Տվյալ դեպքերում ալգորիթմները կուտակված տեսակավորման նման հաճախ առաջարկում են համեմատական արագություն, և պակաս կոմպլեքս են։ Պայմանականորեն, չնայած ստանդարտ միաձուլման, տեղում կատարվող միաձուլումը ստաբիլ տեսակի չէ։ Հղված էջերի դեպքում ալգորիթմը չի օգտագործում ավել տարածք, քան արդեն էջերի ներկայացման ժամանակ օգտագործված տարածքը, բայց O(log(k)) օգտագործվում է ռեկուրսիվ հետքի ժամանակ։

Միաձուլումն ավելի արդյունավետ է, քան արագ տեսակավորումը որոշ էջերի համար, եթե տեսակավորվող ամսաթիվը կարող է լինել միայն արդյունավետորեն թույլատրված հերթականությամբ և հայտնի Lisp –ի նման լեզուներում, որտեղ հերթականությամբ թույլատրված թվային ստրուկտուրաները շատ նման են։ Ի տարբերություն արագ տեսակավորման որոշ( արդյունավետ ) կատարումների, միաձուլումը ստաբիլ տեսակավորում է այնքան ժամանակ, քանի դեռ միաձուլման օպերացիան ճիշտ է կատարված։ Միաձուլումը նույնպես ունի որոշ պայմաններ։ Դրանցից մեկը նրա 2n դիրքի օգտագործումն է, պայմանական n դիրքերն անհրաժեշտ են, քանի որ հնարավոր չէ տեղում տրամաբանորեն կապել 2 տեսակավորված խմբեր։ Բայց չնայած այս տարածքի օգտագործման ալգորիթմը դեռևս շատ աշխատանք է անում։ m – ի պարունակությունը առաջին անգամ պատճենվել է միաձուլման յուրաքանչյուր փուլի արդյունքային էջի ձախ կամ աջ մասում։ Այդ պատճենման ալտերնատիվն ինֆորմացիայի նոր դաշտը բանալու հետ ասոցիացնելն է (m – ի էլեմենտները կոչվում են բանալիներ)։ Այս դաշտը կօգտագործվի բանալիները և յուրաքանչյուր կապված ինֆորմացիա իրար հետ կապելու տեսակավորված էջում (բանալին և նրա վերաբերյալ ինֆորմացիան կոչվում է գրառում)։ Այնուհետև տեսակավորված էջերի միաձուլումը կատարվում է կապի արժեքները փոփոխելով։ Ոչ մի գրառում կարիք չկա տեղաշարժել։ Դաշտը, որը պարունակում է միայն կապ, հիմնականում փոքր կլինի լիարժեք գրառումից, հետևաբար քիչ տարածք կօգտագործվի։ Տարածքի n/2- ից մեկ այլ ալտերնատիվ է դիտարկել աջը և ձախը որպես միասնական ստրուկտուրա, պատճենել m -ի միայն ձախ մասը ժամանակավոր տարածքում և ուղեկցել միաձուլման սահմանված կարգը, տեղադրել միաձուլված արտադրանքը m -ի մեջ։ Ավելի լավ է առանձնացնել ժամանակավոր տարածքը միաձուլված սահմանված կարգից դուրս այնպես, որ անհրաժեշտ լինի միայն մեկ առանձնացում։ Չափից ավելի պատճենումը, որը պահպանվել է նախորդ պարագրաֆում, նույնպես գործում է, քանի դեռ տողերի վերջին զույգը՝ մինչ ետադարձ արդյունքի պնդումը, չի դարձել գերծավալուն։

Օգտագործումը չափերիզների կրիչների հետ

Արտաքին միաձուլումը պրակտիկ է ժապավենի շարժակներն օգտագործել որպես մուտքային և ելքային սարքեր։ Այն ունի փոքր հիշողության ծավալ և դա կախված չէ գրառումների թվից։

Այդ նույն պատճառով այն օգտակար է սկավառակի վրա ինֆորմացիայի տեսակավորման համար, որը շատ մեծ է հիմնական հիշողությունում պահելու համար։ Եթե ունենք 4 ժապավենի շարժիչներ, դրանք աշխատում են հետևյալ կերպ՝ 1. Կիսել հատվածը և դնել 2 ժապավենների մեջ։ 2. Միավորել 2 ժապավենների գրառումների յուրահատուկ մասերը, գրել 2 առանձին գրառում արտադրվող 2 ժապավենների համար։ 3. Միավորել 2 արտադրված ժապավենների գրառումները և գրել դրանք օրիգինալ 2 մուտքային ժապավեններին։ 4. Կրկնել, մինչև ստանաք մեկ քայլ, որը կպարունակի ամբողջ ժամանակահատվածը, կտարբերակի, որ log n-ն անցել է, որտեղ n-ը գրառումների թիվն է։

Ժապավենների վրա արդեն տեսակավորված ժամանակահատվածի համար տարածված է բնական միաձուլում տարբերակը։ Վատագույն դեպքում այն արտացոլում է այն, ինչ ներսում է, այն միավորում է առանձնահատուկ գրառումները 2 գրառումների ցուցակի մեջ, այնուհետև 2-ը՝ 4- ի մեջ, և այլն։ Լավագույն դեպքում այն միավորում է լայնածավալ, արդեն տեսակավորված ցուցակներն ավելի ծավալուն ցուցակների մեջ, հուսալիորեն ավարտելով ավելի քիչ ժամանակում, քան log n- ն է անցնում։ Պարզագույն pseudocode ձևում բնական միաձուլման տեսակավորման ալգորիթմն ունի հետևյալ տեսքը՝

# Original data is on the input tape; the other tapes are blank
function merge_sort(input_tape, output_tape, scratch_tape_C, scratch_tape_D)
while any records remain on the input_tape
while any records remain on the input_tape
merge( input_tape, output_tape, scratch_tape_C)
merge( input_tape, output_tape, scratch_tape_D)
while any records remain on C or D
merge( scratch_tape_C, scratch_tape_D, output_tape)
merge( scratch_tape_C, scratch_tape_D, input_tape)

# take the next sorted run from the input tapes, and merge into the single given output_tape.
# tapes are scanned linearly.
# tape[next] gives the record currently under the read head of that tape.
# tape[current] gives the record previously under the read head of that tape.
# (Generally both tape[current] and tape[previous] are buffered in RAM ...)
function merge(left[], right[], output_tape[])
do
if left[current] ≤ right[current]
append left[current] to output_tape
read next record from left tape
else
append right[current] to output_tape
read next record from right tape
while left[current] < left[next] and right[current] < right[next]
if left[current] < left[next]
append current_left_record to output_tape
if right[current] < right[next]
append current_right_record to output_tape
return

Օպտիմալացվող միաձուլման տեսակավորում

Ժամանակակից համակարգիչներում առնչության լոկալացումը կարող է հսկայական կարևորություն ունենալ թեթև արդյունաբերության մեջ, քանի որ օգտագործվում են հիերարխիկ հիշողություններ։ Միաձուլման ալգորիթմի Cache տարբերակը, որի գործողությունները հատուկ ընտրված են էջերի շարժման մինիմիզացման համար մեքենայի Cache հիշողության ներսում և դրսում, առաջարկված են։ Օրինակ tiled միաձուլման ալգորիթմը դադարեցրեց ենթազանգվածների մասնակցությունը, երբ S չափի ենթազանգվածները նվաճված են, որտեղ S- ը ժամանակահատվածի թիվն է, որը զբաղեցնում է CPU- ի cache- ը։ Այս ենթազանգվածներից յուրաքանչյուրն ընտրված է տեղում տեսակավորմամբ, խափանել հիշողության փոխանակումները և նորմալ միաձուլումն ավարտվում է ստանդարտ ռեկուրսիվ ձևով։ Այս ալգորիթմն ունեցել է ավելի լավ ազդեցություն մեքենաների վրա։ Քրոնռոդն առաջարկել է միաձուլման ալտերնատիվ միջոց, որն օգտագործում է միայն իր համար նախատեսված տարածքը։

Զուգահեռ գործընթաց

Միաձուլումը լավ համընկնում է բաժանիր և տիրիր մեթոդի հետ։ Զուգահեռ կատարումը ցույց է տրված pseudocode- ում։ Այս ալգորիթմ օգտագործվում է զուգահեռ միաձուլման ալգորիթմը զանգվածի ռեկուրսիվ բաժանումը ոչ միայն զուգորդման, այլև միաձուլման գործընթացում։ insertion sort,

Համեմատումն այլ տեսակավորման ալգորիթմների հետ

Չնայած կուտակված տեսակավորումն ունի միևնույն ժամանակի ծախսը, ինչ միաձուլումը, այն ծախսում է միայն Θ(1) օժանդակ տարածք միաձուլման Θ(n)- ի փոխարեն, և հաճախ ավելի արագ է պրակտիկ կիրառման ժամանակ։ Տիպիկ ժամանակակից կառույցներում արդյունավետ արագ տեսակավորման գործընթացը հիմնականում չեն ներկայացնում միաձուլումը RAM – ի վրա հիմնված զանգվածների տեսակավորման համար։ Մյուս կողմից միաձուլումը ստաբիլ տեսակ է և ավելի արդյունավետ է։ Միաձուլումը հաճախ լավագույն տարբերակն է կապված էջը տեսակավորելու համար։heapsort. quicksortlinked list։

Utility- ն օնլայն տեսակավորման մեջ

Միաձուլման գործընթացն օգտակար է online տեսակավորման համար, որտեղ էջը տեսակավորելու համար սկզբում ստանում է կտոր ժամանակին, ամբողջի փոխարեն։ Այս ապլիկացիայում մենք տեսակավորում ենք յուրաքանչյուր նոր տեսակավորման ալգորիթմների օգտագործումից ստացված կտոր, և միացնում այն տեսակավորված էջին՝ օգտագործելով միացման գործընթացը։ algorithm|online.

Կարծիքներ

• Կաղապար:Introduction to Algorithms
• Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). «Practical in-place mergesort». Nordic Journal of Computing. Vol. 3. էջեր 27–40. ISSN 1236-6064. Արխիվացված է օրիգինալից 2011 թ․ օգոստոսի 7-ին. Վերցված է 2009 թ․ ապրիլի 4-ին.. Also Practical In-Place Mergesort. Also [1]
• Knuth, Donald (1998). «Section 5.2.4: Sorting by Merging». Sorting and Searching. The Art of Computer Programming. Vol. 3 (2nd ed.). Addison-Wesley. էջեր 158–168. ISBN 0-201-89685-0.
• Kronrod, M. A. (1969). «Optimal ordering algorithm without operational field». Soviet Mathematics - Doklady. Vol. 10. էջ 744.
• LaMarca, A.; Ladner, R. E. (1997). «The influence of caches on the performance of sorting». Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA97): 370–379.
• Sun Microsystems, Inc. «Arrays API». Վերցված է 2007 թ․ նոյեմբերի 19–ին-ին.
• Sun Microsystems, Inc. «java.util.Arrays.java». Վերցված է 2007 թ․ նոյեմբերի 19–ին-ին.(չաշխատող հղում)

Արտաքին կապեր

• Merge sort in 20 languages Արխիվացված 2011-03-18 Wayback Machine
• Animated Sorting Algorithms: Merge Sort – graphical demonstration and discussion of array-based merge sort
• Merge sort applet Արխիվացված 2009-02-28 Wayback Machine with level order recursive calls to help improve algorithm analysis
• Dictionary of Algorithms and Data Structures: Merge sort
• Implementation of merge sort in various languages on Rosetta Code
• Literate implementations of merge sort in various languages Արխիվացված 2009-06-18 Wayback Machine on LiteratePrograms
• A colored graphical Java applet Արխիվացված 2011-07-08 Wayback Machine which allows experimentation with initial state and shows statistics
• Simon Tatham's explanation and code for a merge sort
• MergeSort tutorial and Java code for beginners Արխիվացված 2011-07-14 Wayback Machine
• Merge sort Fortran routines
• Merge Sort - Wolfram MathWorld