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

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

Goldstine 

Ալգորիթմ

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

recursively 

Merge

Միաձուլումը կազմի մեջ է մտցնում 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 3: pp. 27–40. ISSN 1236-6064. http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/mergesort_NJC.ps։ Վերցված է 2009-04-04. . Also Practical In-Place Mergesort. Also [1]
• Knuth, Donald (1998). "Section 5.2.4: Sorting by Merging", Sorting and Searching, 2nd, The Art of Computer Programming, Addison-Wesley, 158–168. ISBN 0-201-89685-0. 
• Kronrod, M. A. (1969). «Optimal ordering algorithm without operational field». Soviet Mathematics - Doklady 10: pp. 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»։ http://java.sun.com/javase/6/docs/api/java/util/Arrays.html։ Վերցված է 2007-11-19։ 
• Sun Microsystems, Inc.։ «java.util.Arrays.java»։ https://openjdk.dev.java.net/source/browse/openjdk/jdk/trunk/jdk/src/share/classes/java/util/Arrays.java?view=markup։ Վերցված է 2007-11-19։ 

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

• Merge sort in 20 languages
• Animated Sorting Algorithms: Merge Sort – graphical demonstration and discussion of array-based merge sort
• Merge sort applet 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 on LiteratePrograms
• A colored graphical Java applet 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
• Merge sort Fortran routines
• Merge Sort - Wolfram MathWorld