Bilgi Bankamız 62 Kategoride, 9052 Makale ve Konu Anlatımı içermektedir. Son Güncelleme: 27.01.2020 06:06

Sıralama Algoritması | Bilgisayar Bilimlerinde Ya Da Matematikte Kullanılan Verilen Bir Listenin Elemanlarını Belirli Bir Sıraya Sokan Algoritma


İçerik Hakkında Bilgi

  • Bu içerik 29.05.2009 tarihinde Hale tarafından, Matematik ve Geometri Konu Anlatımları bölümünde paylaşılmıştır ve 1883 kez okunmuştur.
    Kaynak: Kadim Dostlar ™ Forum

İçerik ve Kategori Araçları


Sıralama Algoritması

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.


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 Algoritmaları

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.

BirleÅŸtirmeli sıralama‘nın rastgele üretilmiÅŸ sayıları gösteren noktaları nasıl sıraladığını gösteren örnek

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 çı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şlmetmektir. Ancak asıl dizideki öğre sırasının hatırlanması çoğu zaman ek saklama alanı gerektirir.


Sıralama Algoritmalarının Listesi

AÅŸağıdaki tablolarda n dizideki sıralanacak olan eleman sayısını gösterir. “Ortalama” ve “En Kötü” kolonları ilgili durumlardaki karmaşıklığı, “Bellek” kolonu ise listenin sıralanabilmesi için listenin bellekte kapladığı alandan ne kadar daha fazla saklama alanı gerektiÄŸini gösterir.


Karşılaştırmadan Sıralayan Sıralama Algoritmaları

Aşağıdaki tablo karşılaştırma kullanmadan sıralama yapan sıralama algoritmalarını göstermektedir. Bu algoritmalar karşılaştırma yapmadıkları için karmaşıklıklarınınO(n log n) gibi bir alt sınırı yoktur. Tabloda gösterilen karmaşıklıklar sıralanacak listedeki eleman sayısı (n), her bir anahtarın boyutu (k) ve uygulama tarafından kullanılan parça boyutu (k) cinsiden yazılmıştır. Algoritmaların pek çoğu anahtar boyutunun bütün satırlarda özgün anahtar değerleri olmasını sağlayacak kadar büyük ve n << 2k ('<<' = "çok daha küçük") olduğunu varsayar.

Hızlı Sıralama‘nın uygulanması sırasındaki davranışı. Yatay çizgiler seçilen pivot elemanları gösterir.

Kabarcık sıralaması‘nın rastgele üretilmiÅŸ sayıları nasıl sıraladığını gösteren bir örnek.

Eklemeli Sıralama‘nın rastgele üretilmiÅŸ sayıları nasıl sıraya dizdiÄŸini gösteren bir örnek.

(Visited 14 times, 1 visits today)


Kaynak: Kadim Dostlar ™ Forum

Bu içerik 29.05.2009 tarihinde Hale tarafından, Matematik ve Geometri Konu Anlatımları bölümünde paylaşılmıştır ve 1883 kez okunmuştur. Bu içeriğin devamında incelemek isteyebileceğiniz 0 adet mesaj daha bulunmaktadır.

Sıralama Algoritması | Bilgisayar Bilimlerinde Ya Da Matematikte Kullanılan Verilen Bir Listenin Elemanlarını Belirli Bir Sıraya Sokan Algoritma orjinal içeriğine ulaşmak için tıklayın ...

Önceki MakaleBeyin Zihin ve Duygu | GeçmiÅŸi Yeniden YaÅŸamak - Eidetic (Fotografsı) Bellek - Mutluluk ve Öfke - Bilgiler Beynimizde Nasıl Sınıflandırılıyorlar..... Sonraki MakaleKurÅŸunlu Camii - Kayseri | 1574 Yılında DoÄŸan Hacı Mehmet PaÅŸa Tarafından Yaptırılmış

Bu Makaleyle İlgili Fikirlerinizi ve Görüşlerinizi Diğer Ziyaretçilerle Paylaşabilirsiniz