Thursday , November 14 2019
Home / Algoritmalar / Sıralama Algoritmaları (Sorting Algorithms)

Sıralama Algoritmaları (Sorting Algorithms)

Sıralama algoritması, bilgisayar bilimlerinde ya da matematikte kullanılan, verilen bir listenin elemanlarını belirli bir sıraya sokanalgoritmadı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 insankullanı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.

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ı ise Ω(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 olur.

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.

Sıralama Algoritmalarının Listesi

Aşağıda bazı sıralama algoritmaları verilmiştir:

Seçerek Sıralama (Selection Sort)
Hızlı Sıralama Algoritması (Quick Sort Algorithm)
Birleştirme Sıralaması (Merge Sort)
Yığınlama Sıralaması (Heap Sort)
Sayarak Sıralama (Counting Sort)
Kabarcık Sıralaması (Baloncuk sıralaması, Bubble Sort)
Taban Sıralaması (Radix Sort)
Sokma Sıralaması ( Insertion Sort)
Sallama Sıralaması (Shaker Sort)
Kabuk Sıralması (Shell Sort)
Rastgele Sıralama (Bogo Sort)
Şanslı Sıralama (Lucky Sort)
Serseri Sıralaması (Stooge Sort)
Şimşek Sıralaması (Flahs Sort, Bora Sıralaması)
Tarak Sıralaması (Comb Sort)
Gnome Sıralaması (Gnome Sort)
Permütasyon Sıralaması (Permutation Sort)
Strand Sort (İplik Sıralaması)

Sonraki yazılarımızda bütün bu algoritmaları teker teker inceleyeceğiz.

kaynak: https://tr.wikipedia.org/wiki/S%C4%B1ralama_algoritmas%C4%B1

About Burak

Leave a Reply

Your email address will not be published. Required fields are marked *

*

Download Free Premium Joomla Templates • FREE High-quality Joomla! Designs BIGtheme.net