Çok sık kullanılan, karşılaştırmaya dayalı bir sıralama algoritmasıdır. zamanda gerçekleşir. Uzun zaman aldığından, büyük veri paketlerinde kullanılmamasına dikkat edilmelidir. Çalışma sistemine gelince: Arka kısımda 2li sıralama ağacı kullanır. Tüm sıralama işlemlerini bu ağaç üzerinde gerçekleştirir. Algoritma, verilen veri kümesini 2li ağaca çevirir. Bu işlemi yaparken herhangi bir koşul gözetilmez, elemanlar ağaca sırayla eklenir. Fakat ağaç oluşturduktan sonra ağacın en son elemanından başlayarak köke kadar tüm elemanları tarayarak, ağacın bir MAX ya da MIN HEAP ağacı olması sağlarız. (Bu kadarı, sıralamamızı azalan ya da artan olması durumuna göre karar veririz.). Bu işlemden sonra en sondaki eleman ile kök elemanının yerlerini değiştirilir ve en son yaprak ağaçtan koparılır. Sıralama, yer değiştirme ve koparma işlemleri, ağaçta sadece kök elemanı kalana kadar tekrarlanır. Koparılan elemanlar konduğu sırada listeye geri alınır. Böylece sıralama yapılmış olur. Pseudocode: Build Max Heap: BUILD-MAX-HEAP(A)     heap-size[A] ← length[A]     for i ← floor(length[A]/2) downto1         do              MAX-HEAPIFY(A, i) Max Heapify: MAX-HEAPIFY(A, i)     l ← LEFT(i)     r ← RIGHT(i)     if l ≤ heap-size[A] and A[l] > A[i]         then largest ← l         else largest ← i     if r ≤ heap-size[A] and A[r] > A[largest]         then largest ← r     if largest ≠ i         then exchange A[i] ↔ A[largest]             MAX HEAPIFY(A, largest) Sıralama örneği: Bize verilen dizi: 4 1 3 2 16 9 10 14 8 7 2li ağacımızı oluşturalım: Ağacı düzenleyelim (sıralama):   Ağacın son elemanı ile kökü yer değiştirelim, ve son düğümü ağaçtan kopartalım. Ağacın en son hali: Örnek C++ kodu: void heapsort(int *a, int size) { int i, temp; for (i = (size / 2)-1; i >= 0; i--) heapify(a, i, size - 1); for (i = size-1; i >= 1; i--) { temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, 0, i-1); } } void heapify(int *a, int root, int bottom) { int done, maxChild, temp; done = 0; while ((root*2 <= bottom) && (!done)) { if (root*2 == bottom) maxChild = root * 2; else if (a[root * 2] > a[root * 2 + 1]) maxChild = root * 2; else maxChild = root * 2 + 1; if (a[root] < a[maxChild]) { temp = a[root]; a[root] = a[maxChild]; a[maxChild] = temp; root = maxChild; } else done = 1; } } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Kaynak: İ.T.Ü. 2009 – 2010 Güz Dönemi, Advanced Data Structures dersi ders notları, Z.Çataltepe & S.Kabadayı Tags: , | Categories: Algoritma | C++
Özellikler: Uygulaması kolaydır. Küçük Veri kümeleri üzerinde kullanıldığında verimlidir. Çoğunluğu zaten sıralanmış olan diziler üzerinde kullanıldığında verimlidir. Karmaşıklığı seçmeli sıralama ve kabarcık sıralaması gibi çoğu yalın sıralama algoritmalarından daha verimlidir. Kararlı bir sıralama algoritmasıdır (değeri eşit olan öğelerin asıl listedeki göreceli konumlarını değiştirmez) Sıralanacak diziyi yerinde sıralar, ek bir bellek alanı gerektirmez. Sıralanacak dizinin hepsinin algoritmanın girdisi olmasına gerek yoktur. Dizi parça parça da alınabilir ve sıralama işlemi sırasında diziye yeni veriler eklenebilir.   Çalışma mantığı çok basittir: Sıralanmak istenen dizinin en başındaki elemandan en sonundakine kadar tüm verileri tek tek kontrol eder ve gerekli yerlere yerleştirir. Kontrol edeceğimiz değerimizi geçici olarak kaydederiz. Daha sonra kontrol ettiğimiz eleman indisinden itibaren geriye doğru gideriz. Eğer, geçici olarak tuttuğumuz değer, o anda üzerinde bulunduğumuz değerden küçükse, bir basamak önce üzerinde olduğumuz yere yazarız. Bu sayede sayıyı bir sağa kaydırmış oluruz. Fakat daha sonrasında geçici olarak tuttuğumuz (kontrol edilen) değeri şu anda üzerinde bulunduğumuz yere yazmamız gerekmektedir. Kısaca dizinin başından sonuna doğru giderken Bir şekilde anlatmak gerekirse:   Pseudocode: insertionSort(array A) begin for i := 1 to length[A]-1 do begin value := A[i]; j := i - 1; while A[j] > value do begin A[j + 1] := A[j]; j := j - 1; if j < 0 then exit while; end; A[j + 1] := value; end; end;   Örnek C++ Kodu: void insertionsort(int *a, int n) { int i, j, t; for (i=1; i<n; i++) { j=i; t=*(a+j); while (j>0 && *(a+j-1)>t) { *(a+j)=*(a+j-1); j--; } *(a+j)=t; } }   Kaynaklar: www.wikipedia.org www.javacoffeebreak.com .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Tags: , | Categories: Algoritma | C++

