Sıralama Algoritmaları |
10-29-2012 | #1 |
Prof. Dr. Sinsi
|
Sıralama AlgoritmalarıSıralama algoritmaları Sıralama algoritması Ağaç sıralaması Basamağa göre sıralama Birleştirmeli sıralama Cüce sıralaması Eklemeli sıralama Güvercin yuvası sıralaması Hızlı sıralama Kabarcık sıralaması Kabuk sıralaması Kokteyl sıralaması Kova sıralaması Kütüphane sıralaması Rahat sıralama Sabır sıralaması Sayarak sıralama Saçma sıralama Seçmeli sıralama Sıralama Tarak sıralaması Yığın sıralaması İplik sıralaması İçgözlemle sıralama Sıralama algoritması Yığın Sıralaması'nın rastgele üretilmiş sayıları nasıl sıraladığını gösteren örnek Algoritmanın ilk aşamasında dizinin öğeleri yığın yapısını oluşturmak için yeniden düzenlenir Sıralama algoritması, bilgisayar bilimlerinde ya da matematikte kullanılan, verilen bir listenin elemanlarını belirli bir sıraya sokan algoritmadır En çok kullanılan sıralama türleri, sayı büyüklüğüne göre sıralama ve alfabetik sıralamadır Sıralama işleminin verimli yapılması, arama ve birleştirme algoritmaları gibi çalışması için sıralanmış dizilere gereksinim duyan algoritmaların başarımının yüksek olması için önemlidir Sıralama algoritmaları bilgisayarlarda tutulan verilerin düzenlenmesini ve insan kullanıcı tarafından daha rahat algılanmasını da sağlar Sıralama algoritmaları, tanımı çok yalın olmasına karşın çözümü çok karmaşık olan bir işi gerçekleştirdikleri için, üzerinde en fazla araştırma yapılan bilgisayar bilimi konularından biridir Çoğu kişi sıralama sorununu çözülmüş bir sorun olarak görse de, yeni sıralama algoritmaları üzerinde araştırmalar sürmektedir Örneğin kütüphane sıralaması ilk olarak 2004 yılında ortaya atılmıştır Sıralama algoritmaları, sayılarının çok olması ve değişik yaklaşımlar sunmaları nedeniyle özellikle giriş düzeyindeki bilgisayar bilimleri derslerinde büyük O gösterimi ve veri yapıları gibi temel algoritma kavramlarının açıklanması amacıyla yaygın biçimde kullanılırlar Birleştirmeli sıralama'nın rastgele üretilmiş sayıları gösteren noktaları nasıl sıraladığını gösteren örnek Bilgisayar bilimlerinde kullanılan sıralama algoritmaları genellikle aşağıdaki ölçütlere göre sınıflandırılır: Hesaplama karmaşıklığı: Dizideki öğelerin karşılaştırılmasının en iyi, ortalama ve en kötü başarımının dizinin boyutu (n) cinsinden gösterilmiş halidir Olağan uygulamalarda sıralama algoritmalarının iyi durum başarımı O(n log n) ve kötü durum başarımı is Ω(n²)'dir Bir sıralama algoritmasının istenen karmaşıklığı O(n)'dir Yalnızca soyut bir anahtar karşılaştırması yapan bütün sıralama algoritmaları en kötü durumda her zaman Ω(n log n) karşılaştırma yaparlar Yer Değiştirme Karmaşıklığı (yerinde sıralama algoritmaları için) Bellek (ve diğer donanım kaynaklarının) Kullanımı: Bazı sıralama algoritmaları dizinin içerdiği öğelerin dizinin saklandığı alanda sıralar Böylece sıralanan öğeler dışında yalnızca O(1) ya da O(log n)'lik bir ek bellek alanı gerekir Bazı algoritmalar ise verinin geçici olarak saklanması için dizinin tutulduğu alanın dışında ek bellek alanlarına gereksinim duyar Özyineleme: Bazı algoritmalar ya özyinelemeli ya da özyinelemesiz çalışırken, birleştirmeli sıralama gibi bazı algoritmalar iki biçimde de uygulanabilir Kararlılık Kaşılaştırma sıralaması olup olmama: Bir karşılaştırma sıralaması sıralanacak veriyi, bir karşılaştırma işlemi kullanarak, karşılaştırarak inceler Genel Yöntem: Araya sokma, değiştirme, seçme, birleştirme vb Değiştirme sıralamalarına kabarcık sıralaması ve hızlı sıralama örnek olarak gösterilebilir Yığın sıralaması ise seçme sıralamalarındandır Kararlılık Kararlı sıralama algoritmaları sıralanacak dizinin içinde değerleri birbirine eşit olan öğerlerin birbirlerine göre olan konulmlarını korur Başka bir deyişle, bir sıralama algoritması kararlı olduğunda, eğer R ve S gibi içerdiği değer aynı olan iki öğe bulunduran asıl dizide, R, S' den önce geliyorsa, sıralanmış dizide de R, S'den önce gelir Dizinin içinde birbirine eşit değerler içeren öğeler birbirlerinden ayırt edilemiyorsa (örneğin sayılar ya da harfler gibi değerler öğenin kendisini oluşturuyor ise) kararlılık bir sorun değildir Ancak aşağıda gösterildiği gibi sayı çiftleri, her çiftin virgülden önceki sayısına göre sıralanacağı düşünülürse kararlılık sorunu ortaya çıkar (4, 1) (3, 7) (3, 1) (5, 6) Bu durumda, 2 değişik sonuç mümkündür; ilk çözüm sıralama anahtarlarının değerleri aynı olan öğelerinin sırasını korur, ikincisi ise korumaz: (3, 7) (3, 1) (4, 1) (5, 6) (sıra korunmuş) (3, 1) (3, 7) (4, 1) (5, 6) (sıra değişmiş) Kararsız sıralama algoritmaları sıralama anahtarlarının değerleri aynı olan öğelerin dizi içindeki sırasını değiştirebilir ancak kararlı sıralama algoritmaları asla değiştirmez Kararsız sıralama algoritmaları özellikle kararlı olacak biçimde uygulanabilir Bunu yapmanın bir yolu yapay olarak anahtar karşılaştırmasını anahtlarının değerleri birbirine eşit olan iki öğenin durumunu belirlemek için asıl listedeki konumlarını ölçüt olarak kullanacak biçimde genişletmektir Ancak asıl dizideki öğre sırasının hatırlanması çoğu zaman ek saklama alanı gerektirir Ağaç sıralaması Ağaç sıralaması, bilgisayar bilimlerinde kullanılan, herhangi bir diziden önce bir ikili arama ağacı oluşturup ardından bu ağacın üzerinden geçerek dizinin sıralanmasını sağlayan bir sıralama algoritmasıdır Basamağa göre sıralama (İngilizcesi: Radix sort) bilgisayar bilimlerinde sayıları basamaklarının üzerinde işlem yaparak sıralayan bir sıralama algoritmasıdır Sayma sayıları adlar ya da tarihler gibi karakter dizilerini göstermek için kullanılabildiği için basamağa göre sıralama algoritması yalnızca sayma sayılarını sıralamak için kullanılan bir algoritma değildir Çoğu bilgisayar veri saklamak için ikilik tabandaki sayıların elektronikteki gösterim biçimlerini kullandığı için sayma sayılarının basamaklarını ikilik tabandaki sayılardan oluşan öbekler biçiminde göstermek daha kolaydır Basamağa göre sıralama algoritması en anlamlı basamağa göre sıralama ve en anlamsız basamağa göre sıralama olarak ikiye ayrılır En anlamsız basamağa göre sıralama algoritması sayıları en anlamsız (en küçük, en sağdaki) basamaktan başlayıp en anlamlı basamağa doğru yürüyerek sıralarken en anlamlı basamağa göre sıralama bunun tam tersini uygular Sıralama algoritmaları tarafından işlenen ve kendi sayı değerlerini gösterebildiği gibi başka tür verilerle de eşleştirilebilen sayma sayılarına çoğu zaman "anahtar" denir En anlamsız basamağa göre sıralamada kısa anahtarlardan uzunlardan önce gelirken aynı uzunluktaki anahtarlar sözlükteki sıralarına göre sıralanırlar Bu sıralama biçimi sayma sayılarının kendi değerlerine göre sıralandıklarında oluşan sırayla aynı sırayı oluşturur Örneğin 1'den 10'a kadar olan sayılar sıralandığında ortaya 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 dizisi çıkacaktır En anlamlı basamağa göre sıralama sözcükler ya da aynı uzunluktaki sayılar gibi dizgileri sıralamak için uygun olan sözlükteki sıraya göre sıralar Örneğin "b, c, d, e, f, g, h, i, j, ba" dizisi sözlük sırasına göre "b, ba, c, d, e, f, g, h, i, j" olarak sıralanacaktır Eğer sözlük sırası değişken uzunluktaki sayılarda uygulanırsa sayılar değerlerinin gerektirdiği konumlara konulmazlar Örneğin 1'den 10'a kadar olan sayılar sıralandığında, algoritma kısa olan sayıların sonuna boş karakter koyarak bütün anahtarları en uzun anahtarla aynı boyuta getireceğinden sonuç 1, 10, 2, 3, 4, 5, 6, 7, 8, 9 olacaktır |
Sıralama Algoritmaları |
10-29-2012 | #2 |
Prof. Dr. Sinsi
|
Sıralama AlgoritmalarıCüce sıralaması (İngilizcesi: Gnome sort), bilgisayar bilimlerinde kullanılan araya sokmalı sıralamaya benzer bir sıralama algoritmasıdır Ara sokmalı sıralamadan farkı kabarcık sıralaması yönteminde olduğu gibi, bir elemanın sıralanan dizideki yerine birçok yer değiştirme yoluyla gelmesidir Cüce Sıralaması adı algoritmanın yönteminin mitolojideki Hollanda cücelerinin (gnome) bir dizi çiçek saksısını sıraya diziş biçimine benzemesinden kaynaklanmaktadır Sözde Kodu function gnomeSort(a[0size-1]) { i := 1 j := 2 while i < size - 1 if a[i-1] >= a[i] i := j j := j + 1 else swap a[i-1] and a[i] i := i - 1 if i = 0 i := 1 } Algoritmanın Java Uygulaması void gnomeSort(int a[]) { int i = 1; int j = 2; while (i < alength - 1) { if (a[i - 1] >= a[i]) { i = j; j++; } else { int temp = a[i]; a[i] = a[i - 1]; a[i - 1] = temp; i--; if (i == 0) { i = 1; } } } Eklemeli Sıralama (İngilizcesi: Insertion Sort), bilgisayar bilimlerinde kullanılan ve sıralı diziyi her adımda öğe öğe oluşturan bir sıralama algoritmasıdır Büyük dizilerle çalışıldığında hızlı sıralama, birleştirmeli sıralama ve yığın sıralaması gibi daha gelişmiş sıralama algoritmalarından daha verimsiz çalışır Ancak buna karşın bazı artıları da vardır: Eklemeli Sıralama'nın rastgele üretilmiş sayıları nasıl sıraya dizdiğini gösteren bir örnek 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ığı mathcal{O}(n^2) olan 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 İnsanlar herhangi birşeyi (örneğin, iskambil kartları) sıralarken, çoğu durumda eklemeli sıralamaya benzer bir yöntem kullanırlar Sözde Kodu insertionSort(array A) for i = 1 to length[A-1] do value = A[i] j = i-1 while j >= 0 and A[j] > value A[j + 1] = A[j] j = j-1 A[j+1] = value Güvercin yuvası sıralaması Güvercin yuvası sıralaması, n adet öğeyi N adet "güvercin yuvası" (sıralanacak öğelerin alabileceği olası değerlerin sayısı) ile (Θ(n + N)) karmaşıklığıyla sıralayan bir sıralama algoritmasıdır N O(n) olduğunda algoritma doğrusal zamanda çalışır Bir sıralama algoritmasının dizideki öğeleri sıralamak için her bir öğeye en az bir kere bakması zorunlu olduğundan doğrusal zaman sıralama algoritmasından bağımsız olarak erişilebilecek en iyi sonuçtur Güvercin yuvası algoritması aşağıdaki biçimde çalışır: Başlangıçta boş "güvercin yuvalarının" bulunduğu her bir arama anahtarı aralığına bir güvercin yuvası düşecek biçimde bir dizi oluştur Sıralanacak dizinin üzerinden geçerek bütün öğeleri ilgili güvercin yuvasına yerleştir Güvercin yuvası disizinin üzerinden sırayla gerçerek boş olmayan bütün yuvalardaki öğeleri asıl diziye aktar Güvercin yuvası sıralaması hızlı çalışması için gereken durumların nadiren oluşması ve diğer daha esnek ve neredeyse aynı hızda çalışan algoritmaların kullanımı daha kolay olduğu için pek kullanılmaz Özellikle kova sıralaması güvercin yuvası sıralamasının uygulamada daha fazla kullanılan bir türüdür Sözde kodu N adet ayrık elemanı sıralayan güvercin yuvası sıralamasının sözde kodu aşağıdaki gibidir: function pigeonhole_sort(array a[n]) array b[N] var i,j zero_var (b) (* zero out array b *) for i in [0length(a)-1] b[a[i]] := b[a[i]]+1 (* copy the results back to a *) j := 0 for i in [0length(b)-1] repeat b[i] times a[j] := i j := j+1 |
Sıralama Algoritmaları |
10-29-2012 | #3 |
Prof. Dr. Sinsi
|
Sıralama AlgoritmalarıHızlı sıralama Hızlı Sıralama'nın uygulanması sırasındaki davranışı Yatay çizgiler seçilen pivot elemanları gösterir Hızlı Sıralama (İngilizcesi: Quicksort) günümüzde yaygın olarak kullanılan bir sıralama algoritmasıdır Hızlı sıralama algoritması n adet sayıyı, ortalama bir durumda, karmaşıklığıyla, en kötü durumda ise karmaşıklığıyla sıralar Algoritmanın karmaşıklığı aynı zamanda yapılan karşılaştırma sayısına eşittir Tarihi Hızlı Sıralama algoritması 1960 yılında küçük bir İngiliz şirketi olan Elliot Brothers'ta çalışan C A R Hoare tarafından geliştirilmiştir Algoritma Hızlı sıralama algoritması, sıralanacak bir sayı dizisini daha küçük iki parçaya ayırıp oluşan bu küçük parçaların kendi içinde sıralanması mantığıyla çalışır Algoritmanın adımları aşağıdaki gibidir: Sayı dizisinden herhangi bir sayıyı pivot eleman olarak seç Sayı dizisini pivottan küçük olan tüm sayılar pivotun önüne, pivottan büyük olan tüm sayılar pivotun arkasına gelecek biçimde düzenle (pivota eşit olan sayılar her iki yana da geçebilir) Bu bölümlendirme işleminden sonra eleman sıralanmış son dizide olması gerektiği yere gelir Algoritmanın bu aşamasına bölümlendirme aşaması denir Pivotun sol ve sağ yanında olmak üzere oluşan iki ayrı küçük sayı dizisi, hızlı sıralama algoritması bu küçük parçalar üzerinde yeniden özyineli olarak çağrılarak sıralanır Algoritma içinde sayı kalmayan (eleman sayısı sıfır olan) bir alt diziye ulaştığında bu dizinin sıralı olduğunu varsayar Örnek TEKRARLA Ara index_sol için sortFeld[index_sol] ≥ sortFeld[Pivot] Ara index_sağ için sortFeld[index_sağ] ≤ sortFeld[Pivot] EĞER index_sol ve index_sağ bulundu ise SONRA Değiştir sortFeld[index_sol] ile sortFeld[index_sağ] YOKSA Bir element kaydır SON EĞER Koşul tamamlanıncaya kadar Üstteki algoritmaya göre asagidaki örnek : SORTIERBEISPIEL 1 - Pivot(karşılaştırma) elementini bulmak için : İlkönce harfler sayılır Eger toplam tek ise (1) ekleyip ikiye bölünür (15 + 1) / 2 = 8 toplam çift ise ikiye bölünür 2 - Bu durumda Pivot element B oluyor SORTIER B EISPIEL B urada ilk harf olan 'S' son harf olan 'L' ve orta harf olan 'B' karşılaştırılır İçlerinde ortanca olan değer her zaman orta değerdir Yani örnek şu şekle dönüşür : SORTIER L EISPIEB 3 - Yukarıdaki algoritma göz önünde bulundurulursa; Kontrol ediliyor : Soldaki element(S) Pivot(L) den büyük mü? ( Evet ) Sağdaki element(B) Pivot(L) den küçük mü? ( Evet ) Eğer iki koşul da doğru ise ilk element(S) ile son element(B) yer değiştirilir ( BORTIER L EISPIES ) (Algoritmaya göre sadece ikisi 'evet' ise değişim gerçekleşir) Soldaki element(0) Pivot(L) den büyük mü? ( Evet ) Sağdaki element(E) Pivot(L) den küçük mü? ( Evet ) Eğer iki koşul da doğru ise ilk element(0) ile son element(E) yer değiştirilir ( BERTIER L EISPIOS ) Soldaki element(R) Pivot(L) den büyük mü? ( Evet ) Sağdaki element(I) Pivot(L) den küçük mü? ( Evet ) Eğer iki koşul da doğru ise ilk element(R) ile son element(I) yer değiştirilir ( BEITIER L EISPROS ) Soldaki element(T) Pivot(L) den büyük mü? ( Evet ) Sağdaki element(P) Pivot(L) den küçük mü? ( Hayır ) Eğer bir koşul yanlış ise soldaki element(T) sabit kalıyor , sağdaki element(P) yi direk sağa yazılır ( BEIIER L EISPROS ) (DİKKAT : 'T' algoritmaya şu an dahil değil, ta ki ikisi de 'evet' oluncaya kadar) Soldaki element(T) Pivot(L) den büyük mü? ( Evet ) Sağdaki element(S) Pivot(L) den küçük mü? ( Hayır ) Eğer bir koşul yanlış ise soldaki element(T) sabit kalıyor , sağdaki element(S) yi direk sağa yazılır ( BEIIER L EISPROS ) Soldaki element(T) Pivot(L) den büyük mü? ( Evet ) Sağdaki element(I) Pivot(L) den küçük mü? ( Evet ) Eğer iki koşul da doğru ise element(T) ile element(I) yer değiştirilir ( BEIIIER L ETSPROS ) (Şimdi 'T' yazılabilir, ikisi de evet) Soldaki element(E) Pivot(L) den büyük mü? ( Hayır ) Sağdaki element(E) Pivot(L) den küçük mü? ( Evet ) Eğer bir koşul yanlış ise soldaki element(E) sola yazılır , sağdaki element(E) sabit kalıyor ( BEIIIER L ETSPROS ) Soldaki element(R) Pivot(L) den büyük mü? ( Evet ) Sağdaki element(E) Pivot(L) den küçük mü? ( Evet ) Eğer bir koşul da doğru ise soldaki element(R) ile sağdaki element(E) sabit kalıyor ( BEIIIEE L RTSPROS ) Son aşama Soldaki element(R) Pivot(L) den büyük mü? ( Evet ) Sağdaki element(E) Pivot(L) den küçük mü? ( Evet ) Eğer bir koşul yanlış ise soldaki element(R) sola yazılır , sağdaki element(E) sabit kalıyor ( BEIIIEE L RTSPROS ) B - E - I - I - I - E - E - L - R - T - S - P - R - O - S Aynı işlemleri sağdaki ve soldaki bölümlere ayrı ayrı yapılır Sonuç şöyle : B E E E I I I L O P R R S S T Sözde Kodu Algoritmanın yalın bir sözde kod olarak gösterimi aşağıdaki gibidir: function quicksort(array) var list less, equal, greater if length(array) ≤ 1 return array select a pivot value pivot from array for each x in array if x < pivot then append x to less if x = pivot then append x to equal if x > pivot then append x to greater return concatenate(quicksort(less), equal, quicksort(greater)) |
Sıralama Algoritmaları |
10-29-2012 | #4 |
Prof. Dr. Sinsi
|
Sıralama AlgoritmalarıKabarcık sıralaması Kabarcık sıralaması'nın rastgele üretilmiş sayıları sıraladığını gösteren bir örnek Kabarcık Sıralaması, bilgisayar bilimlerinde kullanılan yalın bir sıralama algoritmasıdır Sıralanacak dizinin üzerinde sürekli ilerlerken her defasında iki öğenin birbiriyle karşılaştırılıp, karşılaştırılan öğelerin yanlış sırada olmaları durumunda yerlerinin değiştirilmesi mantığına dayanır Algoritma, herhangi bir değişiklik yapılmayıncaya kadar dizinin başına dönerek kendisini yineler Adına "Kabarcık" sıralaması denmesinin nedeni büyük olan sayıların aynı suyun altındaki bir kabarcık gibi dizinin üstüne doğru ilerlemesidir Başlangıçta yer yer değiştirme sıralaması olarak adlandırılan kabarcık sıralaması, dizi içindeki büyük elemanların algoritmanın her adımında dizinin sonuna doğru doğrusal olarak ilerlemesini sağlar Bu ilerleme, seçmeli sıralama algoritmasındaki dizideki değeri küçük olan elemanların dizinin başında kümelenmesi yöntemine benzer şekilde gerçekleşir İnceleme Kabarcık sıralaması dizinin başından başlar ve dizi elemanlarını sırayla seçer Seçilen dizi elemanı kendinden sonra gelen elemandan büyükse bu iki elemanın yerleri değiştirilir Bu işlem sonucunda dizinin en büyük elemanı dizi sonuna yerleştirildiğinden bir sonraki adımda arama sınırı bir eleman geri çekilir Bu işlem, dizinin sonundaki elemanın karşılaştırılmasına kadar yinelenerek sürdürülür Algoritmanın Karmaşıklığı Kabarcık sıralama algoritmasının ortalama ve en kötü durumdaki karmaşıklığı 'dir Algoritma ortalama ve en kötü durumda adet karşılaştırma ve yer değiştirme gerçekleştirir Algoritmanın Adım Adım İşleyişi İçeriği "5 1 4 2 8" olan bir dizi kabarcık sıralaması ile en küçükten en büyüğe doğru aşağıdaki biçimde sıralanır Her adımda dizinin kalın olarak işaretlenmiş elemenları karşılaştırılan elemanlardır Birinci Geçiş: ( 5 1 4 2 8 ) o ( 1 5 4 2 8 ) Burada algoritma ilk iki elemanı karşılaştırır ve yerlerini değiştirir ( 1 5 4 2 8 ) o ( 1 4 5 2 8 ) ( 1 4 5 2 8 ) o ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) o ( 1 4 2 5 8 ) Burada elemanlar zaten sıralı olduğu için algoritma yerlerini değiştirmez İkinci Geçiş: ( 1 4 2 5 8 ) o ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) o ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) o ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) o ( 1 2 4 5 8 ) Artık dizi sıralıdır ancak algoritma işlemin bittiğini bilmemektedir Algoritmanın dizinin sıralandığını anlaması için bütün dizinin üzerinden hiçbir değişiklik yapmadan tam bir geçiş yapması gerekir Üçüncü Geçiş: ( 1 2 4 5 8 ) o ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) o ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) o ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) o ( 1 2 4 5 8 ) Sonuç olarak dizi sıralanmıştır ve algoritma sonlanır Sözde Kodu Algoritmanın yalın bir sözde kod olarak gösterimi aşağıdaki gibidir: procedure bubbleSort( A : sıralanabilir öğe dizisi ) defined as: do swapped := false for each i in 0 to length( A ) - 2 do: if A[ i ] > A[ i + 1 ] then swap( A[ i ], A[ i + 1 ] ) swapped := true end if end for while swapped end procedure </gösterilebilir: procedure bubbleSort( A : sıralanabilir öğe dizisi ) defined as: for each i in 1 to length(A) do: for each j in length(A) downto i + 1 do: if A[ j -1 ] > A[ j ] then swap( A[ j - 1], A[ j ] ) end if end for end for end procedure |
Sıralama Algoritmaları |
10-29-2012 | #5 |
Prof. Dr. Sinsi
|
Sıralama AlgoritmalarıKabuk sıralaması (İngilizcesi: Shell sort), bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır Eklemeli sıralama algoritmasının aşağıdaki iki gözlem kullanılarak genelleştirilmiş biçimidir: Eklemeli sıralama, sıralanacak dizi zaten büyük oranda sıralıysa daha verimli çalışır Eklemeli sıralama, dizideki öğeleri her adımda yalnızca bir sonraki konuma aktardığından verimsizdir Algoritmanın Geçmişi Kabuk sıralaması algoritmasının adı algoritmayı bulan kişi olan Donald Shell'den gelmektedir Soyadı İngilizce'de Kabuk anlamına gelen Donald Shell algoritmayı 1959 yılında yayınlamıştır Uygulamalar C/C++ dilinde yazılmış kabuk sıralaması Aşağıda C/C++ dilinde yazılmış, bir sayı dizisini kabuk sıralaması algoritmasını kullanarak sıralayan bir program verilmiştir /* SHELL SORT Written by erengencturknet */ #include <stdioh> #define ELEMENTS 6 void shellsort(int A[],int max) { int stop,swap,limit,temp,k; int x=(int)(max/2)-1; while(x>0) { stop=0; limit=max-x; while(stop==0) { swap=0; for(k=0;k<limit;k++) { if(A[k]>A[k+x]) { temp=A[k]; A[k]=A[k+x]; A[k+x]=temp; swap=k; } } limit=swap-x; if(swap==0) stop=1; } x=(int)(x/2); } } int main() { int i; int X[ELEMENTS]={5,2,4,6,1,3}; printf("Unsorted Array: "); for(i=0;i<ELEMENTS;i++) printf("%d ",X[i]); shellsort(X,ELEMENTS); printf(" SORTED ARRAY "); for(i=0;i<ELEMENTS;i++) printf("%d ",X[i]); } Java dilinde yazılmış kabuk sıralaması public static void shellSort(int[] a) { for (int increment = alength / 2; increment > 0; increment = (increment == 2 ? 1 : (int) Mathround(increment / 22))) { for (int i = increment; i < alength; i++) { int temp = a[i]; for (int j = i; j >= increment && a[j - increment] > temp; j -= increment){ a[j] = a[j - increment]; a[j - increment] = temp; } } } } Python dilinde yazılmış kabuk sıralaması def shellsort(a): def increment_generator(a): h = len(a) while h != 1: if h == 2: h = 1 else: h = 5*h//11 yield h for increment in increment_generator(a): for i in xrange(increment, len(a)): for j in xrange(i, increment-1, -increment): if a[j - increment] < a[j]: break a[j], a[j - increment] = a[j - increment], a[j] return a |
Sıralama Algoritmaları |
10-29-2012 | #6 |
Prof. Dr. Sinsi
|
Sıralama AlgoritmalarıKokteyl sıralaması Kokteyl sıralaması, bilgisayar bilimlerinde kabarcık sıralaması algoritmasına benzer bir sıralama algoritmasıdır Kabarcık sıralamasından farkı sıralanacak listenin üzerinden tek yöne doğru değil iki yöne de geçerek öğeleri sıralamasıdır Algoritmanın uygulanması kabarcık sıralaması algoritmasının uygulanmasından çok az daha zordur Sözde kodu Kokteyl sıralamasının en yalın biçimi her defasında listenin tamamının üzerinden geçer: procedure cocktailSort( A : list of sortable items ) defined as: do swapped := false for each i in 0 to length( A ) - 2 do: if A[ i ] > A[ i + 1 ] then // ardışık iki öğenin doğru sırada olup olmadığına bak order swap( A[ i ], A[ i + 1 ] ) // iki öğenin yerlerini değiştir swapped := true end if end for if swapped = false then // eğer değişiklik yapılmadıysa dıştaki döngüden çıkabiliriz break do-while loop end if swapped := false for each i in length( A ) - 2 to 0 do: if A[ i ] > A[ i + 1 ] then swap( A[ i ], A[ i + 1 ] ) swapped := true end if end for while swapped // hiçbir öğe yer değiştirmediyse liste sıralanmıştır end procedure |
Sıralama Algoritmaları |
10-29-2012 | #7 |
Prof. Dr. Sinsi
|
Sıralama AlgoritmalarıKova Sıralaması Elemanlar önce kovalar arasında dağıtılır Daha sonra her kovadaki elemanlar kendi içinde sıralanır Kova Sıralaması (ya da sepet sıralaması), sıralanacak bir diziyi parçalara ayırarak sınırlı sayıdaki kovalara (ya da sepetlere) atan bir sıralama algoritmasıdır Ayrışma işleminin ardından her kova kendi içinde ya farklı bir algoritma kullanılarak ya da kova sıralamasını özyinelemeli olarak çağırarak sıralanır Kova sıralaması aşağıdaki biçimde çalışır: Başlangıçta boş olan bir "kovalar" dizisi oluştur Asıl dizinin üzerinden geçerek her öğeyi ilgili aralığa denk gelen kovaya at Boş olmayan bütün kovaları sırala Boş olmayan kovalardaki bütün öğeleri yeniden diziye al Sözde kodu function bucket-sort(array, n) is buckets ← new array of n empty lists for i = 0 to (length(array)-1) do insert array[i] into buckets[msbits(array[i], k)] for i = 0 to n - 1 do next-sort(buckets[i]) return the concatenation of buckets[0], , buckets[n-1] |
Sıralama Algoritmaları |
10-29-2012 | #8 |
Prof. Dr. Sinsi
|
Sıralama AlgoritmalarıKütüphane Sıralaması Kütüphane Sıralaması, ya da diğer bir deyişle aralıklı eklemeli sıralama, eklemeli sıralama algoritmasını art arda yapılan eklemeleri dizideki boşlukları kullanıp hızlandırarak kullanan bir sıralama algoritmasıdır Adının kütüphabe sıralaması olması bir benzetmeden gelmektedir: Bir kütüphane görevlisinin bir raftaki bütün kitapları A harfiyle başlayanlar sol tarafta kalarak sağa doğru kitapların arasında boşluk kalmayacak biçimde alfabetik sıraya dizmek istediğini varsayalım Eğer görevli B bölümüne ait yeni bir kitabı yerleştirmek isterse kitabın yerini B alanında bulduktan sonra yeni kitaba yer açmak için ilgili kitaptan sonraki bütün kitapları sağa kaydırması gerekir Bu bir eklemeli sıralamadır Ancak, eğer görvli daha önce her bir harften sonra belirli bir boşluk bırakmış olsaydı, yalnızca B harfindeki kitapların yarısını hareket ettirerek bu sıralamayı sağlayabilirdi Kütüphane sıralamasının ana ilkesi budur Algoritma Michael A Bender, Martín Farach-Colton, ve Miguel Mosteiro tarafından 2004'te geliştirilmiştir Kütüphane sıralaması, aynı kendisinden türetildiği eklemeli sıralama gibi, kararlı bir karşılaştırma sıralamasıdır ve sıralamayı yaptığı sırada sıraladığı diziye yeni elemanlar eklenmesine izin verir Ayrıca kütüphane sıralaması çoğu durumda eklemeli sıralama algoritmasının O(n2) karmaşıklığı yerine hızlı sıralama algoritmasının O(n log n) karmaşıklığına yaklaşmaktadır Tek sorunu ise algoritmanın kullanıdığı aralıklar nedeniyle fazladan yere gereksinim duymasıdır |
Sıralama Algoritmaları |
10-29-2012 | #9 |
Prof. Dr. Sinsi
|
Sıralama AlgoritmalarıSabır sıralaması Sabır sıralaması bilgisayar bilimlerinde kullanılan ve bir kâğıt oyununa dayanan bir sıralama algoritmasıdır Kağıt oyunu Oyun, 1, 2, , n biçiminde numaralandırılmış n adet oyun kağıdından oluşan desteyle oynanır Kağıtlar masanın üzerinde aşadaki kurallara uygun olarak bölümlere ayrılır: Başlangıçta hiçbir kâğıt yığını yoktur Oynanan ilk kart tek kartta oluşan bir alt deste oluşturur Oynanan her yeni kart ya en üstte kendisinden daha büyük bir kart bulunan kâğıt yığının en üstüne ya da masadaki tüm yığınların en sağına yeni bir yığın oluşturmak üzere yerleştirilir Dağıtılacak kâğıt kalmadığı zaman oyun biter Oyunun amacı oyunu olabilecek en az sayıda kâğıt yığınıyla bitirmektir |
Sıralama Algoritmaları |
10-29-2012 | #10 |
Prof. Dr. Sinsi
|
Sıralama AlgoritmalarıSabır sıralaması Sabır sıralaması bilgisayar bilimlerinde kullanılan ve bir kâğıt oyununa dayanan bir sıralama algoritmasıdır Kağıt oyunu Oyun, 1, 2, , n biçiminde numaralandırılmış n adet oyun kağıdından oluşan desteyle oynanır Kağıtlar masanın üzerinde aşadaki kurallara uygun olarak bölümlere ayrılır: Başlangıçta hiçbir kâğıt yığını yoktur Oynanan ilk kart tek kartta oluşan bir alt deste oluşturur Oynanan her yeni kart ya en üstte kendisinden daha büyük bir kart bulunan kâğıt yığının en üstüne ya da masadaki tüm yığınların en sağına yeni bir yığın oluşturmak üzere yerleştirilir Dağıtılacak kâğıt kalmadığı zaman oyun biter Oyunun amacı oyunu olabilecek en az sayıda kâğıt yığınıyla bitirmektir |
Sıralama Algoritmaları |
10-29-2012 | #11 |
Prof. Dr. Sinsi
|
Sıralama AlgoritmalarıSayarak sıralama Sayarak sıralama bilgisayar bilimlerinde kullanılan ve kova sıralaması gibi sıralanacak dizinin içindeki değerlerin aralığının bilinmesi durumunda kullanılabilen bir sıralama algoritmasıdır Sayarak sıralama algoritması dizideki değerlerin aralık bilgilerini yeni bir dizi oluşturmak için kullanır Oluşturulan yeni dizinin her bir satırı ana dizide o satır numarasının değerine sahip öğelerin sayısını gösterir Yeni dizideki öğe değeri sayıları daha sonra ana dizideki tüm değerlerin doğru konuma konulması için kullanılır Sayarak sıralama algoritması güvercin yuvası sıralamasından daha verimsiz bir algoritmadır C++ ile uygulaması Aşağıdaki program sayarak sıralama algoritmasının C++ dilinde yazılmış bir uygulamasını göstermektedir /// countingSort - değerleri tutan bir diziyi sıralamak için /// /// Algoritmanın verimli çalışması için sıralacak /// değerlerin aralığı sıralanacak öğelerin sayısından /// çok daha büyük olmamalıdır /// /// param nums - girdi - sıralanacak değerler dizisi /// param size - girdi - dizideki öğelerin sayısı /// void counting_sort(int *nums, int size) { // search for the minimum and maximum values in the input int i, min = nums[0], max = min; for(i = 1; i < size; ++i) { if (nums[i] < min) min = nums[i]; else if (nums[i] > max) max = nums[i]; } // create a counting array, counts, with a member for // each possible discrete value in the input // initialize all counts to 0 int distinct_element_count = max - min + 1; int[] counts = new int[distinct_element_count]; for(i=0; i<distinct_element_count; ++i) counts[i] = 0; // accumulate the counts - the result is that counts will hold // the offset into the sorted array for the value associated with that index for(i=0; i<size; ++i) ++counts[ nums[i] - min ]; // store the elements in the array int j=0; for(i=min; i<=max; i++) for(int z=0; z<counts[i-min]; z++) nums[j++] = i; delete[] counts; |
Sıralama Algoritmaları |
10-29-2012 | #12 |
Prof. Dr. Sinsi
|
Sıralama AlgoritmalarıSaçma sıralama Saçma sıralama (ya da rastgele sıralama) bilgisayar bilimlerinde yalnızca eğitim amaçlı olarak kullanılan verimsiz bir sıralama algoritmasıdır Bir deste oyun kağıdı saçma sıralama algoritmasıyla sıralanmak istendiğinde, destenin sıralı olup olmadığına bakılır, eğer deste sıralı değilse havaya atılarak yere düşen kartlar toplanarak deste yeniden oluşturulur Bu işlem deste sıralanana kadar sürer Uygulama Sözde kodu: while not InOrder(deck) do Shuffle(deck); Java public int[] BogoSort(int[] numbers) { Random rnd = new Random(); while(true) { boolean sorted = true; for(int i = 0; i < numberslength-1; i++) if(numbers[i] > numbers[i+1]) sorted = false; if (sorted) return numbers; for(int i = numberslength - 1; i > 0; i--) { int rand = rndnextInt(i); int temp = numbers[i]; numbers[i] = numbers[rand]; numbers[rand] = temp; } } } Benzer algoritmalar Rastgele değiştirmeli sıralama Rastgele değiştirmeli sıralama, rastgele sayı seçmeye dayalı, saçma sıralamaya benzer bir sıralama algoritmasıdır Eğer sıralanacak dizi sıralı değilse algoritma rastgele iki sayı seçer ve bu iki sayıyı birbiriyle değiştirir Algoritmanın çalışma süresini belirlemek oldukça zordur ve gerçek uygulamalarında sıralanmış bir diziye ulaşamayabilir |
Sıralama Algoritmaları |
10-29-2012 | #13 |
Prof. Dr. Sinsi
|
Sıralama AlgoritmalarıSeçmeli Sıralama Seçmeli Sıralama, bilgisayar bilimlerinde kullanılan karmaşıklığı bir sıralama algoritmasıdır Karmaşıklığı olduğu için büyük listeler üzerinde kullanıldığında verim sağlamaz ve genel olarak benzeri olan eklemeli sıralamadan daha başarısızdır Seçmeli sıralama yalın olduğu ve bazı durumlarda daha karmaşık olan algoritmalardan daha iyi sonuç verdiği için tercih edilebilir Seçmeli sıralama algoritması Seçmeli Sıralama'nın nasıl çalıştığını gösteren görüntü Yöntem Seçmeli Sıralama'nın nasıl çalıştığını gösteren görüntü Algoritma aşağıdaki gibi çalışır: Listedeki en küçük değerli öğeyi bul İlk konumdaki öğeyle bulunan en küçük değerli öğenin yerini değiştir Yukarıdaki adımları listenin ilk elemanından sonrası için (ikinci elemandan başlayarak) yinele Sözde Kodu A sıralanacak öğeler kümesi, n ise A'daki öğe sayısıdır Dizi 0 numaralı dizinle başlamaktadır for i ← 0 to n-2 do min ← i for j ← (i + 1) to n-1 do if A[j] < A[min] min ← j swap A[i] and A[min] Seçmeli Sıralama Algoritmasının Örnek Kodu public int[] secmeliSiralama(int[] dizi) { int enkucuk, yedek; for (int i = 0; i < diziLength - 1; i++) { enkucuk = i; for (int j = i + 1; j < diziLength; j++) if (dizi[j] < dizi[enkucuk]) enkucuk = j; if (enkucuk != i) { yedek = dizi[i]; dizi[i] = dizi[enkucuk]; dizi[enkucuk] = yedek; } } return dizi; 6 elemanlı içeriği karışık olarak verilmiş bir bir sayı dizisinin Seçmeli Sıralama algoritması kullanılarak nasıl küçükten-büyüğe doğru sıralandığını göstermektedir 1 adımda dizinin ilk elemanı (6) alınır Bu eleman diğer 5 eleman ile karşılaştırılır Eğer bulunan eleman(1) ilk elemandan küçükse 1elman ile yer değiştirilir 2 adımda dizinin ikinci elemanı(3) alınır Bu eleman kalan 4 eleman ile karşılaştırılır Eğer bulunan eleman(2) ikinci elemandan küçükse 2 eleman ile yer değiştirilir ve bu işlem dizi sonuna kadar devam eder Böylelikle dizi küçükten-büyüğe sıralanmış olur |
Sıralama Algoritmaları |
10-29-2012 | #14 |
Prof. Dr. Sinsi
|
Sıralama AlgoritmalarıSıralama Sıralama bir dizi elemanı, belirli bir özelliğine göre sıraya dizme işlemine verilen addır Bilgisayar bilimlerinin en çok incelenmiş konularından birisi sıralama algoritmalarıdır Karışık halde: 9 4 2 8 3 1 5 6 7 Sıraya dizilmiş: 1 2 3 4 5 6 7 8 9 Sıralama, genellikle indekslerde, ansiklopedilerde kullanılır Ayrıca şuralarda da yaygındır: Katalog, bibliyografya, sözlük, kütüphane fişleri, ve bazı arama motorları Tarrak Sıralaması Tarrak Sıralaması, ilk defa 1991 yılının Nisan ayında Stephen Lacey ve Richard Box tarafından Byte dergisinde duyurulmuş yalın bir sıralama algoritmasıdır Kendisinden önce duyurulmuş kabarcık sıralaması algoritmasından başarılıdır ve karmaşıklıkta hızlı sıralama algoritmasıyla yarışır Algoritmanın ana fikri listenin sonundaki küçük değerli öğelerin sayısını azaltmaktır Kabarcık sıralaması algoritmasında sıralanacak listenin sonundaki küçük değerli öğelerin varlığı algoritmayı çok yavaşlattığı için tarak sıralamasında bu değerlerin sayısının azaltılması yoluna gidilmiştir Kabarcık sıralaması algoritmasında iki öğe karşılaştırıldığında aralarındaki mesafe her zaman 1'dir Başka bir deyişle, kabarcık sıralaması her zaman ardışık iki değeri karşılaştırır Taraf sıralaması ise bunun aksine aralarındaki mesafe birden çok daha fazla olan öğeleri karşılaştırabilir (Kabuk sıralaması da aynı düşünceyle tasarlanmıştır ancak kabuk sıralaması kabarcık sıralamasının değil seçmeli sıralamanın bir türevidir) Sözde Kodu function combsort11(array input) gap := inputsize //öğeler arasındaki aralığın başlangıç boyutunu belirle loop until gap <= 1 or swaps = 0 //yeni bir tarama için aralığın boyutunu güncelle if gap > 1 gap := gap / 13 if gap = 10 or gap = 9 gap := 11 end if end if i := 0 swaps := 0 // Açıklama için kabarcık sıralamasına bakınız // giriş listesinin üzerinden tek bir "tarama" loop until i + gap >= arraysize //Benzer yaklaşım için kabuk sıralamasına bakınız if array[i] > array[i+gap] swap(array[i], array[i+gap]) swaps := 1 // Aritmetik taşma düzeltmesi için end if i := i + 1 end loop end loop end function |
Sıralama Algoritmaları |
10-29-2012 | #15 |
Prof. Dr. Sinsi
|
Sıralama AlgoritmalarıYığın Sıralaması (İngilizcesi: Heapsort), bilgisayar bilimlerinde kullanılan karşılaştırmaya dayalı bir sıralama algoritmasıdır Uygulamada pek çok bilgisayarda hızlı sıralama algoritmasından daha yavaş çalışsa da en kötü durumda O(n log n) çalışma süresi vardır Yığın sıralaması diziyi yerinde sıralar ancak kararlı bir sıralama algoritması değildir Sözde Kodu Aşağıda yığın sıralaması algoritmasının sözde kodu verilmiştir swap dizideki iki öğenin yerlerini değiştirmek için kullanılmaktadır function heapSort(a, count) is input: an unordered array a of length count (first place a in max-heap order) heapify(a, count) end := count - 1 while end > 0 do (swap the root(maximum value) of the heap with the last element of the heap) swap(a[end], a[0]) (decrease the size of the heap by one so that the previous max value will stay in its proper placement) end := end - 1 (put the heap back in max-heap order) siftDown(a, 0, end) function heapify(a,count) is (start is assigned the index in a of the last parent node) start := (count - 1) / 2 while start ≥ 0 do (sift down the node at index start to the proper place such that all nodes below the start index are in heap order) siftDown(a, start, count-1) start := start - 1 (after sifting down the root all nodes/elements are in heap order) function siftDown(a, start, end) is input: end represents the limit of how far down the heap to sift root := start while root * 2 + 1 ≤ end do (While the root has at least one child) child := root * 2 + 1 (root*2+1 points to the left child) (If the child has a sibling and the child's value is less than its sibling's) if child < end and a[child] < a[child + 1] then child := child + 1 ( then point to the right child instead) if a[root] < a[child] then (out of max-heap order) swap(a[root], a[child]) root := child (repeat to continue sifting down the child now) else return heapify fonksiyonu alttan üste doğru bir yığın oluşturmak için kullanılırken yığın özelliği kazandırılmak için öğeler aşağıya doğru incelenir Aşağıda gösterilmiş bir diğer yol kullanılarak yığın üstten alta oluşturulup öğeler yukarı doğru incelenebilir Ancak aşağıdaki uygulama her ne kadar anlaşılması daha kolay olsa da daha yavaştır function heapify(a,count) is (end is assigned the index of the first (left) child of the root) end := 1 while end < count (sift up the node at index end to the proper place such that all nodes above the end index are in heap order) siftUp(a, 0, end) end := end + 1 (after sifting up the last node all nodes are in heap order) function siftUp(a, start, end) is input: start represents the limit of how far up the heap to sift end is the node to sift up child := end while child > start parent := ⌊(child - 1) ÷ 2⌋ if a[parent] < a[child] then (out of max-heap order) swap(a[parent], a[child]) child := parent (repeat to continue sifting up the parent now) else return |
|