Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Birleşmeli Sıralama (Merge Sort), bilgisayar bilimlerinde derecesinde karmaşıklığa sahip bir sıralama algoritmasıdır.
| Birleştirmeli sıralama | |
|---|---|
 Birleştirmeli sıralama'nın rastgele üretilmiş sayıları gösteren noktaları nasıl sıraladığını gösteren örnek | |
| Sınıf | Sıralama algoritması |
| Veri yapısı | Dizi |
| Zaman karmaşıklığı | O(n log n) |
| En iyi | Genellikle |
| Alan karmaşıklığı | En kötü durumda О(n) |
Girdi olarak aldığı diziyi en küçük hale gelene kadar ikili gruplara böler ve karşılaştırma yöntemi kullanarak diziyi sıralar.
Algoritmanın çalışması kavramsal olarak şöyledir:
- Sıralı olmayan listeyi ortadan eşit olarak iki alt listeye ayırır.
- Alt listeleri kendi içinde sıralar.
- Sıralı iki alt listeyi tek bir sıralı liste olacak şekilde birleştirir.
Bu algoritma John von Neumann tarafından 1945 yılında bulunmuştur. Sözde kod formatındaki bir algoritma örneği aşağıdaki gibidir.
function mergesort(m) var list left, right if length(m) ≤ 1 return m else 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 = mergesort(left) right = mergesort(right) result = merge(left, right) return result
Yukarıda kullanılan merge() fonksiyonunun değişik şekilleri olabilir. Bunlardan en basiti şöyledir.
function merge(left,right) var list result while 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) if length(left) > 0 append left to result if length(right) > 0 append right to result return result
Karmaşıklık Hesabı
Birleştirme sıralaması böl ve yönet algoritmasına güzel bir örnektir. Algoritma her adımda diziyi ikiye bölüp en küçük birime geldiğinde bu alt dizileri sıralar ve daha sonra sıralanmış alt dizileri birleştirerek sonuca varır. Birleştirme sıralamasının karmaşıklığını hesaplamak için sıralanacak N elemanlı diziyi bir ağaç yapısına taşıyınca her bir düğüm bir alt diziyi temsil eder. Ağaç tam olarak n seviye içerir. k sayısı 0'dan n-1'e kadar ağaç seviyesini temsil etsin, yukarıdan aşağıya doğru ağacın k. seviyesinde 
tane düğüm bulunur. Bu düğümlerin her biri 
uzunluğunda bir alt diziyi temsil eder. Bir alt dizinin eleman sayısı olduğu için en fazla karşılaştırma yapılabilir.
Ağacın her seviyesindeki alt dizi sayısı ve yapılabilecek en fazla karşılaştırma sayısı 
' dır.
n seviye ağaç için toplam 
karşılaştırma yapılır. Elde edilen değerinin asimptotik üst sınırı 
değeridir.
Analiz
Birleştirme sıralaması örneğinde rastgele sayılardan oluşan bir liste sıralanıyor. Örnek olarak N adet elemanın sıralandığını düşünelim. Birleştirme sıralamasının ortalama durum ve en kötü durum olarak iki analizi vardır. Uzunluğu n olan bir liste üzerinde birleştirme sıralamasının işletim zamanı 
olsun. Bu sıralama bölünen alt listelere tekrarlı olarak uygulanırsa algoritmanın tanımından 
olur (Algoritmayı 2 alt listeye uygula ve birleşimden doğacak N basamağı ekle). Daha geniş bir analiz için master teoremine bakınız.
En kötü durum analizinde 
olur. Bu da 
ile 
arasındadır. Bazı alt listelerin sıralanmış geldiğini düşünürsek ve n sayısı çok büyükken yapılan karşılaştırma sayısı en kötü durumdan x.n kez daha azdır. {x≈0,2645}
Birleştirme sıralaması en kötü durum performansında bile ortalama durumda çalışan bir hızlı sıralama algoritmasından %39 civarında daha az karşılaştırma yapar. İki algoritmanın eş zamanlı olarak çalıştığı durumda yani birleştirme sıralamasının en kötü durum performansı hızlı sıralamanın en iyi durumuna eşit olduğunda iki algoritmanın da karmaşıklığı Q(N logN) olarak eşittir. Birleştirme sıralamasının en iyi durumu en kötü durumun yarısı kadar karşılaştırma yapar.
Birleştirme sıralama fonksiyonu çağrıldığında, diziyi ikiye bölüp sadece iki diziyi sıraladığını düşünürsek oluşan her alt dizi için fonksiyonu tekrar tekrar çağırmamız gerekir. Bu da fonksiyonun 2N –l kez işlem görmesi demektir. Hızlı sıralama ise en kötü durumda bile N kez işlem görür. Bu durumda birleştirme sıralamasının hızlı sıralamaya oranla neredeyse iki kat bir maliyeti ortaya çıkar. Bundan sakınmak için fonksiyonun içine kendi kendini çağıran interatif bir yapı koymak basit ve etkili bir çözümdür. Genellikle birleştirme sıralaması uygulamalarında verinin son hali girdi için ayrılan alana kaydedildiğinden bellekte ayrıca bir yer kaplamaz. Sıralama işlemini başka bir bellek alanında yapmak da mümkündür. Fakat bu oldukça karmaşıktır. Bu işlem performans olarak kazançlı olsa bile algoritma işletim zamanı hala Q(NlogN)'dir. Bu tip durumlarda algoritma algoritması gibi çalışır. Sıralı erişim prensibine göre çalışan veri yapılarında birleştirme sıralaması hızlı sıralamaya oranla daha etkilidir.
Birleştirme sıralamasının optimizasyonu
Günümüz modern bilgisayarlarında yazılım optimizasyonunda çok önemlidir. Bunun nedeni günümüzdeki çok katlı bellek sıradüzenselliğinin kullanımıdır.
Bir anlayışa göre ana RAM hızlı bir kaset sürücü gibi düşünülebilir. Ve daha hızlı olan ön bellekler. Ön belleğin tekrar tekrar yüklenmesi kabul edilemez zaman kayıplarını dayatmaktadır. Bu nedenle titiz bir birleştirme sıralaması işletim zamanında olumlu iyileştirmeler yapar. Fakat bu düşünce çok hızlı bellek elemanlarının ucuzlaması ve mimari de daha yaygın olarak kullanılmasıyla tersine de dönebilir.
Sonuç olarak bir birleştirme sıralaması tasarlamak, donanımsal değişiklikler gerektirir. Örneğin kaset sürücülerinin sayısında boyutunda veya hızında bazı değişiklikler yapılmalıdır.
Algoritmanın kodları
void Merge(int Alt, int Ust) { if(Alt < Ust) return; int AltSinir= Alt; int UstSinir= Ust; int Pivot=(AltSinir+UstSinir)/2; Merge(AltSinir,Pivot); Merge(Pivot+1,UstSinir); int end_AltSinir=Pivot; int start_UstSinir=Pivot+1; while(( AltSinir<=end_AltSinir)&&(start_UstSinir<= UstSinir)) { if(Dizi[AltSinir]<Dizi[start_UstSinir]) AltSinir++; else { int T=AnaForm ->SIRALA[start_UstSinir]; for( int k=start_UstSinir-1;k >= AltSinir; k--) Dizi[k+1]=Dizi[k]; Dizi[AltSinir]=T; AltSinir++; end_AltSinir++; start_UstSinir++; } } } Kaynakça
- ^ Robert Sedgewick, Kevin Wayne, Algorithms 4th Edition, Addison-Wesley 2011 (chapter 2 p. 274)
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Birlesmeli Siralama Merge Sort bilgisayar bilimlerinde O n log n displaystyle mathcal O n log n derecesinde karmasikliga sahip bir siralama algoritmasidir Birlestirmeli siralamaBirlestirmeli siralama nin rastgele uretilmis sayilari gosteren noktalari nasil siraladigini gosteren ornekSinifSiralama algoritmasiVeri yapisiDiziZaman karmasikligiO n log n En iyiGenellikleAlan karmasikligiEn kotu durumda O n Girdi olarak aldigi diziyi en kucuk hale gelene kadar ikili gruplara boler ve karsilastirma yontemi kullanarak diziyi siralar AlgoritmaAlgoritmanin calismasi kavramsal olarak soyledir Sirali olmayan listeyi ortadan esit olarak iki alt listeye ayirir Alt listeleri kendi icinde siralar Sirali iki alt listeyi tek bir sirali liste olacak sekilde birlestirir Bu algoritma John von Neumann tarafindan 1945 yilinda bulunmustur Sozde kod formatindaki bir algoritma ornegi asagidaki gibidir function mergesort m var list left right if length m 1 return m else 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 mergesort left right mergesort right result merge left right return result Yukarida kullanilan merge fonksiyonunun degisik sekilleri olabilir Bunlardan en basiti soyledir function merge left right var list result while length left gt 0 and length right gt 0 if first left first right append first left to result left rest left else append first right to result right rest right if length left gt 0 append left to result if length right gt 0 append right to result return resultKarmasiklik HesabiBirlestirme siralamasi bol ve yonet algoritmasina guzel bir ornektir Algoritma her adimda diziyi ikiye bolup en kucuk birime geldiginde bu alt dizileri siralar ve daha sonra siralanmis alt dizileri birlestirerek sonuca varir Birlestirme siralamasinin karmasikligini hesaplamak icin siralanacak N elemanli diziyi bir agac yapisina tasiyinca her bir dugum bir alt diziyi temsil eder Agac tam olarak n seviye icerir k sayisi 0 dan n 1 e kadar agac seviyesini temsil etsin yukaridan asagiya dogru agacin k seviyesinde 2k textstyle 2 k tane dugum bulunur Bu dugumlerin her biri 2n k textstyle 2 n k uzunlugunda bir alt diziyi temsil eder Bir alt dizinin eleman sayisi 2n k textstyle 2 n k oldugu icin en fazla 2n k textstyle 2 n k karsilastirma yapilabilir Agacin her seviyesindeki alt dizi sayisi ve yapilabilecek en fazla karsilastirma sayisi 2k 2n k 2n textstyle 2 k 2 n k 2 n dir n seviye agac icin toplam n 2n textstyle n 2 n karsilastirma yapilir Elde edilen n 2n textstyle n 2 n degerinin asimptotik ust siniri O NlgN displaystyle O NlgN degeridir AnalizBirlestirme siralamasi orneginde rastgele sayilardan olusan bir liste siralaniyor Ornek olarak N adet elemanin siralandigini dusunelim Birlestirme siralamasinin ortalama durum ve en kotu durum olarak iki analizi vardir Uzunlugu n olan bir liste uzerinde birlestirme siralamasinin isletim zamani T N textstyle T N olsun Bu siralama bolunen alt listelere tekrarli olarak uygulanirsa algoritmanin tanimindan T N 2T N 2 N textstyle T N 2T N 2 N olur Algoritmayi 2 alt listeye uygula ve birlesimden dogacak N basamagi ekle Daha genis bir analiz icin master teoremine bakiniz En kotu durum analizinde NlgN 2lgN 1 textstyle NlgN 2lgN 1 olur Bu da NlgN N 1 textstyle NlgN N 1 ile NlgN N O lgN textstyle NlgN N O lgN arasindadir Bazi alt listelerin siralanmis geldigini dusunursek ve n sayisi cok buyukken yapilan karsilastirma sayisi en kotu durumdan x n kez daha azdir x 0 2645 Birlestirme siralamasi en kotu durum performansinda bile ortalama durumda calisan bir hizli siralama algoritmasindan 39 civarinda daha az karsilastirma yapar Iki algoritmanin es zamanli olarak calistigi durumda yani birlestirme siralamasinin en kotu durum performansi hizli siralamanin en iyi durumuna esit oldugunda iki algoritmanin da karmasikligi Q N logN olarak esittir Birlestirme siralamasinin en iyi durumu en kotu durumun yarisi kadar karsilastirma yapar Birlestirme siralama fonksiyonu cagrildiginda diziyi ikiye bolup sadece iki diziyi siraladigini dusunursek olusan her alt dizi icin fonksiyonu tekrar tekrar cagirmamiz gerekir Bu da fonksiyonun 2N l kez islem gormesi demektir Hizli siralama ise en kotu durumda bile N kez islem gorur Bu durumda birlestirme siralamasinin hizli siralamaya oranla neredeyse iki kat bir maliyeti ortaya cikar Bundan sakinmak icin fonksiyonun icine kendi kendini cagiran interatif bir yapi koymak basit ve etkili bir cozumdur Genellikle birlestirme siralamasi uygulamalarinda verinin son hali girdi icin ayrilan alana kaydedildiginden bellekte ayrica bir yer kaplamaz Siralama islemini baska bir bellek alaninda yapmak da mumkundur Fakat bu oldukca karmasiktir Bu islem performans olarak kazancli olsa bile algoritma isletim zamani hala Q NlogN dir Bu tip durumlarda algoritma algoritmasi gibi calisir Sirali erisim prensibine gore calisan veri yapilarinda birlestirme siralamasi hizli siralamaya oranla daha etkilidir Birlestirme siralamasinin optimizasyonuGunumuz modern bilgisayarlarinda yazilim optimizasyonunda cok onemlidir Bunun nedeni gunumuzdeki cok katli bellek siraduzenselliginin kullanimidir Bir anlayisa gore ana RAM hizli bir kaset surucu gibi dusunulebilir Ve daha hizli olan on bellekler On bellegin tekrar tekrar yuklenmesi kabul edilemez zaman kayiplarini dayatmaktadir Bu nedenle titiz bir birlestirme siralamasi isletim zamaninda olumlu iyilestirmeler yapar Fakat bu dusunce cok hizli bellek elemanlarinin ucuzlamasi ve mimari de daha yaygin olarak kullanilmasiyla tersine de donebilir Sonuc olarak bir birlestirme siralamasi tasarlamak donanimsal degisiklikler gerektirir Ornegin kaset suruculerinin sayisinda boyutunda veya hizinda bazi degisiklikler yapilmalidir Algoritmanin kodlarivoid Merge int Alt int Ust if Alt lt Ust return int AltSinir Alt int UstSinir Ust int Pivot AltSinir UstSinir 2 Merge AltSinir Pivot Merge Pivot 1 UstSinir int end AltSinir Pivot int start UstSinir Pivot 1 while AltSinir lt end AltSinir amp amp start UstSinir lt UstSinir if Dizi AltSinir lt Dizi start UstSinir AltSinir else int T AnaForm gt SIRALA start UstSinir for int k start UstSinir 1 k gt AltSinir k Dizi k 1 Dizi k Dizi AltSinir T AltSinir end AltSinir start UstSinir Kaynakca Robert Sedgewick Kevin Wayne Algorithms 4th Edition Addison Wesley 2011 chapter 2 p 274