Ocak 1007

B Ağacı (B Tree)

Bilgisayar bilimlerinde bir B ağacı, veri sıralaması tutar ve logaritmik azalan zamanda ağaç yapısında ekleme, çıkartma ve arama işlemlerine izin verir. B ağaçları ikili sıralama ağaçlarının daha genel halidir. Özelikleri: Her B ağacının m değerinde bir faktör değeri vardır (m>1 koşulu sağlanmalıdır). Her düğümde en fazla m adet çocuk bulunmalıdır. m sayısından daha fazla çocuk olması durumunda düğüm parçalanır. Kök ve yaprak düğümleri haricinde en az m/2 adet eleman bulunmalıdır. Aksi takdirde diğer düğümlerle birleştirme işlemi uygulanır. Ağacın derinliği her yaprak için aynı olmalıdır. Her bir düğümde k çocuk bulunuyorsa k-1 sayıda elemanı gösteren anahtar (key) bulunmalıdır.   Örnek B ağacı aşağıdaki şekildeki gibidir:   B ağacı üzerindeki işlemler: B-Tree-Search(x, k) i <- 1while i <= n[x] and k > keyi[x]     do i <- i + 1if i <= n[x] and k = keyi[x]     then return (x, i)if leaf[x]     then return NIL     else Disk-Read(ci[x])          return B-Tree-Search(ci[x], k) B ağacındaki arama ikili araçtaki arama ile benzerdir. Arama sırasında sağ - sol taraf seçenekleri yerine n tane farklı taraf vardır. Düğüm içerisinde lineer bir arama yapılarak doğru çocuk düğüme yönlenebilir. İstenilen değere küçük eşit değer bulunduktan sonra, bulunan key değerinin sol tarafındaki çocuk düğüme gidilir. Eğer Düğümdeki tüm keylerin değerleri aranan değerden küçükse en sağdaki çocuk düğüme dallanılır. Aranan değer bulununca arama işlemi sonlanır. Arama sırasındaki geçen zaman ağacın derinliğine bağlı O(logt n) olarak hesaplanır. B-Tree-Create(T) x <- Allocate-Node()leaf[x] <- TRUEn[x] <- 0Disk-Write(x)root[T] <- x Boş B ağacı yaratma işlemidir. Çocuk düğümü olmayan kök düğümü yaratır. B-Tree-Create işlemi O(1) zamanda koşulur. B-Tree-Insert(T, k) r <- root[T]if n[r] = 2t – 1     then s <- Allocate-Node()          root[T] <- s          leaf[s] <- FALSE          n[s] <- 0          c1 <- r          B-Tree-Split-Child(s, 1, r)          B-Tree-Insert-Nonfull(s, k)     else B-Tree-Insert-Nonfull(r, k) B-Tree-Split-Child(x, i, y) z <- Allocate-Node()leaf[z] <- leaf[y]n[z] <- t – 1for j <- 1 to t – 1     do keyj[z] <- keyj+t[y]if not leaf[y]     then for j <- 1 to t          do cj[z] <- cj+t[y]n[y] <- t – 1for j <- n[x] + 1 downto i + 1     do cj+1[x] <- cj[x]ci+1 <- zfor j <- n[x] downto i     do keyj+1[x] <- keyj[x]keyi[x] <- keyt[y]n[x] <- n[x] + 1Disk-Write(y)Disk-Write(z)Disk-Write(x) Eğer düğümdeki eleman sayısı faktör değerine ulaşmışsa ayırma işlemi uygulanması gerekir. Ayırma işlemi, tümüyle dolu bir düğümü 2t-1 key), 2 adet düğüme (t-1 key) dönüştürür. Unutulmamalıdır ki, ayırma işlemi ile bir tane key ebeveyn düğüme kayar. Ayırma işlemi O(t) kadar zamanda gerçekleşir. B-Tree-Delete(x) B ağaçları için silme işlemi mümkündür. Fakat diğer işlemlere nazaran daha çok dikkat gerektiren bir işlemdir. Çünkü çıkartma işlemi sonrasında eğer key sayısı koşulumuzu sağlamıyorsa düğümlerde birleştirme işlemi yapılmalıdır. Fakat bu durumda da ağacın dengeli olmasına (derinliğinin her yaprak için aynı olmasına) dikkat edilmelidir.   Bu kadar yazı okudunuz. Ancak B Tree nin B’sinin neyin kısaltması olduğundan hiç biryerde bahsetmedim. Bahsedememem de zaten. Bu algoritmayı yazandan başka kimse bilmiyor bunu. Sadece varsayımlardan behsediliyor. Yazımın sonunda bu konu hakkında ufak bir alıntı yapmak istiyorum: The origin of "B-tree" has never been explained by the authors. ... "balanced," "broad," or "bushy" might apply. Others suggest that the "B" stands for Boeing. [Bayer and McCreight were at Boeing Scientific Research Labs in 1972.] Because of his contributions, however, it seems appropriate to think of B-trees as "Bayer"-trees.     -   Douglas Comer, The Ubiquitous B-Tree, Computing Surveys, 11(2):123, June 1979. Tags: | Categories: Algoritma