Merge sort 1945-ci ildə böyük riyaziyyatçı Con fon Neumann tərəfindən tərtib edilmiş əsas kompüter elmi alqoritmlərindən biridir. Manhetten Layihəsində iştirak edərkən Neumann böyük həcmdə məlumatı səmərəli şəkildə emal etmək ehtiyacı ilə üzləşdi. Onun inkişaf etdirdiyi metodda "böl və qalib gəl" prinsipindən istifadə olunurdu ki, bu da iş üçün tələb olunan vaxtı əhəmiyyətli dərəcədə azaldır.
Alqoritmin prinsipi və istifadəsi
Birləşmə çeşidləmə metodu massivlər, siyahılar, axınlar kimi elementlərə sifarişli girişi olan strukturların çeşidlənməsi problemlərində istifadə olunur.
Emal zamanı ilkin məlumat bloku bir elementə qədər kiçik komponentlərə bölünür ki, bu da əslində artıq çeşidlənmiş siyahıdır. Sonra düzgün ardıcıllıqla yenidən yığılır.
Müəyyən uzunluqlu massivin çeşidlənməsi eyni ölçülü əlavə yaddaş sahəsi tələb edir və çeşidlənmiş massiv hissə-hissə toplanır.
Metod rəqəmlər və ya sətirlər kimi istənilən müqayisə edilə bilən məlumat növünü sifariş etmək üçün istifadə edilə bilər.
Birləşmə çeşidləndisüjetlər
Alqoritmi başa düşmək üçün onun təhlilinə sondan - çeşidlənmiş blokların birləşmə mexanizmindən başlayaq.
Təsəvvür edək ki, çeşidləmə pozulmaması üçün bir-biri ilə birləşdirilməli olan hər hansı şəkildə çeşidlənmiş iki ədəd massivimiz var. Sadəlik üçün rəqəmləri artan qaydada çeşidləyəcəyik.
Elementar nümunə: hər iki massiv hər biri bir elementdən ibarətdir.
int arr1={31}; int arr2={18};
Onları birləşdirmək üçün birinci massivin sıfır elementini (nömrələmənin sıfırdan başladığını unutmayın) və ikinci massivin sıfır elementini götürməlisiniz. Bunlar müvafiq olaraq 31 və 18-dir. Çeşidləmə şərtinə görə 18 rəqəmi birinci gəlməlidir, çünki o, azdır. Sadəcə nömrələri düzgün ardıcıllıqla qoyun:
int nəticə={18, 31};
Hər massivin bir neçə elementdən ibarət olduğu daha mürəkkəb nümunəyə baxaq:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Birləşmə alqoritmi daha kiçik elementləri ardıcıl olaraq müqayisə etməkdən və onları düzgün ardıcıllıqla nəticələnən massivdə yerləşdirməkdən ibarət olacaq. Cari indeksləri izləmək üçün iki dəyişən təqdim edək - index1 və index2. Massivlər çeşidləndiyi və ən kiçik elementlər başlanğıcda olduğu üçün ilkin olaraq onları sıfıra təyin etdik.
int indeks1=0; int indeksi2=0;
Bütün birləşmə prosesini addım-addım yazaq:
- İndeks1 olan elementi arr1 massivindən, index2 olan elementi isə massiv2-dən götürün.
- Müqayisə edin, onlardan ən kiçiyini seçin və daxil edinnəticə massivi.
- Kiçik elementin cari indeksini 1 artırın.
- İlk addımdan davam edin.
İlk orbitdə vəziyyət belə görünəcək:
index1=0; indeks2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; indeks1++; nəticə[0]=arr1[0]; // nəticə=[2]
İkinci döngədə:
index1=1; indeks2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; indeks2++; nəticə[1]=arr2[0]; // nəticə=[2, 5]
Üçüncü:
index1=1; indeks2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; indeks2++; nəticə[2]=arr2[1]; // nəticə=[2, 5, 6]
Və s., nəticə tamamilə çeşidlənmiş massiv olana qədər: {2, 5, 6, 17, 21, 19, 30, 45}.
Müxtəlif uzunluqlu massivlər birləşdirilərsə, müəyyən çətinliklər yarana bilər. Bəs cari indekslərdən biri sonuncu elementə çatıbsa və ikinci massivdə hələ də üzvlər qalıbsa?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 addım indeks1=0, indeks2=0; 1 2 nəticə={1, 2}; // 3 addımlı indeks1=1, indeks2=1; 4 < 5 nəticə={1, 2, 4}; //4 addım indeks1=2, indeks2=1 ??
İndeks1 dəyişəni 2 dəyərinə çatıb, lakin arr1 massivində həmin indekslə element yoxdur. Burada hər şey sadədir: sadəcə olaraq ikinci massivin qalan elementlərini onların sırasını qoruyaraq nəticədə əldə edilənə köçürün.
nəticə={1, 2, 4, 5, 6, 7, 9};
Bu vəziyyət bizə ehtiyacdan xəbər verircari yoxlama indeksini birləşdirilən massivin uzunluğu ilə uyğunlaşdırın.
Müxtəlif uzunluqda sifariş edilmiş ardıcıllıqlar (A və B) üçün birləşdirmə sxemi:
- Hər iki ardıcıllığın uzunluğu 0-dan böyükdürsə, A[0] və B[0]-ı müqayisə edin və kiçik olanı buferə köçürün.
- Ardıcıllıqlardan birinin uzunluğu 0-dırsa, ikinci ardıcıllığın qalan elementlərini götürün və onların sırasını dəyişmədən buferin sonuna keçin.
İkinci mərhələnin həyata keçirilməsi
Java-da iki çeşidlənmiş massivin birləşdirilməsi nümunəsi aşağıda verilmişdir.
int a1=yeni int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=yeni int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=yeni int[a1.uzunluq + a2.uzunluq]; int i=0, j=0; üçün (int k=0; k a1.uzunluq-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=a; i++; } else if (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } else { int b=a2[j]; a3[k]=b; j++; } }
Burada:
- a1 və a2 birləşdiriləcək orijinal çeşidlənmiş massivlərdir;
- a3 – yekun massiv;
- i və j a1 və a2 massivləri üçün cari elementlərin indeksləridir.
Birinci və ikinci əgər şərtlər indekslərin massivin ölçüsündən kənara çıxmamasını təmin edir. Üçüncü və dördüncü şərt blokları müvafiq olaraq daha kiçik elementin nəticə massivinə köçürülür.
Bölün və Qalib Ol
Beləliklə, biz çeşidlənmişləri birləşdirməyi öyrəndikdəyərlər toplusu. Demək olar ki, birləşmənin çeşidlənməsi alqoritminin ikinci hissəsi - birləşmənin özü - artıq çeşidlənib.
Lakin siz hələ də orijinal sıralanmamış nömrələr massivindən birləşdirilə bilən bir neçə çeşidlənmiş sıraya necə keçəcəyinizi başa düşməlisiniz.
Gəlin alqoritmin birinci mərhələsini nəzərdən keçirək və massivləri necə ayırmağı öyrənək.
Bu çətin deyil - dəyərlərin orijinal siyahısı yarıya bölünür, sonra hər bir hissə də ikiyə bölünür və çox kiçik bloklar əldə olunana qədər belə davam edir.
Belə minimal elementlərin uzunluğu birinə bərabər ola bilər, yəni onlar özləri sıralanmış massiv ola bilərlər, lakin bu zəruri şərt deyil. Blokun ölçüsü əvvəlcədən müəyyən edilir və onu sifariş etmək üçün kiçik ölçülü massivlərlə (məsələn, sürətli çeşidləmə və ya daxiletmə çeşidi) səmərəli işləyən istənilən uyğun çeşidləmə alqoritmi istifadə edilə bilər.
Belə görünür.
// orijinal massiv {34, 95, 10, 2, 102, 70}; // ilk bölünmə {34, 95, 10} və {2, 102, 70}; // ikinci bölgü {34} və {95, 10} və {2} və {102, 70}
1-2 elementdən ibarət olan blokları təşkil etmək çox asandır.
Bundan sonra siz artıq öyrəndiyimiz üzvlərin sırasını qorumaqla artıq çeşidlənmiş kiçik massivləri cüt-cüt birləşdirməlisiniz.
Birinci mərhələnin həyata keçirilməsi
Massivin rekursiv bölməsi aşağıda göstərilmişdir.
void mergeSort(T a, uzun başlanğıc, uzun bitiş) { uzun bölünmə; əgər(start < finish) { split=(start + finish)/2; mergeSort(a, start, split); mergeSort(a, split+1, bitir); birləşmə (a, başlamaq, bölmək, bitirmək); } }
Bu kodda nə baş verir:
-
MergeSort funksiyası
a
ilkin massivi və çeşidlənəcək regionun sol və sağ sərhədlərini əldə edir (indekslər başlanğıc və
- finish).
-
Bu bölmənin uzunluğu birdən çox olarsa (
start < finish
), o zaman iki hissəyə bölünür (indeks üzrə
- split) və hər biri rekursiv olaraq sıralanır.
-
Sol tərəf üçün rekursiv funksiya çağırışında süjetin başlanğıc indeksi və
split
indeksi ötürülür. Düzgün olan üçün başlanğıc
- (bölünmüş + 1), sonu isə orijinal bölmənin son indeksi olacaq.
-
Funksiya
merge
iki sıralı ardıcıllıq əldə edir (
a[start]…a[split]
və
- a[bölünmüş) +1]…a[finish]) və onları çeşidləmə qaydasında birləşdirir.
Birləşmə funksiyasının mexanikası yuxarıda müzakirə edilmişdir.
Alqoritmin ümumi sxemi
Birləşmə sıralama massivi üsulu iki böyük addımdan ibarətdir:
- Çöllənməmiş orijinal massivi kiçik parçalara bölün.
- Çeşidləmə qaydasına əməl edərək onları cüt-cüt toplayın.
Böyük və mürəkkəb tapşırıq bir çox sadə tapşırıqlara bölünür, onlar ardıcıllıqla həll edilir və bu, arzu olunan nəticəyə gətirib çıxarır.
Metodun qiymətləndirilməsi
Birləşmə növünün vaxt mürəkkəbliyi bölünmüş ağacın hündürlüyü ilə müəyyən ediliralqoritmdir və massivdəki elementlərin sayının (n) onun loqarifminin (log n) çarpımına bərabərdir. Belə hesablama loqarifmik adlanır.
Bu, metodun həm üstünlüyü, həm də dezavantajıdır. Orijinal massiv tərs qaydada çeşidləndikdə, onun işləmə müddəti ən pis halda belə dəyişmir. Bununla belə, tam çeşidlənmiş verilənləri emal edərkən, alqoritm vaxt qazancını təmin etmir.
Birləşdirmə çeşidləmə metodunun yaddaş xərclərini də qeyd etmək vacibdir. Onlar orijinal kolleksiyanın ölçüsünə bərabərdirlər. Bu əlavə olaraq ayrılmış sahədə parçalardan çeşidlənmiş massiv yığılır.
Alqoritmin həyata keçirilməsi
Paskal birləşmə çeşidi aşağıda göstərilmişdir.
Prosedur MergeSort(ad: sətir; var f: mətn); Var a1, a2, s, i, j, kol, tmp: tam ədəd; f1, f2: mətn; b: boolean Begincol:=0; Təyin (f, ad); sıfırla(f); EOF(f) olmasa da (f, a1) oxumağa başlayın; inc(col); son; yaxın(f); Assign(f1, '{1-ci köməkçi faylın adı}'); Assign(f2, '{2-ci köməkçi faylın adı}'); s:=1; (s<kol) sıfırlamağa başlasa da(f); yenidən yaz (f1); yenidən yaz (f2); i:=1 to kol div 2 üçün Read(f, a1); Yaz(f1, a1, ' '); son; Əgər (kol div 2) mod s0 olarsa, onda tmp başlayın:=kol div 2; tmp mod s0 oxumağa başlayarkən (f, a1); Yaz(f1, a1, ' '); inc(tmp); son; son; EOF(f) olmasa da Oxumağa (f, a2) başlayın; Yaz(f2, a2, ' '); son; yaxın(f); yaxın(f1); yaxın(f2); yenidən yaz (f); sıfırla (f1); sıfırla (f2); Oxu (f1, a1); Oxu (f2, a2); (EOF(f1) deyil) və (EOF(f2) deyil) isə başlayır i:=0; j:=0; b:=doğru; (b) və (EOF(f1) deyil) və (EOF(f2) deyil) başladıqda (a1<a2) başlasınYaz(f, a1, ' '); Oxu (f1, a1); inc(i); End else begin Write(f, a2, ' '); Oxu (f2, a2); inc(j); son; Əgər (i=s) və ya (j=s) onda b:=false; son; Əgər b deyilsə, onda başlayın While (i<s) və (EOF(f1) deyil) başlayır Write(f, a1, ' '); Oxu (f1, a1); inc(i); son; (j<s) və (EOF(f2) deyil) Write (f, a2, ' '); Oxu (f2, a2); inc(j); son; son; son; EOF(f1) olmasa da tmp:=a1; Oxu (f1, a1); EOF(f1) deyilsə, Write(f, tmp, ' ') else Write(f, tmp); son; EOF(f2) olmasa da tmp:=a2; Oxu (f2, a2); EOF(f2) deyilsə, Write(f, tmp, ' ') else Write(f, tmp); son; yaxın(f); yaxın(f1); yaxın(f2); s:=s2; son; Silin (f1); Silin (f2); Son;
Vizual olaraq alqoritmin işləməsi belə görünür (yuxarı - sırasız ardıcıllıq, aşağı - sıralı).
Xarici məlumat çeşidlənməsi
Çox tez-tez kompüterin xarici yaddaşında olan bəzi məlumatların çeşidlənməsinə ehtiyac var. Bəzi hallarda, onlar təsir edici ölçüdədirlər və onlara girişi asanlaşdırmaq üçün RAM-a yerləşdirilə bilməzlər. Belə hallar üçün xarici çeşidləmə üsullarından istifadə olunur.
Xarici mediaya daxil olma ehtiyacı emal vaxtının səmərəliliyini aşağı salır.
İşin mürəkkəbliyi ondan ibarətdir ki, alqoritm eyni anda məlumat axınının yalnız bir elementinə daxil ola bilər. Və bu halda, ən yaxşı nəticələrdən biri iki faylın elementlərini ardıcıl olaraq bir-birinin ardınca müqayisə edə bilən birləşmə çeşidləmə üsulu ilə göstərilir.
Məlumat oxunurxarici mənbə, onların işlənməsi və yekun fayla yazılması sifarişli bloklarda (seriya) həyata keçirilir. Sifariş edilmiş seriyanın ölçüsü ilə işləmə üsuluna görə, iki növ çeşidləmə var: sadə və təbii birləşmə.
Sadə birləşmə
Sadə birləşmə ilə seriya uzunluğu sabitlənir.
Beləliklə, orijinal çeşidlənməmiş faylda bütün seriyalar bir elementdən ibarətdir. İlk addımdan sonra ölçü ikiyə qədər artır. Sonrakı - 4, 8, 16 və s..
Belə işləyir:
- Mənbə faylı (f) iki köməkçiyə bölünür - f1, f2.
- Onlar yenidən bir faylda birləşdirilir (f), lakin eyni zamanda bütün elementlər cüt-cüt müqayisə edilir və cütlər yaradır. Bu addımda seriya ölçüsü iki olur.
- 1-ci addım təkrarlanır.
- 2-ci addım təkrarlanır, lakin artıq sifariş edilmiş 2-lər sıralanmış 4-lər yaratmaq üçün birləşdirilir.
- Dövrə bütün fayl sıralanana qədər hər iterasiyada seriyanı artıraraq davam edir.
Sadə birləşmə ilə xarici çeşidləmənin tamamlandığını haradan bilirsiniz?
- yeni seriya uzunluğu (birləşdikdən sonra) elementlərin ümumi sayından az olmamalıdır;
- yalnız bir epizod qaldı;
- F2 köməkçi faylı boş qaldı.
Sadə birləşmənin çatışmazlıqları bunlardır: qaçış uzunluğu hər birləşmə keçidində sabit olduğundan, qismən sıralanmış məlumatların işlənməsi tamamilə təsadüfi məlumat qədər uzun çəkəcək.
Təbii birləşmə
Bu üsul uzunluğu məhdudlaşdırmırseriya, lakin mümkün olan maksimumu seçir.
Çeşidləmə alqoritmi:
- f faylından ilkin ardıcıllığın oxunması. İlk qəbul edilən element f1 faylına yazılır.
- Növbəti qeyd çeşidləmə şərtini ödəyirsə, orada, yoxsa, f2 ikinci köməkçi faylına yazılır.
- Beləliklə, mənbə faylının bütün qeydləri paylanır və f1-də seriyanın cari ölçüsünü təyin edən ardıcıl ardıcıllıq formalaşır.
- f1 və f2 faylları birləşdirilib.
- Dövr təkrarlanır.
Serialın qeyri-sabit ölçüsünə görə, ardıcıllığın sonunu xüsusi simvolla qeyd etmək lazımdır. Ona görə də birləşmə zamanı müqayisələrin sayı artır. Bundan əlavə, köməkçi fayllardan birinin ölçüsü orijinalın ölçüsünə yaxın ola bilər.
Orta hesabla, təbii birləşmə xarici çeşidlə sadə birləşmədən daha səmərəlidir.
Alqoritmin xüsusiyyətləri
İki eyni dəyəri müqayisə edərkən metod onların orijinal sırasını qoruyur, yəni sabitdir.
Çeşidləmə prosesi çox uğurla bir neçə başlığa bölünə bilər.
Video birləşmə çeşidləmə alqoritminin işini aydın şəkildə nümayiş etdirir.
