Birleştirme sıralama, 1945'te büyük matematikçi John von Neumann tarafından formüle edilen temel bilgisayar bilimi algoritmalarından biridir. Manhattan Projesi'ne katılırken Neumann, büyük miktarda veriyi verimli bir şekilde işleme ihtiyacıyla karşı karşıya kaldı. Geliştirdiği yöntem, iş için gereken süreyi önemli ölçüde az altan "böl ve yönet" ilkesini kullandı.
Algoritmanın ilkesi ve kullanımı
Birleştirme sıralama yöntemi, diziler, listeler, akışlar gibi öğelere sıralı erişime sahip yapıları sıralama problemlerinde kullanılır.
İşleme sırasında, ilk veri bloğu, aslında zaten sıralanmış bir liste olan bir öğeye kadar küçük bileşenlere bölünür. Ardından doğru sırada yeniden birleştirilir.
Belirli uzunluktaki bir diziyi sıralamak, sıralanan dizinin parçalar halinde toplandığı aynı boyutta ek bir bellek alanı gerektirir.
Yöntem, sayılar veya dizeler gibi karşılaştırılabilir herhangi bir veri türünü sıralamak için kullanılabilir.
Birleştirme sıralandıarsa
Algoritmayı anlamak için, analizine sondan başlayalım - sıralanmış blokları birleştirme mekanizmasından.
Sıralamanın bozulmaması için birbiriyle birleştirilmesi gereken herhangi bir şekilde sıralanmış iki sayı dizimiz olduğunu düşünelim. Basit olması için sayıları artan düzende sıralayacağız.
Temel örnek: her iki dizi de birer elemandan oluşur.
int arr1={31}; int dizi2={18};
Onları birleştirmek için, ilk dizinin sıfır öğesini (numaralandırmanın sıfırdan başladığını unutmayın) ve ikinci dizinin sıfır öğesini almanız gerekir. Bunlar sırasıyla 31 ve 18'dir. Sıralama koşuluna göre 18 sayısı daha küçük olduğu için önce gelmelidir. Sadece sayıları doğru sıraya koyun:
int sonuç={18, 31};
Her dizinin birkaç öğeden oluştuğu daha karmaşık bir örneğe bakalım:
int arr1={2, 17, 19, 45}; int dizi2={5, 6, 21, 30};
Birleştirme algoritması, daha küçük öğeleri sırayla karşılaştırmaktan ve bunları elde edilen diziye doğru sırada yerleştirmekten oluşacaktır. Mevcut endeksleri takip etmek için iki değişkeni tanıtalım - index1 ve index2. Başlangıçta, diziler sıralandığından ve en küçük elemanlar başlangıçta olduğu için onları sıfıra ayarladık.
int index1=0; int dizin2=0;
Tüm birleştirme işlemini adım adım yazalım:
- dizin1'e sahip öğeyi arr1 dizisinden ve dizin2'ye sahip öğeyi arr2 dizisinden alın.
- Karşılaştır, en küçüğünü seç ve girsonuçtaki dizi.
- Daha küçük öğenin mevcut dizinini 1 ile artırın.
- İlk adımdan devam edin.
İlk yörüngede durum şöyle görünecek:
index1=0; indeks2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; dizin1++; sonuç[0]=arr1[0]; // sonuç=[2]
İkinci dönüşte:
index1=1; indeks2=0; dizi1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; indeks2++; sonuç[1]=arr2[0]; // sonuç=[2, 5]
Üçüncü:
index1=1; indeks2=1; dizi1[1]=17; dizi2[1]=6; arr1[1] > arr2[1]; indeks2++; sonuç[2]=dizi2[1]; // sonuç=[2, 5, 6]
Ve böylece, sonuç tamamen sıralanmış bir dizi olana kadar: {2, 5, 6, 17, 21, 19, 30, 45}.
Farklı uzunluklardaki diziler birleştirilirse bazı zorluklar ortaya çıkabilir. Ya mevcut dizinlerden biri son öğeye ulaştıysa ve ikinci dizide hala üyeler varsa?
int arr1={1, 4}; int dizi2={2, 5, 6, 7, 9}; // 1 adım indeks1=0, indeks2=0; 1 2 sonuç={1, 2}; // 3 adım indeks1=1, indeks2=1; 4 < 5 sonuç={1, 2, 4}; // adım indeks1=2, indeks2=1 ??
İndeks1 değişkeni 2 değerine ulaştı, ancak arr1 dizisinde bu dizine sahip bir öğe yok. Burada her şey basit: sadece ikinci dizinin kalan öğelerini sıralarını koruyarak ortaya çıkan diziye aktarın.
sonuç={1, 2, 4, 5, 6, 7, 9};
Bu durum bize ihtiyacın olduğunu gösteriyor.geçerli kontrol dizinini birleştirilecek dizinin uzunluğuyla eşleştirin.
Farklı uzunluklarda sıralı diziler (A ve B) için birleştirme şeması:
- Her iki dizinin uzunluğu 0'dan büyükse, A[0] ve B[0]'ı karşılaştırın ve daha küçük olanı arabelleğe taşıyın.
- Dizilerden birinin uzunluğu 0 ise, ikinci dizinin kalan elemanlarını alın ve sıralarını değiştirmeden arabelleğin sonuna gidin.
İkinci aşamanın uygulanması
Java'da iki sıralı diziyi birleştirme örneği aşağıda verilmiştir.
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.uzunluk + a2.uzunluk]; int i=0, j=0; for (int k=0; k a1.uzunluk-1) { int a=a2[j]; a3[k]=bir; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=bir; ben++; } else if (a1 < a2[j]) { int a=a1; a3[k]=bir; ben++; } başka { int b=a2[j]; a3[k]=b; j++; } }
Burada:
- a1 ve a2 birleştirilecek orijinal sıralanmış dizilerdir;
- a3 – son dizi;
- i ve j, a1 ve a2 dizileri için geçerli öğelerin dizinleridir.
Birinci ve ikinci if koşulları, dizinlerin dizinin boyutunu aşmamasını sağlar. Sırasıyla üçüncü ve dördüncü koşul blokları, daha küçük öğenin sonuç dizisine taşınır.
Böl ve Yönet
Yani, sıralananları birleştirmeyi öğrendik.değer koleksiyonları. Birleştirme sıralama algoritmasının ikinci bölümünün - birleştirmenin kendisi - zaten sıralanmış olduğu söylenebilir.
Ancak, orijinal sıralanmamış sayı dizisinden birleştirilebilecek birkaç sıralı sayıya nasıl ulaşacağınızı anlamanız gerekir.
Algoritmanın ilk aşamasını ele alalım ve dizileri nasıl ayıracağımızı öğrenelim.
Bu zor değil - orijinal değer listesi yarıya bölünür, ardından her parça da çatallanır ve bu çok küçük bloklar elde edilene kadar devam eder.
Böyle minimal öğelerin uzunluğu bire eşit olabilir, yani kendileri sıralanmış bir dizi olabilir, ancak bu gerekli bir koşul değildir. Bloğun boyutu önceden belirlenir ve küçük boyutlu dizilerle verimli bir şekilde çalışan herhangi bir uygun sıralama algoritması (örneğin, hızlı sıralama veya ekleme sıralama) onu sıralamak için kullanılabilir.
Öyle görünüyor.
// orijinal dizi {34, 95, 10, 2, 102, 70}; // ilk bölme {34, 95, 10} ve {2, 102, 70}; // ikinci bölme {34} ve {95, 10} ve {2} ve {102, 70}
1-2 elemandan oluşan elde edilen blokların düzenlenmesi çok kolaydır.
Ardından, zaten sıralanmış küçük dizileri, daha önce yapmayı öğrendiğimiz üyelerin sırasını koruyarak çiftler halinde birleştirmeniz gerekir.
İlk aşamanın uygulanması
Bir dizinin özyinelemeli bölümlenmesi aşağıda gösterilmiştir.
void mergeSort(T a, uzun başlangıç, uzun bitiş) { uzun bölme; Eğer(başlangıç < bitiş) { bölme=(başlangıç + bitiş)/2; mergeSort(a, başlat, böl); mergeSort(a, split+1, bitiş); birleştirme(a, başlat, böl, bitir); } }
Bu kodda ne olur:
-
mergeSort işlevi,
a
başlangıç dizisini ve sıralanacak bölgenin sol ve sağ kenarlıklarını alır (endeksler başlar ve
- finish).
-
Bu bölümün uzunluğu birden fazlaysa (
start < bitiş
), o zaman iki parçaya bölünür (dizine göre
- split) ve her biri özyinelemeli olarak sıralanır.
-
Sol taraf için özyinelemeli işlev çağrısında, grafiğin başlangıç dizini ve
split
dizini iletilir. Sağdaki için sırasıyla başlangıç
- (split + 1) olacak ve son orijinal bölümün son dizini olacaktır.
-
Function
merge
iki sıralı dizi alır (
a[start]…a[split]
ve
- a[split +1]…a[finish]) ve bunları sıralama düzeninde birleştirir.
Birleştirme işlevinin mekaniği yukarıda tartışılmıştır.
Algoritmanın genel şeması
Birleştirme sıralama dizisi yöntemi iki büyük adımdan oluşur:
- Sıralanmamış orijinal diziyi küçük parçalara ayırın.
- Sıralama kuralına uyarak onları çiftler halinde toplayın.
Geniş ve karmaşık bir görev, birçok basit göreve bölünür ve bunlar sırayla çözülerek istenen sonuca ulaşır.
Yöntem değerlendirmesi
Birleştirme sıralamasının zaman karmaşıklığı, bölünmüş ağacın yüksekliğine göre belirleniralgoritmadır ve dizideki eleman sayısı (n) ile logaritmasının (log n) çarpımına eşittir. Böyle bir tahmine logaritmik denir.
Bu, yöntemin hem avantajı hem de dezavantajıdır. Orijinal dizi ters sırada sıralandığında, en kötü durumda bile çalışma süresi değişmez. Ancak, tamamen sıralanmış verileri işlerken, algoritma bir zaman kazancı sağlamaz.
Birleştirme sıralama yönteminin bellek maliyetini de not etmek önemlidir. Orijinal koleksiyonun boyutuna eşittirler. Ek olarak tahsis edilen bu alanda, parçalardan bir sıralı dizi oluşturulur.
Algoritmanın uygulanması
Pascal birleştirme sıralaması aşağıda gösterilmiştir.
Procedure MergeSort(ad: dize; var f: metin); Var a1, a2, s, i, j, kol, tmp: tamsayı; f1, f2: metin; b: boole Başla:=0; Ata(f, isim); sıfırla(f); EOF(f) olmasa da read(f, a1); inc(sütun); son; kapat(f); Assign(f1, '{1. yardımcı dosyanın adı}'); Assign(f2, '{2. yardımcı dosyanın adı}'); s:=1; (s<kol) Reset(f) başlarken; yeniden yaz(f1); yeniden yaz(f2); i:=1 ila kol div 2 için Read(f, a1); Yaz(f1, a1, ' '); son; (kol div 2) mod s0 ise, tmp:=kol div 2'ye başlayın; tmp mod s0 iken Read(f, a1); Yaz(f1, a1, ' '); inc(tmp); son; son; EOF(f) olmasa da Read(f, a2); Yaz(f2, a2, ' '); son; kapat(f); kapat(f1); kapat(f2); yeniden yaz(f); sıfırla(f1); sıfırla(f2); Oku(f1, a1); Oku(f2, a2); while (EOF(f1) değil) ve (EOF(f2) değil) i:=0; j:=0; b:=doğru; (b) ve (EOF(f1) değil) ve (EOF(f2) değil) başlarken (a1<a2) o zaman başlarsaYaz(f, a1, ' '); Oku(f1, a1); inc(i); End else start Write(f, a2, ' '); Oku(f2, a2); inc(j); son; (i=s) veya (j=s) ise b:=yanlış; son; Eğer b değilse, o zaman başlayın While (i<s) ve (EOF(f1) değil) başlayın Write(f, a1, ' '); Oku(f1, a1); inc(i); son; (j<s) ve (EOF(f2) değil) Write(f, a2, ' '); Oku(f2, a2); inc(j); son; son; son; EOF(f1) olmasa da tmp:=a1; Oku(f1, a1); EOF(f1) değilse Write(f, tmp, ' ') değilse Write(f, tmp); son; EOF(f2) olmasa da tmp:=a2; Oku(f2, a2); EOF(f2) değilse Write(f, tmp, ' ') değilse Write(f, tmp); son; kapat(f); kapat(f1); kapat(f2); s:=s2; son; Sil(f1); Sil(f2); Bitiş;
Görsel olarak, algoritmanın işleyişi şu şekildedir (üst - sırasız sıra, alt - sıralı).
Harici veri sıralama
Çoğu zaman bilgisayarın harici belleğinde bulunan bazı verileri sıralamaya ihtiyaç duyulur. Bazı durumlarda, etkileyici boyuttadırlar ve bunlara erişimi kolaylaştırmak için RAM'e yerleştirilemezler. Bu gibi durumlar için harici sıralama yöntemleri kullanılır.
Harici medyaya erişim ihtiyacı, işlem süresinin verimliliğini düşürür.
İşin karmaşıklığı, algoritmanın aynı anda veri akışının yalnızca bir öğesine erişebilmesidir. Ve bu durumda, en iyi sonuçlardan biri, iki dosyanın öğelerini birbiri ardına sıralı olarak karşılaştırabilen birleştirme sıralama yöntemiyle gösterilir.
Veri okumadış kaynak, işlenmesi ve nihai dosyaya yazılması sıralı bloklar (seri) halinde gerçekleştirilir. Sıralı serilerin boyutuyla çalışma şekline göre iki tür sıralama vardır: basit ve doğal birleştirme.
Basit birleştirme
Basit bir birleştirme ile seri uzunluğu sabitlenir.
Böylece, orijinal sıralanmamış dosyada tüm seriler tek bir öğeden oluşur. İlk adımdan sonra, boyut ikiye çıkar. Sonraki - 4, 8, 16 vb.
Şu şekilde çalışır:
- Kaynak dosya (f) iki yardımcı dosyaya bölünmüştür - f1, f2.
- Yine tek bir dosyada (f) birleştirilirler, ancak aynı zamanda tüm öğeler çiftler halinde karşılaştırılır ve çiftler oluşturur. Bu adımda seri boyutu iki olur.
- 1. Adım tekrarlanır.
- Adım 2 tekrarlanır, ancak önceden sıralanmış 2'ler sıralı 4'ler oluşturmak için birleştirilir.
- Döngü, tüm dosya sıralanana kadar her yinelemede seriyi artırarak devam eder.
Basit bir birleştirme ile dış sıralamanın tamamlandığını nereden biliyorsunuz?
- yeni dizi uzunluğu (birleştirmeden sonra) toplam öğe sayısından az değil;
- sadece bir bölüm kaldı;
- Yardımcı dosya f2 boş bırakıldı.
Basit bir birleştirmenin dezavantajları şunlardır: çalıştırma uzunluğu her birleştirme geçişinde sabit olduğundan, kısmen sıralı verilerin işlenmesi tamamen rastgele veriler kadar uzun sürer.
Doğal füzyon
Bu yöntem uzunluğu sınırlamazancak mümkün olan maksimumu seçer.
Sıralama algoritması:
- F dosyasından ilk diziyi okuma. İlk alınan eleman f1 dosyasına yazılır.
- Bir sonraki giriş sıralama koşulunu sağlıyorsa oraya, değilse ikinci yardımcı dosya f2'ye yazılır.
- Bu şekilde, kaynak dosyanın tüm kayıtları dağıtılır ve f1'de serinin mevcut boyutunu belirleyen sıralı bir dizi oluşturulur.
- F1 ve f2 dosyaları birleştirilir.
- Döngü tekrarlanır.
Dizilerin boyutu sabit olmadığı için dizinin sonunu özel bir karakterle işaretlemek gerekir. Bu nedenle, birleştirme sırasında karşılaştırma sayısı artar. Ayrıca, yardımcı dosyalardan birinin boyutu orijinalin boyutuna yakın olabilir.
Ortalama olarak, doğal birleştirme, harici sıralama ile basit birleştirmeden daha verimlidir.
Algoritmanın özellikleri
İki özdeş değeri karşılaştırırken, yöntem orijinal sırasını korur, yani kararlıdır.
Sıralama işlemi çok başarılı bir şekilde birden çok iş parçacığına bölünebilir.
Video, birleştirme sıralama algoritmasının çalışmasını açıkça göstermektedir.
