Merge sort არის კომპიუტერული მეცნიერების ერთ-ერთი ძირითადი ალგორითმი, ჩამოყალიბებული ჯერ კიდევ 1945 წელს დიდი მათემატიკოსის ჯონ ფონ ნეუმანის მიერ. მანჰეტენის პროექტში მონაწილეობისას, ნეუმანს დიდი რაოდენობის მონაცემების ეფექტურად დამუშავების აუცილებლობა შეექმნა. მის მიერ შემუშავებული მეთოდი იყენებდა „გაყავი და იბატონე“პრინციპს, რამაც საგრძნობლად შეამცირა სამუშაოსთვის საჭირო დრო.
ალგორითმის პრინციპი და გამოყენება
შერწყმის დალაგების მეთოდი გამოიყენება სტრუქტურების დახარისხების პრობლემებში, რომლებსაც აქვთ მოწესრიგებული წვდომა ელემენტებზე, როგორიცაა მასივები, სიები, ნაკადები.
დამუშავების დროს მონაცემთა საწყისი ბლოკი იყოფა მცირე კომპონენტებად, ერთ ელემენტამდე, რაც ფაქტობრივად უკვე დახარისხებული სიაა. შემდეგ ის ხელახლა იკრიბება სწორი თანმიმდევრობით.
გარკვეული სიგრძის მასივის დახარისხება მოითხოვს იმავე ზომის დამატებით მეხსიერების არეალს, რომელშიც დალაგებული მასივი ნაწილ-ნაწილ გროვდება.
მეთოდი შეიძლება გამოყენებულ იქნას ნებისმიერი შესადარებელი მონაცემთა ტიპის შესაკვეთად, როგორიცაა რიცხვები ან სტრიქონები.
შერწყმა დალაგებულიანაკვეთები
ალგორითმის გასაგებად, დავიწყოთ მისი ანალიზი ბოლოდან - დალაგებული ბლოკების შერწყმის მექანიზმიდან.
მოდით წარმოვიდგინოთ, რომ გვაქვს რიცხვების ორი მასივი დალაგებული ნებისმიერი გზით, რომლებიც უნდა იყოს ერთმანეთთან შერწყმული, რათა დალაგება არ დაირღვეს. სიმარტივისთვის, ჩვენ დავახარისხებთ რიცხვებს ზრდადი თანმიმდევრობით.
ელემენტარული მაგალითი: ორივე მასივი შედგება ერთი ელემენტისგან.
int arr1={31}; int arr2={18};
მათი გაერთიანებისთვის, თქვენ უნდა აიღოთ პირველი მასივის ნულოვანი ელემენტი (არ დაგავიწყდეთ, რომ ნუმერაცია იწყება ნულიდან) და მეორე მასივის ნულოვანი ელემენტი. ეს არის, შესაბამისად, 31 და 18. დახარისხების პირობის მიხედვით, რიცხვი 18 უნდა იყოს პირველი, რადგან ის ნაკლებია. უბრალოდ ჩაწერეთ რიცხვები სწორი თანმიმდევრობით:
int შედეგი={18, 31};
მოდით შევხედოთ უფრო რთულ მაგალითს, სადაც თითოეული მასივი შედგება რამდენიმე ელემენტისგან:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
შერწყმის ალგორითმი შედგება მცირე ელემენტების თანმიმდევრული შედარებისგან და მათ მიღებულ მასივში სწორი თანმიმდევრობით მოთავსებისგან. იმისთვის, რომ თვალყური ადევნოთ მიმდინარე ინდექსებს, შემოვიღოთ ორი ცვლადი - index1 და index2. თავდაპირველად, ჩვენ ვაყენებთ მათ ნულზე, რადგან მასივები დალაგებულია, ხოლო ყველაზე პატარა ელემენტები დასაწყისშია.
int index1=0; int index2=0;
მოდით დავწეროთ მთელი შერწყმის პროცესი ეტაპობრივად:
- აიღეთ ელემენტი index1-ით arr1 მასივიდან და ელემენტი index2-ით arr2-დან.
- შეადარეთ, აირჩიეთ მათგან ყველაზე პატარა და ჩადეთშედეგად მიღებული მასივი.
- გაზარდეთ პატარა ელემენტის მიმდინარე ინდექსი 1-ით.
- გააგრძელეთ პირველი ნაბიჯიდან.
პირველ ორბიტაზე სიტუაცია ასე გამოიყურება:
index1=0; ინდექსი2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; ინდექსი1++; შედეგი[0]=arr1[0]; // შედეგი=[2]
მეორე შემობრუნებაზე:
index1=1; ინდექსი2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; ინდექსი2++; შედეგი[1]=arr2[0]; // შედეგი=[2, 5]
მესამე:
index1=1; ინდექსი2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; ინდექსი2++; შედეგი[2]=arr2[1]; // შედეგი=[2, 5, 6]
და ასე შემდეგ, სანამ შედეგი არ იქნება მთლიანად დალაგებული მასივი: {2, 5, 6, 17, 21, 19, 30, 45}.
სხვადასხვა სიგრძის მასივების გაერთიანების შემთხვევაში შეიძლება წარმოიშვას გარკვეული სირთულეები. რა მოხდება, თუ ერთ-ერთმა მიმდინარე ინდექსმა მიაღწია ბოლო ელემენტს და დარჩენილია წევრები მეორე მასივში?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 ნაბიჯის ინდექსი1=0, ინდექსი2=0; 1 2 შედეგი={1, 2}; // 3 ნაბიჯის ინდექსი1=1, ინდექსი2=1; 4 < 5 შედეგი={1, 2, 4}; //4 ნაბიჯის ინდექსი1=2, ინდექსი2=1 ??
index1 ცვლადმა მიაღწია 2 მნიშვნელობას, მაგრამ arr1 მასივს არ აქვს ელემენტი ამ ინდექსით. აქ ყველაფერი მარტივია: უბრალოდ გადაიტანეთ მეორე მასივის დარჩენილი ელემენტები მიღებულ მასივზე, მათი თანმიმდევრობის შენარჩუნებით.
შედეგი={1, 2, 4, 5, 6, 7, 9};
ეს სიტუაცია მიუთითებს ჩვენზე საჭიროებაზეემთხვევა მიმდინარე შემოწმების ინდექსს გაერთიანებული მასივის სიგრძესთან.
შერწყმის სქემა სხვადასხვა სიგრძის მოწესრიგებული მიმდევრებისთვის (A და B):
- თუ ორივე მიმდევრობის სიგრძე 0-ზე მეტია, შეადარეთ A[0] და B[0] და გადაიტანეთ პატარა ბუფერში.
- თუ ერთ-ერთი მიმდევრობის სიგრძეა 0, აიღეთ მეორე მიმდევრობის დარჩენილი ელემენტები და მათი რიგის შეცვლის გარეშე გადადით ბუფერის ბოლოს.
მეორე ეტაპის განხორციელება
Java-ში ორი დახარისხებული მასივის შეერთების მაგალითი მოცემულია ქვემოთ.
int a1=ახალი int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=ახალი int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=ახალი int[a1.სიგრძე + a2.სიგრძე]; int i=0, j=0; for (int k=0; k a1.სიგრძე-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=a; მე++; } else if (a1 < a2[j]) { int a=a1; a3[k]=a; მე++; } else { int b=a2[j]; a3[k]=b; j++; } }
აქ:
- a1 და a2 არის ორიგინალური დახარისხებული მასივები, რომლებიც უნდა გაერთიანდეს;
- a3 - საბოლოო მასივი;
- i და j არის მიმდინარე ელემენტების ინდექსები a1 და a2 მასივებისთვის.
პირველი და მეორე თუ პირობები უზრუნველყოფს, რომ ინდექსები არ სცდება მასივის ზომას. მესამე და მეოთხე მდგომარეობის ბლოკები, შესაბამისად, გადატანილია მცირე ელემენტის მიღებულ მასივში.
გათიშე და იბატონე
მაშ, ჩვენ ვისწავლეთ დალაგების შერწყმაღირებულებების კოლექციები. შეიძლება ითქვას, რომ შერწყმის დახარისხების ალგორითმის მეორე ნაწილი - თავად შერწყმა - უკვე დახარისხებულია.
თუმცა, თქვენ მაინც უნდა გესმოდეთ, როგორ გადახვიდეთ რიცხვების ორიგინალური დაუხარისხებელი მასივიდან რამდენიმე დალაგებულ რიცხვებამდე, რომლებიც შეიძლება გაერთიანდეს.
მოდით განვიხილოთ ალგორითმის პირველი ეტაპი და ვისწავლოთ როგორ გამოვყოთ მასივები.
ეს არ არის რთული - მნიშვნელობების თავდაპირველი სია გაყოფილია ნახევრად, შემდეგ თითოეული ნაწილი ასევე ორადაა და ასე გრძელდება ძალიან მცირე ბლოკების მიღებამდე.
ასეთი მინიმალური ელემენტების სიგრძე შეიძლება იყოს ერთის ტოლი, ანუ ისინი თავად შეიძლება იყვნენ დახარისხებული მასივი, მაგრამ ეს არ არის აუცილებელი პირობა. ბლოკის ზომა წინასწარ არის განსაზღვრული და მისი შეკვეთისთვის შეიძლება გამოყენებულ იქნას ნებისმიერი შესაფერისი დახარისხების ალგორითმი, რომელიც ეფექტურად მუშაობს მცირე ზომის მასივებთან (მაგალითად, სწრაფი დახარისხება ან ჩასმის დალაგება).
ეს ასე გამოიყურება.
// ორიგინალური მასივი {34, 95, 10, 2, 102, 70}; // პირველი გაყოფა {34, 95, 10} და {2, 102, 70}; // წამის გაყოფა {34} და {95, 10} და {2} და {102, 70}
მიღებული ბლოკები, რომლებიც შედგება 1-2 ელემენტისგან, ძალიან მარტივი დასაწყობია.
ამის შემდეგ, თქვენ უნდა გააერთიანოთ უკვე დალაგებული პატარა მასივები წყვილებში, წევრების თანმიმდევრობის შენარჩუნებით, რაც უკვე ვისწავლეთ.
პირველი ეტაპის განხორციელება
მაივის რეკურსიული დაყოფა ნაჩვენებია ქვემოთ.
void mergeSort(T a, ხანგრძლივი დაწყება, ხანგრძლივი დასრულება) { long split; თუ(დაწყება < დასრულება) { split=(დაწყება + დასრულება)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); შერწყმა (ა, დაწყება, გაყოფა, დასრულება); } }
რა ხდება ამ კოდში:
-
mergeSort ფუნქცია იღებს საწყის მასივს
a
და დასახარისხებელი რეგიონის მარცხენა და მარჯვენა საზღვრებს (ინდექსები იწყება და
- დასრულება).
-
თუ ამ მონაკვეთის სიგრძე ერთზე მეტია (
დაწყება < დასრულება
), მაშინ ის იყოფა ორ ნაწილად (ინდექსით
- გაყოფა), და თითოეული დალაგებულია რეკურსიულად.
-
მარცხენა მხარის რეკურსიული ფუნქციის გამოძახებისას, ნაკვეთის საწყისი ინდექსი და ინდექსი
split
გადადის. სწორისთვის, შესაბამისად, დასაწყისი იქნება
- (გაყოფა + 1) და დასასრული იქნება ორიგინალური განყოფილების ბოლო ინდექსი.
-
ფუნქცია
შერწყმა
იღებს ორ დალაგებულ თანმიმდევრობას (
a[დაწყება]…a[გაყოფა]
და
- a[გაყოფა +1]…a[დასრულება]) და აერთიანებს მათ დალაგების მიხედვით.
შერწყმის ფუნქციის მექანიკა განხილულია ზემოთ.
ალგორითმის ზოგადი სქემა
შერწყმის დახარისხების მეთოდი შედგება ორი დიდი ნაბიჯისგან:
- დაყავით დაუხარისხებელი ორიგინალური მასივი პატარა ნაჭრებად.
- შეაგროვეთ ისინი წყვილებში დახარისხების წესის მიხედვით.
დიდი და რთული ამოცანა იყოფა ბევრ მარტივ ამოცანად, რომლებიც თანმიმდევრულად იხსნება და მივყავართ სასურველ შედეგამდე.
მეთოდის შეფასება
შერწყმის დახარისხების დროის სირთულე განისაზღვრება გაყოფილი ხის სიმაღლითალგორითმი და უდრის მასივის ელემენტების რაოდენობას (n) გამრავლებული მის ლოგარითმზე (log n). ასეთ შეფასებას ლოგარითმული ეწოდება.
ეს არის მეთოდის როგორც უპირატესობა, ასევე უარყოფითი მხარე. მისი გაშვების დრო არ იცვლება უარეს შემთხვევაშიც კი, როდესაც ორიგინალური მასივი დალაგებულია საპირისპირო თანმიმდევრობით. თუმცა, სრულად დალაგებული მონაცემების დამუშავებისას, ალგორითმი არ იძლევა დროის მომატებას.
ასევე მნიშვნელოვანია აღინიშნოს შერწყმის დახარისხების მეთოდის მეხსიერების ღირებულება. ისინი უდრის ორიგინალური კოლექციის ზომას. ამ დამატებით გამოყოფილ ზონაში, დახარისხებული მასივი იკრიბება ნაწილებისგან.
ალგორითმის განხორციელება
პასკალის შერწყმის დალაგება ნაჩვენებია ქვემოთ.
პროცედურა MergeSort(სახელი: string; var f: text); Var a1, a2, s, i, j, kol, tmp: მთელი რიცხვი; f1, f2: ტექსტი; ბ: ლოგიკური დასაწყისი:=0; მინიჭება (f, სახელი); გადატვირთვა (f); მიუხედავად იმისა, რომ EOF(f) არ არის, დაიწყეთ კითხვა (f, a1); inc(col); დასასრული; დახურვა (f); Assign(f1, '{1st დამხმარე ფაილის სახელი}'); Assign(f2, '{მე-2 დამხმარე ფაილის სახელი}'); s:=1; სანამ (s<kol) დაიწყება Reset(f); გადაწერა (f1); გადაწერა (f2); იყიდება i:=1-დან kol div 2-მდე დაიწყება Read(f, a1); Write(f1, a1, ' '); დასასრული; თუ (kol div 2) mod s0 დაიწყეთ tmp:=kol div 2; სანამ tmp mod s0 დაიწყება Read(f, a1); Write(f1, a1, ' '); inc(tmp); დასასრული; დასასრული; სანამ EOF(f) არ იწყება Read(f, a2); Write(f2, a2, ' '); დასასრული; დახურვა (f); დახურვა (f1); დახურვა (f2); გადაწერა (f); გადატვირთვა (f1); გადატვირთვა (f2); წაკითხვა (f1, a1); წაკითხვა (f2, a2); სანამ (არა EOF(f1)) და (არა EOF(f2)) იწყება i:=0; j:=0; ბ:=მართალია; სანამ (b) და (არა EOF(f1)) და (არა EOF(f2)) იწყება თუ (a1<a2) მაშინ დაიწყებაWrite(f, a1, ' '); წაკითხვა (f1, a1); inc(i); ბოლოს სხვა დაწყება Write(f, a2, ' '); წაკითხვა (f2, a2); inc(j); დასასრული; თუ (i=s) ან (j=s) მაშინ b:=false; დასასრული; თუ არა b, მაშინ დაიწყეთ while (i<s) და (არა EOF(f1)) დაიწყეთ Write(f, a1, ''); წაკითხვა (f1, a1); inc(i); დასასრული; სანამ (j<s) და (არა EOF(f2)) იწყებენ Write(f, a2, ' '); წაკითხვა (f2, a2); inc(j); დასასრული; დასასრული; დასასრული; სანამ EOF(f1) არ არის, დაიწყეთ tmp:=a1; წაკითხვა (f1, a1); თუ არა EOF(f1) მაშინ Write(f, tmp, ' ') else Write(f, tmp); დასასრული; სანამ EOF(f2) არ არის, დაიწყეთ tmp:=a2; წაკითხვა (f2, a2); თუ არა EOF(f2) მაშინ Write(f, tmp, ' ') else Write(f, tmp); დასასრული; დახურვა (f); დახურვა (f1); დახურვა (f2); s:=s2; დასასრული; წაშლა (f1); წაშლა (f2); დასასრული;
ვიზუალურად, ალგორითმის მოქმედება ასე გამოიყურება (ზემოდან - უწესრიგო თანმიმდევრობა, ქვედა - მოწესრიგებული).
გარე მონაცემების დახარისხება
ძალიან ხშირად ჩნდება კომპიუტერის გარე მეხსიერებაში მდებარე ზოგიერთი მონაცემის დახარისხების საჭიროება. ზოგიერთ შემთხვევაში, ისინი შთამბეჭდავი ზომისაა და არ შეიძლება მოთავსდეს RAM-ში მათზე წვდომის გასაადვილებლად. ასეთი შემთხვევებისთვის გამოიყენება გარე დახარისხების მეთოდები.
გარე მედიაზე წვდომის აუცილებლობა ამცირებს დამუშავების დროის ეფექტურობას.
ნამუშევრის სირთულე იმაში მდგომარეობს, რომ ალგორითმს შეუძლია მონაცემთა ნაკადის მხოლოდ ერთ ელემენტზე წვდომა ერთდროულად. და ამ შემთხვევაში, ერთ-ერთი საუკეთესო შედეგი ნაჩვენებია შერწყმის დახარისხების მეთოდით, რომელსაც შეუძლია ორი ფაილის ელემენტების ერთმანეთის მიყოლებით შედარება.
მონაცემების წაკითხვაგარე წყარო, მათი დამუშავება და საბოლოო ფაილზე ჩაწერა ხდება შეკვეთილ ბლოკებში (სერიებში). შეკვეთილი სერიების ზომასთან მუშაობის წესის მიხედვით, არსებობს დახარისხების ორი ტიპი: მარტივი და ბუნებრივი შერწყმა.
მარტივი შერწყმა
მარტივი შერწყმით, სერიის სიგრძე ფიქსირდება.
ამგვარად, თავდაპირველ დაუხარისხებელ ფაილში, ყველა სერია შედგება ერთი ელემენტისგან. პირველი ნაბიჯის შემდეგ ზომა ორამდე იზრდება. შემდეგი - 4, 8, 16 და ასე შემდეგ.
მუშაობს ასე:
- წყაროს ფაილი (f) იყოფა ორ დამხმარე - f1, f2.
- ისინი კვლავ გაერთიანებულია ერთ ფაილში (f), მაგრამ ამავე დროს ყველა ელემენტი შედარებულია წყვილებში და ქმნიან წყვილებს. სერიის ზომა ამ ეტაპზე ხდება ორი.
- ნაბიჯი 1 მეორდება.
- ნაბიჯი 2 მეორდება, მაგრამ უკვე დალაგებული 2-ები გაერთიანებულია დახარისხებული 4-ების შესაქმნელად.
- ციკლი გრძელდება, იზრდება სერიები ყოველ გამეორებაზე, სანამ მთელი ფაილი არ დალაგდება.
საიდან იცით, რომ გარე დახარისხება მარტივი შერწყმით დასრულებულია?
- ახალი სერიის სიგრძე (შერწყმის შემდეგ) არანაკლებ ელემენტების საერთო რაოდენობაზე;
- დარჩენილია მხოლოდ ერთი ეპიზოდი;
- დამხმარე ფაილი f2 ცარიელი დარჩა.
მარტივი შერწყმის უარყოფითი მხარეა: ვინაიდან გაშვების სიგრძე ფიქსირდება ყოველ შერწყმის უღელტეხილზე, ნაწილობრივ შეკვეთილი მონაცემების დამუშავებას იმდენი დრო დასჭირდება, როგორც სრულიად შემთხვევითი მონაცემები.
ბუნებრივი შერწყმა
ეს მეთოდი არ ზღუდავს სიგრძესსერია, მაგრამ ირჩევს მაქსიმუმს.
დახარისხების ალგორითმი:
- საწყისი თანმიმდევრობის წაკითხვა ფაილიდან f. პირველი მიღებული ელემენტი იწერება ფაილში f1.
- თუ შემდეგი ჩანაწერი აკმაყოფილებს დახარისხების პირობას, იქ იწერება, თუ არა, მაშინ მეორე დამხმარე ფაილში f2.
- ამ გზით, წყაროს ფაილის ყველა ჩანაწერი ნაწილდება და f1-ში ყალიბდება მოწესრიგებული თანმიმდევრობა, რომელიც განსაზღვრავს სერიის მიმდინარე ზომას.
- ფაილები f1 და f2 გაერთიანდა.
- ციკლი მეორდება.
სერიის არაფიქსირებული ზომის გამო, აუცილებელია მიმდევრობის დასასრულის აღნიშვნა სპეციალური სიმბოლოთი. ამიტომ, შერწყმისას, შედარებების რაოდენობა იზრდება. გარდა ამისა, ერთ-ერთი დამხმარე ფაილის ზომა შეიძლება ახლოს იყოს ორიგინალის ზომასთან.
საშუალოდ, ბუნებრივი შერწყმა უფრო ეფექტურია, ვიდრე მარტივი შერწყმა გარე დალაგებით.
ალგორითმის მახასიათებლები
ორი იდენტური მნიშვნელობის შედარებისას მეთოდი ინარჩუნებს მათ თავდაპირველ წესრიგს, ანუ სტაბილურია.
დახარისხების პროცესი შეიძლება ძალიან წარმატებით დაიყოს მრავალ ძაფად.
ვიდეო ნათლად აჩვენებს შერწყმის დალაგების ალგორითმის მოქმედებას.
