Sıralama algoritması - Sorting algorithm

Gelen bilgisayar bilimleri , bir sıralama algoritması bir olan algoritma a koyar unsurları olduğu listede bir içine sırayla . En sık kullanılan sıralar , sayısal sıra ve sözlük sırasına göre artan veya azalan sıralardır . Verimli sıralama , giriş verilerinin sıralanmış listelerde olmasını gerektiren diğer algoritmaların ( arama ve birleştirme algoritmaları gibi) verimliliğini optimize etmek için önemlidir . Sıralama, genellikle verileri standart hale getirmek ve insan tarafından okunabilir çıktılar üretmek için de yararlıdır .

Resmi olarak, herhangi bir sıralama algoritmasının çıktısı iki koşulu karşılamalıdır:

1. Çıktı monotonik sıradadır (gerekli sıraya göre her eleman bir önceki elemandan daha küçük/daha büyük değildir).
2. Çıktı, girdinin bir permütasyonudur (yeniden sıralama, ancak tüm orijinal öğeleri korur).

Optimum verimlilik için, girdi verileri , yalnızca sıralı erişime izin veren bir veri yapısından ziyade rastgele erişime izin veren bir veri yapısında saklanmalıdır .

Tarih ve kavramlar

Hesaplamanın başlangıcından beri, sıralama problemi, belki de basit, tanıdık ifadesine rağmen onu verimli bir şekilde çözmenin karmaşıklığı nedeniyle, çok sayıda araştırmayı kendine çekmiştir. 1951 civarında erken sıralama algoritmalarının yazarları arasında ENIAC ve UNIVAC üzerinde çalışan Betty Holberton vardı . Kabarcık sıralama 1956 gibi erken bir tarihte analiz edildi. Asimptotik olarak optimal algoritmalar 20. yüzyılın ortalarından beri biliniyor - yaygın olarak kullanılan Timsort'un 2002'ye tarihlenmesi ve kütüphane sıralamasının ilk kez 2006'da yayınlanmasıyla yeni algoritmalar hala icat ediliyor.

Karşılaştırmalı sıralama algoritmalarının temel bir Ω( n log n ) karşılaştırma gereksinimi vardır (bazı giriş dizileri, n'nin sıralanacak dizideki öğelerin sayısı olduğu birden fazla n log n karşılaştırması gerektirir ). Sıralama sayma gibi karşılaştırmalara dayalı olmayan algoritmalar daha iyi performansa sahip olabilir.

Sıralama algoritmaları giriş yaygındır bilgisayar gibi bir sorun için algoritmaların bolluğu çekirdek algoritma kavramları çeşitli yumuşak bir giriş sağlar sınıflar, büyük O gösterimi , Böl ve yen algoritmaları , veri yapıları gibi yığınlar ve ikili ağaç , rastgele algoritmalar , en iyi, en kötü ve ortalama durum analizi, zaman-uzay değiş tokuşları ve üst ve alt sınırlar .

Küçük dizileri en uygun şekilde (en az miktarda karşılaştırma ve takas) veya hızlı (yani makineye özel ayrıntıları dikkate alarak) sıralamak, yalnızca çok küçük diziler (<20 eleman) için bilinen çözümlerle hala açık bir araştırma problemidir. Benzer şekilde, paralel bir makinede optimal (çeşitli tanımlara göre) sıralama, açık bir araştırma konusudur.

sınıflandırma

Sıralama algoritmaları şu şekilde sınıflandırılabilir:

• hesaplama karmaşıklığı
  • Listenin boyutuna göre en iyi, en kötü ve ortalama durum davranışı. Tipik seri sıralama algoritmaları için, iyi davranış O( n  log  n ), paralel sıralama O(log ²  n ) ve kötü davranış O( n ² ) şeklindedir. Seri sıralama için ideal davranış O( n )'dir, ancak bu ortalama durumda mümkün değildir. En uygun paralel sıralama O(log  n )'dir.
  • "Yerinde" algoritmalar için takaslar.
• Bellek kullanımı (ve diğer bilgisayar kaynaklarının kullanımı). Özellikle, bazı sıralama algoritmaları "dir yerinde ". Kesin olarak, yerinde sıralama, sıralanan öğelerin ötesinde yalnızca O(1) belleğe ihtiyaç duyar; bazen O(log  n ) ek bellek "yerinde" olarak kabul edilir.
• Özyineleme: Bazı algoritmalar ya özyinelemeli ya da özyinelemesizdir, diğerleri ise her ikisi de olabilir (örneğin, birleştirme sıralama).
• Kararlılık: kararlı sıralama algoritmaları , eşit anahtarlarla (yani değerler) göreli kayıt sırasını korur.
• Bir karşılaştırma türü olup olmadıkları . Karşılaştırmalı sıralama, verileri yalnızca iki öğeyi bir karşılaştırma operatörüyle karşılaştırarak inceler.
• Genel yöntem: ekleme, değiştirme, seçme, birleştirme, vb. Değişim sıralamaları, kabarcıklı sıralama ve hızlı sıralamayı içerir. Seçim sıralamaları, döngü sıralamasını ve yığın sıralamasını içerir.
• Algoritmanın seri mi yoksa paralel mi olduğu. Bu tartışmanın geri kalanı neredeyse yalnızca seri algoritmalara odaklanır ve seri çalışmayı varsayar.
• Uyarlanabilirlik: Girdinin önceden sıralanmasının çalışma süresini etkileyip etkilemediği. Bunu hesaba katan algoritmaların uyarlanabilir olduğu bilinmektedir .
• Çevrimiçi: Çevrimiçi olan Ekleme Sıralaması gibi bir algoritma, sabit bir girdi akışını sıralayabilir.

istikrar

Oyun kartlarında kararlı sıralama örneği. Kartlar istikrarlı bir sıralama ile sıraya göre sıralandığında, iki 5'ler, sıralanan çıktıda orijinal olarak bulundukları sırada aynı sırada kalmalıdır. Kararlı olmayan bir sıralama ile sıralandıklarında, 5'ler tam tersi şekilde sonuçlanabilir. sıralanmış çıktıda sıralayın.

Kararlı sıralama algoritmaları, eşit öğeleri girdide göründükleri sırayla sıralar. Örneğin, sağdaki kart sıralama örneğinde, kartlar derecelerine göre sıralanıyor ve renkleri yok sayılıyor. Bu, orijinal listenin birden çok farklı doğru sıralanmış versiyonunun olasılığını sağlar. Kararlı sıralama algoritmaları, aşağıdaki kurala göre bunlardan birini seçer: eğer iki öğe eşit olarak karşılaştırılırsa (iki 5 kart gibi), o zaman göreli sıraları korunur, yani girişte biri diğerinden önce gelirse, gelir. çıktıda diğerinden önce.

Kararlılık, aynı veri kümesindeki birden çok sıralamada düzeni korumak için önemlidir . Örneğin, isim ve sınıf bölümünden oluşan öğrenci kayıtlarının, önce isme, sonra sınıf bölümüne göre dinamik olarak sıralandığını varsayalım. Her iki durumda da kararlı bir sıralama algoritması kullanılıyorsa, sınıfa göre bölümleme işlemi ad sırasını değiştirmez; kararsız bir sıralamayla, bölüme göre sıralamanın ad sırasını karıştırarak alfabetik olmayan bir öğrenci listesiyle sonuçlanması olabilir.

Daha resmi olarak, sıralanan veriler bir kayıt veya değer demeti olarak temsil edilebilir ve verilerin sıralama için kullanılan kısmına anahtar adı verilir . Kart örneğinde, kartlar bir kayıt (sıra, renk) olarak temsil edilir ve anahtar sıralamadır. Bir sıralama algoritması, aynı anahtara sahip iki R ve S kaydı olduğunda ve orijinal listede R, S'den önce görünüyorsa, sıralanmış listede R her zaman S'den önce görünürse kararlıdır.

Tamsayılar veya daha genel olarak, tüm öğenin anahtar olduğu herhangi bir veri gibi eşit öğeler ayırt edilemez olduğunda, kararlılık bir sorun değildir. Tüm tuşlar farklıysa, kararlılık da bir sorun değildir.

Kararsız sıralama algoritmaları, kararlı olması için özel olarak uygulanabilir. Bunu yapmanın bir yolu, anahtar karşılaştırmasını yapay olarak genişletmektir, böylece, aksi takdirde eşit anahtarlara sahip iki nesne arasındaki karşılaştırmalara, bir bağlantı kesici olarak orijinal girdi listesindeki girişlerin sırası kullanılarak karar verilir. Ancak bu sırayı hatırlamak ek zaman ve alan gerektirebilir.

Kararlı sıralama algoritmaları için bir uygulama, bir birincil ve ikincil anahtar kullanarak bir listeyi sıralamaktır. Örneğin, kartların takımları sopalar (♣), karolar ( ♦ ), kupalar ( ♥ ), maçalar (♠) ve her renkte kartlar şu şekilde sıralanacak şekilde sıralamak istediğimizi varsayalım . rütbe. Bu, önce kartları rütbeye göre sıralayarak (herhangi bir sıralama kullanarak) ve ardından takıma göre istikrarlı bir sıralama yaparak yapılabilir:

Her bir takım içinde, istikrarlı sıralama, halihazırda yapılmış olan sıralamaya göre sıralamayı korur. Bu fikir herhangi bir sayıda anahtara genişletilebilir ve radix sort tarafından kullanılır . Aynı etki, örneğin, önce takıma göre karşılaştıran ve sonra takımlar aynıysa sıraya göre karşılaştıran sözlükbilimsel bir anahtar karşılaştırması kullanılarak kararsız bir sıralama ile elde edilebilir.

algoritmaların karşılaştırılması

Bu tablolarda n , sıralanacak kayıt sayısıdır. "En İyi", "Ortalama" ve "En Kötü" sütunları , her bir anahtarın uzunluğunun sabit olduğu ve dolayısıyla tüm karşılaştırmaların, takasların ve diğer işlemlerin sabit zamanda devam edebileceği varsayımı altında, her durumda zaman karmaşıklığını verir . "Bellek", aynı varsayım altında, listenin kendisi tarafından kullanılana ek olarak ihtiyaç duyulan ekstra depolama miktarını belirtir. Listelenen çalışma süreleri ve bellek gereksinimleri büyük O notasyonu içindedir , bu nedenle logaritmaların tabanı önemli değildir. log ² n gösterimi (log n ) ² anlamına gelir .

Karşılaştırma türleri

Aşağıda karşılaştırma türlerinin bir tablosu bulunmaktadır . Bir karşılaştırmalı sıralama , ortalama olarak O ( n log n ) değerinden daha iyi performans gösteremez .

Karşılaştırma türleri

İsim	En iyisi	Ortalama	En kötüsü	Hafıza	Kararlı	Yöntem	Diğer notlar
Hızlı sıralama	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	${\görüntüleme stili n^{2}}$	${\görüntüleme stili \log n}$	Numara	bölümleme	Hızlı sıralama genellikle O (log n ) yığın alanı ile yerinde yapılır .
Sıralamayı birleştir	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	n	Evet	birleştirme	Üç Macar Algoritması kullanılarak son derece paralelleştirilebilir ( O (log n ) değerine kadar).
Yerinde birleştirme sıralama	-	-	${\displaystyle n\log ^{2}n}$	1	Evet	birleştirme	Kararlı yerinde birleştirmeye dayalı kararlı bir sıralama olarak uygulanabilir.
tanıtım	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	${\görüntüleme stili \log n}$	Numara	Bölümleme ve Seçim	Birkaç STL uygulamasında kullanılır.
yığın sıralaması	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	1	Numara	seçim
Ekleme sıralama	n	${\görüntüleme stili n^{2}}$	${\görüntüleme stili n^{2}}$	1	Evet	sokma	O ( n + d ) , en kötü durumda, d inversiyonu olan diziler üzerinde.
Blok sıralama	n	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	1	Evet	Ekleme ve Birleştirme	Blok tabanlı yerinde birleştirme algoritmasını aşağıdan yukarıya birleştirme sıralamasıyla birleştirin . ${\görüntüleme stili O(n)}$
Timsort	n	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	n	Evet	Ekleme ve Birleştirme	Veriler zaten sıralanmış veya ters sıralanmışsa n-1 karşılaştırması yapar .
Seçim sıralaması	${\görüntüleme stili n^{2}}$	${\görüntüleme stili n^{2}}$	${\görüntüleme stili n^{2}}$	1	Numara	seçim	İle Kararlı iki öğe takas çeşit yerine İNSERSİYONLARININ bir varyantı olarak yapılan ekstra bağlantılı listelerini kullanarak alanı, ya zaman. ${\görüntüleme stili O(n)}$
Küp Sıralaması	n	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	n	Evet	sokma	Veriler zaten sıralanmış veya ters sıralanmışsa n-1 karşılaştırması yapar .
Kabuk sıralaması	${\görüntüleme stili n\log n}$	${\görüntüleme stili n^{4/3}}$	${\görüntüleme stili n^{3/2}}$	1	Numara	sokma	Küçük kod boyutu.
Kabarcık sıralama	n	${\görüntüleme stili n^{2}}$	${\görüntüleme stili n^{2}}$	1	Evet	değiş tokuş	Küçük kod boyutu.
Değişim sıralaması	${\görüntüleme stili n^{2}}$	${\görüntüleme stili n^{2}}$	${\görüntüleme stili n^{2}}$	1	Evet	değiş tokuş	Küçük kod boyutu.
Ağaç sıralama	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$(dengeli)	n	Evet	sokma	Bir kullanırken kendini dengeleyen ikili arama ağacı .
döngü sıralama	${\görüntüleme stili n^{2}}$	${\görüntüleme stili n^{2}}$	${\görüntüleme stili n^{2}}$	1	Numara	seçim	Teorik olarak optimal yazma sayısı ile yerinde.
Kitaplık sıralaması	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	${\görüntüleme stili n^{2}}$	n	Numara	sokma	Boşluklu ekleme sıralamasına benzer. Yüksek olasılıklı zaman sınırlarını garanti etmek için girdiye rastgele izin verilmesini gerektirir, bu da onu kararlı yapmaz.
sabır sıralama	n	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	n	Numara	Ekleme ve Seçim	Buluntular tüm en uzun artan alt diziler içinde O ( n log n ) .
Pürüzsüz sıralama	n	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	1	Numara	seçim	Bir uyarlamalı dayalı HizliSiralama varyantı Leonardo dizisi yerine geleneksel ikili yığın .
iplik sıralama	n	${\görüntüleme stili n^{2}}$	${\görüntüleme stili n^{2}}$	n	Evet	seçim
Turnuva sıralaması	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	${\görüntüleme stili n\log n}$	n	Numara	seçim	Heapsort'un varyasyonu.
Kokteyl çalkalayıcı sıralama	n	${\görüntüleme stili n^{2}}$	${\görüntüleme stili n^{2}}$	1	Evet	değiş tokuş	Listenin sonundaki küçük değerlerle iyi ilgilenen bir Bubblesort çeşidi
tarak sıralama	${\görüntüleme stili n\log n}$	${\görüntüleme stili n^{2}}$	${\görüntüleme stili n^{2}}$	1	Numara	değiş tokuş	Ortalama olarak kabarcık sıralamadan daha hızlı.
Cüce sıralama	n	${\görüntüleme stili n^{2}}$	${\görüntüleme stili n^{2}}$	1	Evet	değiş tokuş	Küçük kod boyutu.
Tek-çift sıralama	n	${\görüntüleme stili n^{2}}$	${\görüntüleme stili n^{2}}$	1	Evet	değiş tokuş	Paralel işlemcilerde kolayca çalıştırılabilir.

Karşılaştırmasız türler

Aşağıdaki tabloda, tamsayı sıralama algoritmaları ve karşılaştırmalı sıralama olmayan diğer sıralama algoritmaları açıklanmaktadır . Bu nedenle, Ω ( n log n ) ile sınırlı değildirler . Aşağıdaki karmaşıklıklar , sıralanacak n öğenin, k boyutunda anahtarlar, d rakam boyutu ve r sıralanacak sayı aralığıyla birlikte olduğunu varsayar . Bunların çoğu, anahtar boyutunun, tüm girdilerin benzersiz anahtar değerlerine sahip olacak kadar büyük olduğu ve dolayısıyla n ≪ 2 ^k , burada ≪ "çok daha az" anlamına geldiği varsayımına dayanmaktadır . Birim maliyetli rastgele erişimli makine modelinde, sayı tabanı sıralama gibi çalışma süresine sahip algoritmalar hala Θ( n log n ) ile orantılı zaman alır , çünkü n , 'den fazla olmamakla ve daha fazla sayıda öğeyle sınırlıdır sıralamak, onları hafızada saklamak için daha büyük bir k gerektirir . ${\displaystyle \scriptstyle n\cdot {\frac {k}{d}}}$${\ Displaystyle 2^{\frac {k}{d}}}$

Karşılaştırmasız türler

İsim	En iyisi	Ortalama	En kötüsü	Hafıza	Kararlı	n ≪ 2k	Notlar
Güvercin deliği sıralama	-	${\görüntüleme stili n+2^{k}}$	${\görüntüleme stili n+2^{k}}$	${\ Displaystyle 2^{k}}$	Evet	Evet	Tamsayı olmayanlar sıralanamaz.
Kova sıralama (tek tip tuşlar)	-	${\görüntüleme stili n+k}$	${\displaystyle n^{2}\cdot k}$	${\displaystyle n\cdot k}$	Evet	Numara	Dizideki etki alanından öğelerin düzgün dağılımını varsayar. Ayrıca tamsayı olmayanları sıralayamaz
Kova sıralama (tamsayı tuşları)	-	${\görüntüleme stili n+r}$	${\görüntüleme stili n+r}$	${\görüntüleme stili n+r}$	Evet	Evet	Eğer r ise , o zaman ortalama süre karmaşıklığı olduğunu . ${\görüntüleme stili O(n)}$${\görüntüleme stili O(n)}$
sayma sıralama	-	${\görüntüleme stili n+r}$	${\görüntüleme stili n+r}$	${\görüntüleme stili n+r}$	Evet	Evet	Eğer r ise , o zaman ortalama süre karmaşıklığı olduğunu . ${\görüntüleme stili O(n)}$${\görüntüleme stili O(n)}$
LSD Radix Sıralaması	${\görüntüleme stili n}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\görüntüleme stili n+2^{d}}$	Evet	Numara	${\displaystyle {\frac {k}{d}}}$yineleme seviyeleri, sayı dizisi için 2 d . Çoğu dağıtım türünden farklı olarak, bu, Kayan noktalı sayıları , negatif sayıları ve daha fazlasını sıralayabilir .
MSD Radix Sıralaması	-	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\görüntüleme stili n+2^{d}}$	Evet	Numara	Kararlı sürüm, tüm kutuları tutmak için n boyutunda harici bir dizi kullanır . LSD varyantı ile aynı, tamsayı olmayanları sıralayabilir.
MSD Radix Sıralaması (yerinde)	-	${\displaystyle n\cdot {\frac {k}{1}}}$	${\displaystyle n\cdot {\frac {k}{1}}}$	${\görüntüleme stili 2^{1}}$	Numara	Numara	yerinde, özyineleme seviyeleri için d=1 , sayım dizisi yok. ${\görüntüleme stili k/1}$
elektronik sıralama	n	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot \sol({{\frac {k}{s}}+d}\sağ)}$	${\displaystyle {\frac {k}{d}}\cdot 2^{d}}$	Numara	Numara	Asimptotik, n ≪ 2 k olduğu varsayımına dayanır , ancak algoritma bunu gerektirmez.
seri sıralama	-	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	Numara	Numara	Dizeleri sıralamak için sayı tabanı sıralamasından daha iyi sabit faktöre sahiptir. Her ne kadar yaygın olarak karşılaşılan dizelerin özelliklerine biraz güvenir.
Flaş sıralama	n	${\görüntüleme stili n+r}$	${\görüntüleme stili n^{2}}$	n	Numara	Numara	Doğrusal zamanda çalışması için dizideki etki alanındaki öğelerin tek tip dağılımını gerektirir. Dağılım aşırı derecede çarpıksa, temel sıralama ikinci dereceden ise (genellikle bir ekleme sıralamadır) ikinci dereceden olabilir. Yerinde sürüm kararlı değil.
Postacı sıralama	-	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\görüntüleme stili n+2^{d}}$	-	Numara	MSD Radix Sort'a çok benzer şekilde çalışan bir kova sıralama varyasyonu. Posta hizmeti ihtiyaçlarına özel.

Samplesort , verileri birkaç kovaya verimli bir şekilde dağıtarak ve ardından sıralamayı birkaç işlemciye aktararak, kovalar zaten kendi aralarında sıralandığından birleştirmeye gerek kalmadan karşılaştırma olmayan sıralamalardan herhangi birini paralelleştirmek için kullanılabilir.

Diğerleri

Sınırsız çalışma süresine sahip bogosort ve O ( n ^2.7 ) çalışma süresine sahip yardakçı sıralama gibi bazı algoritmalar yukarıda tartışılanlara kıyasla yavaştır . Bu türler, algoritmaların çalışma süresinin nasıl tahmin edildiğini göstermek için genellikle eğitim amaçlı olarak tanımlanır. Aşağıdaki tabloda, son derece düşük performans veya özel donanım gereksinimleri nedeniyle geleneksel yazılım bağlamlarında gerçek hayatta kullanım için pratik olmayan bazı sıralama algoritmaları açıklanmaktadır.

İsim	En iyisi	Ortalama	En kötüsü	Hafıza	Kararlı	Karşılaştırmak	Diğer notlar
boncuk sıralama	n	S	S	${\görüntüleme stili n^{2}}$	Yok	Numara	Yalnızca pozitif tam sayılarla çalışır. Garantili sürede çalışması için özel donanım gerektirir . Yazılım uygulaması için bir olasılık vardır, ancak çalışma süresi olacaktır , burada S sıralanacak tüm tam sayıların toplamıdır, küçük tamsayılar olması durumunda doğrusal olarak kabul edilebilir. ${\görüntüleme stili O(n)}$${\görüntüleme stili O(S)}$
Basit gözleme sıralama	-	n	n	${\görüntüleme stili \log n}$	Numara	Evet	Sayı, çevirme sayısıdır.
Spagetti (Anket) sıralama	n	n	n	${\görüntüleme stili n^{2}}$	Evet	yoklama	Bu, O ( n ) yığın alanı gerektiren bir dizi öğeyi sıralamak için doğrusal zamanlı, analog bir algoritmadır ve sıralama kararlıdır. Bu, n paralel işlemci gerektirir . Bkz. spagetti sıralama#Analiz .
Sıralama ağı	değişir	değişir	değişir	değişir	Değişir (kararlı sıralama ağları daha fazla karşılaştırma gerektirir)	Evet	Karşılaştırma sırası, sabit bir ağ boyutuna göre önceden belirlenir.
bitonik sıralayıcı	${\displaystyle \log ^{2}n}$ paralel	${\displaystyle \log ^{2}n}$ paralel	${\displaystyle n\log ^{2}n}$ paralel olmayan	1	Numara	Evet	Sıralama ağlarının etkili bir varyasyonu.
Bogosort	n	${\görüntüleme stili (n\ kere n!)}$	sınırsız (kesin), (beklenen)${\görüntüleme stili (n\ kere n!)}$	1	Numara	Evet	Rastgele karıştırma. Beklenen en iyi durum çalışma zamanı bile korkunç olduğundan, yalnızca örnek amaçlı kullanılır.
yardakçı sıralama	${\ Displaystyle n^{\log 3/\log 1.5}}$	${\ Displaystyle n^{\log 3/\log 1.5}}$	${\ Displaystyle n^{\log 3/\log 1.5}}$	n	Numara	Evet	O ( n log 3 / log 1.5 ) = O ( n 2.7095... ) zaman karmaşıklığına sahip sıralama algoritmalarının çoğundan daha yavaş (saf olanlar bile) kararlı hale getirilebilir ve aynı zamanda bir sıralama ağıdır .
Yavaş sıralama	${\görüntüleme stili n^{\log n}}$	${\görüntüleme stili n^{\log n}}$	${\görüntüleme stili n^{\log n}}$	n	Numara	Evet	Böl ve yönet algoritmasının zıttı olan bir çarpma ve teslim etme algoritması .

Teorik bilgisayar bilimcileri , aşağıdakiler dahil olmak üzere ek kısıtlamalar varsayarak O ( n log n ) zaman karmaşıklığından daha iyi sağlayan ayrıntılı diğer sıralama algoritmalarına sahiptir :

• Thorup'un algoritması , O ( n log log n ) zaman ve O ( n ) boşluk alarak, sonlu boyuttaki bir etki alanından anahtarları sıralamak için rastgele bir algoritma .
• Beklenen zaman ve O ( n ) boşluk alan rastgele bir tamsayı sıralama algoritması .${\displaystyle O\sol(n{\sqrt {\log \log n}}\sağ)}$

Popüler sıralama algoritmaları

Çok sayıda sıralama algoritması varken, pratik uygulamalarda birkaç algoritma baskındır. Yerleştirmeli sıralama, küçük veri kümeleri için yaygın olarak kullanılırken, büyük veri kümeleri için asimptotik olarak verimli bir sıralama kullanılır, öncelikle yığın sıralama, birleştirme sıralama veya hızlı sıralama kullanılır. Verimli uygulamalar genellikle , genel sıralama için asimptotik olarak verimli bir algoritmayı, bir özyinelemenin altındaki küçük listeler için ekleme sıralama ile birleştiren bir hibrit algoritma kullanır . Yüksek düzeyde ayarlanmış uygulamalar , Android, Java ve Python'da kullanılan Timsort (birleştirme sıralama, ekleme sıralama ve ek mantık) ve bazı C++ sıralamalarında kullanılan introsort (hızlı sıralama ve yığın sıralama) gibi daha karmaşık değişkenler kullanır. uygulamalarda ve .NET'te.

Sabit bir aralıktaki sayılar gibi daha kısıtlı veriler için, sayım sıralaması veya sayı tabanı sıralaması gibi dağıtım sıralamaları yaygın olarak kullanılır. Kabarcık sıralama ve varyantları pratikte nadiren kullanılır, ancak öğretimde ve teorik tartışmalarda yaygın olarak bulunur.

Nesneleri fiziksel olarak sıralarken (kağıtları, testleri veya kitapları alfabetik olarak sıralarken), insanlar genellikle küçük kümeler için eklemeli sıralamaları sezgisel olarak kullanır. Daha büyük kümeler için, insanlar genellikle ilk harfe göre ilk kepçe ve çoklu kepçe, çok büyük kümelerin pratik olarak sıralanmasını sağlar. Nesneleri zemine veya geniş bir alana yaymak gibi genellikle alan nispeten ucuzdur, ancak işlemler pahalıdır, özellikle bir nesneyi büyük bir mesafeye taşımak – referansın yeri önemlidir. Birleştirme sıralamaları, fiziksel nesneler için de pratiktir, özellikle her listenin birleştirilmesi için bir tane olmak üzere iki el kullanılabilirken, yığın sıralama veya hızlı sıralama gibi diğer algoritmalar insan kullanımı için pek uygun değildir. Yerleştirme sıralamasının boşluk bırakan bir çeşidi olan library sort gibi diğer algoritmalar da fiziksel kullanım için pratiktir.

Basit çeşitler

En basit türlerden ikisi, eklemeli sıralama ve seçmeli sıralamadır; bunların her ikisi de düşük ek yük nedeniyle küçük verilerde etkilidir, ancak büyük verilerde verimli değildir. Ekleme sıralama, neredeyse sıralanmış veriler üzerinde daha az karşılaştırma ve iyi performans nedeniyle pratikte genellikle seçim sıralamadan daha hızlıdır ve bu nedenle uygulamada tercih edilir, ancak seçim sıralama daha az yazma kullanır ve bu nedenle yazma performansı sınırlayıcı bir faktör olduğunda kullanılır.

Ekleme sıralama

Ekleme sıralama , küçük listeler ve çoğunlukla sıralanmış listeler için nispeten verimli olan ve genellikle daha karmaşık algoritmaların parçası olarak kullanılan basit bir sıralama algoritmasıdır. Listeden öğeleri tek tek alarak ve bunları cüzdanımıza nasıl para koyduğumuza benzer şekilde yeni bir sıralanmış listeye doğru konumlarına ekleyerek çalışır. Dizilerde, yeni liste ve kalan öğeler dizinin alanını paylaşabilir, ancak ekleme pahalıdır ve aşağıdaki tüm öğelerin birer birer kaydırılmasını gerektirir. Shellsort (aşağıya bakın), daha büyük listeler için daha verimli olan bir eklemeli sıralama çeşididir.

Seçim sıralaması

Seçimli sıralama , yerinde karşılaştırmalı bir sıralamadır . Bu sahip O ( n, ² , büyük listelerinde verimsiz hale) karmaşıklığı ve genellikle benzer daha kötü performans sıralama yerleştirilmesi . Seçim sıralama basitliği ile dikkat çeker ve ayrıca belirli durumlarda daha karmaşık algoritmalara göre performans avantajlarına sahiptir.

Algoritma minimum değeri bulur, ilk konumdaki değerle değiştirir ve bu adımları listenin geri kalanı için tekrarlar. N tane takastan fazlasını yapmaz ve bu nedenle takasın çok pahalı olduğu durumlarda kullanışlıdır.

Verimli çeşitler

Pratik genel sıralama algoritmaları neredeyse her zaman ortalama zaman karmaşıklığına (ve genellikle en kötü durum karmaşıklığına) sahip bir algoritmaya dayanır (ve genellikle en kötü durum karmaşıklığı) O( n log n ) bunların en yaygınları yığın sıralama, birleştirme sıralama ve hızlı sıralamadır. Her birinin avantajları ve dezavantajları vardır, en önemlisi, birleştirme sıralamasının basit uygulamasının O( n ) ek alan kullanması ve hızlı sıralamanın basit uygulamasının O( n ² ) en kötü durum karmaşıklığına sahip olmasıdır. Bu problemler, daha karmaşık bir algoritma pahasına çözülebilir veya iyileştirilebilir.

Bu algoritmalar rastgele veriler üzerinde asimptotik olarak verimli olsa da, gerçek dünya verileri üzerinde pratik verimlilik için çeşitli modifikasyonlar kullanılır. İlk olarak, bu algoritmaların ek yükü daha küçük veriler üzerinde önemli hale gelir, bu nedenle genellikle veriler yeterince küçük olduğunda eklemeli sıralamaya geçen hibrit bir algoritma kullanılır. İkincisi, algoritmalar zaten sıralanmış verilerde veya neredeyse sıralanmış verilerde genellikle kötü performans gösterir - bunlar gerçek dünya verilerinde yaygındır ve uygun algoritmalar tarafından O( n ) zamanında sıralanabilir . Son olarak, aynı zamanda kararsız da olabilirler ve kararlılık genellikle bir türde istenen bir özelliktir. Bu nedenle, Timsort (birleştirme sıralamasına dayalı) veya introsort (hızlı sıralamaya dayalı, yığın sıralamasına geri dönme) gibi daha karmaşık algoritmalar sıklıkla kullanılır .

Sıralamayı birleştir

Birleştirme sıralama , önceden sıralanmış listeleri yeni bir sıralanmış listede birleştirme kolaylığından yararlanır. Her iki öğeyi karşılaştırarak başlar (yani, 1 ile 2, sonra 3 ile 4...) ve eğer birincisi ikinciden sonra gelecekse bunları değiştirerek başlar. Daha sonra, ortaya çıkan iki listenin her birini dörtlü listeler halinde birleştirir, ardından bu dörtlü listeleri birleştirir ve bu şekilde devam eder; en son iki liste nihai sıralanmış listede birleştirilene kadar. Burada açıklanan algoritmalardan, çok büyük listelere iyi ölçeklenen ilk algoritmadır, çünkü en kötü durum çalışma süresi O( n log n )'dir. Rastgele erişim değil, yalnızca sıralı erişim gerektirdiğinden, yalnızca dizilere değil, listelere de kolayca uygulanır. Ancak, ek O( n ) uzay karmaşıklığına sahiptir ve basit uygulamalarda çok sayıda kopya içerir.

Birleştirme sıralama, Python ve Java programlama dillerinde ( JDK7'den itibaren ) standart sıralama rutini için kullanılan karmaşık Timsort algoritmasında kullanılması nedeniyle, pratik uygulamalar için popülerlikte nispeten yeni bir artış gördü . Merge sort'un kendisi, diğerleri arasında Perl'deki standart rutindir ve Java'da en az 2000'den beri JDK1.3'te kullanılmaktadır .

yığın sıralaması

Heapsort , seçim sıralamanın çok daha verimli bir versiyonudur . Ayrıca, listenin en büyük (veya en küçük) öğesini belirleyerek, bunu listenin sonuna (veya başına) yerleştirerek ve ardından listenin geri kalanıyla devam ederek çalışır, ancak bu görevi, bir veri yapısını kullanarak verimli bir şekilde gerçekleştirir. yığın , özel bir ikili ağaç türü . Veri listesi bir yığın haline getirildikten sonra, kök düğümün en büyük (veya en küçük) eleman olması garanti edilir. Kaldırıldığında ve listenin sonuna yerleştirildiğinde, kalan en büyük öğe köke taşınacak şekilde yığın yeniden düzenlenir. Yığın kullanarak, bir sonraki en büyük öğeyi bulmak, basit seçim sıralamasında olduğu gibi doğrusal bir tarama için O( n ) yerine O(log n ) zaman alır . Bu, Heapsort'un O( n log n ) zamanında çalışmasına izin verir ve bu aynı zamanda en kötü durum karmaşıklığıdır.

Hızlı sıralama

Quicksort a, Böl ve yen algoritması bir dayanır bölüm , bir dizi, bir adlandırılan bir eleman bölme: operasyon eksen seçilir. Pivottan daha küçük olan tüm elemanlar ondan önce ve daha büyük olan bütün elemanlar ondan sonra hareket ettirilir. Bu, doğrusal zamanda ve yerinde verimli bir şekilde yapılabilir . Daha küçük ve daha büyük alt listeler daha sonra özyinelemeli olarak sıralanır. Bu , düşük ek yük ile O( n log n )' nin ortalama zaman karmaşıklığını verir ve bu nedenle bu popüler bir algoritmadır. Hızlı sıralamanın verimli uygulamaları (yerinde bölümleme ile) tipik olarak kararsız sıralamalardır ve biraz karmaşıktır, ancak pratikte en hızlı sıralama algoritmaları arasındadır. Mütevazı O(log n ) alan kullanımıyla birlikte hızlı sıralama, en popüler sıralama algoritmalarından biridir ve birçok standart programlama kitaplığında bulunur.

Quicksort ile ilgili önemli uyarı, en kötü durum performansının O( n ² ); Bu nadir olmakla birlikte, saf uygulamalarda (pivot olarak ilk veya son öğenin seçilmesi) bu, sıralanmış veriler için ortaya çıkar, bu yaygın bir durumdur. Bu nedenle hızlı sıralamadaki en karmaşık sorun iyi bir pivot elemanı seçmektir, çünkü sürekli olarak zayıf pivot seçimleri büyük ölçüde daha yavaş O( n ² ) performansına neden olabilir, ancak iyi pivot seçimi O( n log n ) asimptotik olarak optimal olan performansı verir. . Örneğin, her adımda medyan pivot olarak seçilirse, algoritma O( n  log  n ) içinde çalışır. Gibi ilgili medyan, bulma medyan medyan seçme algoritması , ancak bir O (bir n- sıralanmamış listelerinde) işlemi ve bu nedenle ayırma büyük masraf Balder Ölümsüz. Pratikte rastgele bir pivot seçmek neredeyse kesinlikle O( n  log  n ) performansı sağlar.

Kabuk sıralaması

Öğeleri çok sayıda değiş tokuş pozisyonuna taşımasıyla kabarcıklı sıralamadan farklı bir Shellsort .

Shellsort , Donald Shell tarafından 1959'da icat edildi . Sıra dışı öğeleri aynı anda birden fazla konuma taşıyarak eklemeli sıralamayı geliştirir. Shellsort'un arkasındaki konsept, eklemeli sıralamanın zaman içinde gerçekleştirilmesidir ; burada k, iki yerinde olmayan öğe arasındaki en büyük mesafedir. Bu, genel olarak, O ( n ² ) ' de performans gösterdikleri , ancak yalnızca birkaç öğenin yerinde olmadığı çoğunlukla sıralanmış veriler için daha hızlı performans gösterdikleri anlamına gelir. Bu nedenle, önce öğeleri uzakta sıralayarak ve sıralamak için öğeler arasındaki boşluğu aşamalı olarak daraltarak, son sıralama çok daha hızlı hesaplanır. Bir uygulama, veri dizisini iki boyutlu bir dizide düzenlemek ve ardından eklemeli sıralamayı kullanarak dizinin sütunlarını sıralamak olarak tanımlanabilir. ${\görüntüleme stili O(kn)}$

Shellsort'un en kötü durum zaman karmaşıklığı açık bir problemdir ve O ( n ² ) ile O ( n ^4/3 ) ve Θ( n log ² n ) arasında değişen bilinen karmaşıklıklarla birlikte kullanılan boşluk dizisine bağlıdır . Bu, Shellsort'un yerinde olması , yalnızca nispeten az miktarda koda ihtiyaç duyması ve çağrı yığınının kullanılmasını gerektirmemesi gerçeğiyle birleştiğinde , gömülü sistemler gibi belleğin önemli olduğu durumlarda kullanışlı olmasını sağlar. ve işletim sistemi çekirdekleri .

Kabarcık sıralama ve çeşitleri

Kabarcık sıralama ve Shellsort ve kokteyl sıralama gibi değişkenler basit, oldukça verimsiz sıralama algoritmalarıdır. Analiz kolaylığı nedeniyle giriş metinlerinde sıklıkla görülürler, ancak pratikte nadiren kullanılırlar.

Kabarcık sıralama

Kabarcıklı sıralama, sürekli bir listede adım adım ilerleyen, öğeleri doğru sırada görünene kadar değiştiren bir sıralama algoritması .

Kabarcık sıralama basit bir sıralama algoritmasıdır. Algoritma, veri setinin başlangıcında başlar. İlk iki öğeyi karşılaştırır ve eğer birincisi ikinciden büyükse, onları değiştirir. Bunu, veri kümesinin sonuna kadar her bir bitişik eleman çifti için yapmaya devam eder. Daha sonra ilk iki elemanla tekrar başlar ve son geçişte hiçbir takas gerçekleşmeyinceye kadar tekrarlanır. Bu algoritmanın ortalama süresi ve en kötü durum performansı O( n ² )'dir, bu nedenle büyük, sırasız veri kümelerini sıralamak için nadiren kullanılır. Kabarcık sıralama, az sayıda öğeyi sıralamak için kullanılabilir (burada asimptotik verimsizliği yüksek bir ceza değildir). Kabarcık sıralama, hemen hemen sıralanan herhangi bir uzunluktaki bir listede de verimli bir şekilde kullanılabilir (yani, öğeler önemli ölçüde yerinde değildir). Örneğin, herhangi bir sayıda öğe yalnızca bir konumda yersizse (örneğin 0123546789 ve 1032547698), kabarcık sıralamanın değişimi onları ilk geçişte sırayla alacak, ikinci geçiş tüm öğeleri sırayla bulacaktır, böylece sıralama sadece 2 n zaman ayırın.

tarak sıralama

Tarak sıralama , kabarcık sıralamaya dayalı nispeten basit bir sıralama algoritmasıdır ve orijinal olarak 1980 yılında Włodzimierz Dobosiewicz tarafından tasarlanmıştır. Daha sonra Stephen Lacey ve Richard Box tarafından Nisan 1991'de yayınlanan bir Byte Magazine makalesiyle yeniden keşfedildi ve popüler hale getirildi . Temel fikir kaplumbağaları ortadan kaldırmaktır. veya listenin sonuna yakın küçük değerler, çünkü bir baloncuk sıralamasında bunlar sıralamayı çok yavaşlatır. ( Tavşanlar , listenin başındaki büyük değerler, kabarcık sıralamada sorun oluşturmaz) Bunu, yalnızca bitişik ise öğeleri değiştirmek yerine, başlangıçta dizide birbirinden belirli bir mesafede olan öğeleri değiştirerek gerçekleştirir. ve ardından normal bir baloncuk sıralaması olarak çalışana kadar seçilen mesafeyi küçültün. Bu nedenle, Shellsort, birbirinden belirli bir uzaklıkta bulunan öğeleri değiştiren eklemeli sıralamanın genelleştirilmiş bir versiyonu olarak düşünülebilirse, tarak sıralama, kabarcık sıralamaya uygulanan aynı genelleme olarak düşünülebilir.

Değişim sıralaması

Algoritmalar aslında farklı olsa da, değişim sıralama bazen kabarcık sıralama ile karıştırılır. Değişim sıralaması, ilk öğeyi üzerindeki tüm öğelerle karşılaştırarak, gerektiğinde değiş tokuş ederek çalışır, böylece ilk öğenin son sıralama düzeni için doğru olduğunu garanti eder; daha sonra ikinci eleman için aynısını yapmaya devam eder ve bu böyle devam eder. Liste zaten sıralanmışsa kabarcık sıralamanın tek geçişte algılama avantajından yoksundur, ancak sabit bir faktöre göre kabarcık sıralamadan daha hızlı olabilir (sıralanacak veriler üzerinde bir geçiş eksik; toplam karşılaştırmanın yarısı kadar) en kötü durum durumları. Herhangi bir basit O( n ² ) sıralama gibi, çok küçük veri kümeleri üzerinde oldukça hızlı olabilir, ancak genel olarak ekleme sıralama daha hızlı olacaktır.

dağıtım sıralaması

Dağıtım sıralama , verilerin girdilerinden daha sonra toplanıp çıktıya yerleştirilen çoklu ara yapılara dağıtıldığı herhangi bir sıralama algoritmasını ifade eder. Örneğin, her iki kova sıralama ve flashsort dağıtım esaslı sıralama algoritmaları vardır. Dağıtım sıralama algoritmaları, tek bir işlemcide kullanılabilir veya ayrı alt kümelerin farklı işlemcilerde ayrı ayrı sıralanıp daha sonra birleştirildiği dağıtılmış bir algoritma olabilir . Bu, tek bir bilgisayarın belleğine sığmayacak kadar büyük verilerin harici olarak sıralanmasına olanak tanır .

sayma sıralama

Sayma sıralaması, her girdinin belirli bir olasılık kümesine ( S) ait olduğu bilindiğinde uygulanabilir . Algoritma, O(| S | + n ) zamanında ve O(| S |) belleğinde çalışır, burada n , girişin uzunluğudur. Bir tamsayı boyutu dizisi oluşturarak çalışır | S | ve kullanma i inci bin yineleme sayısını i th üyesi S girişinde. Her giriş daha sonra karşılık gelen bölmenin değeri artırılarak sayılır. Daha sonra, tüm girişleri sırayla düzenlemek için sayma dizisi döngüye alınır. Bu sıralama algoritması genellikle kullanılamaz çünkü algoritmanın verimli olması için S'nin oldukça küçük olması gerekir, ancak son derece hızlıdır ve n arttıkça harika asimptotik davranış gösterir . Ayrıca kararlı davranış sağlamak için değiştirilebilir.

kova sıralama

Kova sıralama, bir diziyi sınırlı sayıda kovaya bölerek sayma sıralamasını genelleştiren bir böl ve yönet sıralama algoritmasıdır . Daha sonra her bir kova, ya farklı bir sıralama algoritması kullanılarak ya da kova sıralama algoritmasının yinelemeli bir şekilde uygulanmasıyla ayrı ayrı sıralanır.

Bir paket sıralama, veri kümesinin öğeleri tüm paketlere eşit olarak dağıtıldığında en iyi sonucu verir.

Radix sıralama

Radix sıralama , sayıları tek tek basamakları işleyerek sıralayan bir algoritmadır. k basamaktan oluşan n sayı, her biri O( n · k ) zamanında sıralanır . Radix sıralama, en az anlamlı basamaktan (LSD) başlayarak veya en önemli basamaktan (MSD) başlayarak her bir sayının basamaklarını işleyebilir . LSD algoritması, kararlı bir sıralama kullanarak göreli sırasını korurken ilk önce listeyi en az anlamlı basamağa göre sıralar. Ardından bunları bir sonraki basamağa göre sıralar ve böylece en önemsizden en önemliye doğru sıralanmış bir listeyle sonuçlanır. LSD taban sıralaması, kararlı bir sıralama kullanılmasını gerektirse de, MSD taban sıralama algoritması bunu gerektirmez (kararlı sıralama istenmedikçe). Yerinde MSD sayı tabanı sıralaması kararlı değil. Sayım sıralama algoritmasının, sayı tabanı sıralaması tarafından dahili olarak kullanılması yaygındır . Bir hibrid kullanmak gibi sıralama yaklaşım, ekleme tür küçük kutuları için, sıralama önemli sayı tabanı performansını artırır.

Bellek kullanım kalıpları ve dizin sıralama

Sıralanacak dizinin boyutu mevcut birincil belleğe yaklaştığında veya onu aştığında, (çok daha yavaş) disk veya takas alanı kullanılması gerektiğinde, bir sıralama algoritmasının bellek kullanım modeli önemli hale gelir ve oldukça uygun olabilecek bir algoritma. dizi RAM'e kolayca sığdığında verimli hale gelebilir. Bu senaryoda, toplam karşılaştırma sayısı (nispeten) daha az önemli hale gelir ve bellek bölümlerinin diske ve diskten kaç kez kopyalanması veya değiştirilmesi gerektiği, bir algoritmanın performans özelliklerine hükmedebilir. Bu nedenle, geçiş sayısı ve karşılaştırmaların yerelleştirilmesi ham karşılaştırma sayısından daha önemli olabilir, çünkü yakındaki öğelerin birbirleriyle karşılaştırmaları sistem veriyolu hızında (veya önbelleğe alma ile, hatta CPU hızında) gerçekleşir. disk hızına, neredeyse anında.

Örneğin, popüler özyinelemeli hızlı sıralama algoritması, yeterli RAM ile oldukça makul bir performans sağlar, ancak dizinin bölümlerini kopyalamanın özyinelemeli yolu nedeniyle, dizi RAM'e sığmadığında çok daha az pratik hale gelir, çünkü bir dizi neden olabilir. diske ve diskten yavaş kopyalama veya taşıma işlemleri. Bu senaryoda, daha fazla toplam karşılaştırma gerektirse bile başka bir algoritma tercih edilebilir.

Karmaşık kayıtlar ( ilişkisel veritabanında olduğu gibi ) nispeten küçük bir anahtar alana göre sıralanırken işe yarayan bu soruna geçici bir çözüm bulmanın bir yolu , dizide bir dizin oluşturmak ve ardından dizini tamamı yerine sıralamaktır. dizi. (Bütün dizinin sıralanmış bir versiyonu daha sonra dizinden okuma yaparak tek geçişle üretilebilir, ancak sıralanmış dizine sahip olmak yeterli olduğundan, çoğu zaman bu bile gereksizdir.) Dizin tüm diziden çok daha küçük olduğu için, olabilir. tüm dizinin olmayacağı yerde belleğe kolayca sığdırarak disk değiştirme sorununu etkin bir şekilde ortadan kaldırır. Bu prosedür bazen "etiket sıralama" olarak adlandırılır.

Bellek boyutu sorununun üstesinden gelmek için başka bir teknik, harici sıralama kullanmaktır ; örneğin, yollardan biri, genel performansı artırmak için her birinin gücünden yararlanacak şekilde iki algoritmayı birleştirmektir. Örneğin, dizi, RAM'e sığacak boyutta parçalara bölünebilir, her parçanın içeriği verimli bir algoritma kullanılarak sıralanabilir ( hızlı sıralama gibi ) ve sonuçlar , kullanılana benzer bir k- yollu birleştirme kullanılarak birleştirilebilir. sıralama birleştirme . Bu, tüm liste üzerinde birleştirme sıralama veya hızlı sıralama gerçekleştirmekten daha hızlıdır.

Teknikler de birleştirilebilir. Sistem belleğini büyük ölçüde aşan çok büyük veri kümelerini sıralamak için, dizinin bile bir algoritma veya sanal bellekle makul düzeyde performans gösterecek , yani gerekli takas miktarını azaltmak için tasarlanmış algoritmalar kombinasyonu kullanılarak sıralanması gerekebilir.

İlgili algoritmalar

İlgili diğer sorunlar kısmen sıralama (sadece ayırma k listenin en küçük elemanlar, ya da seçenek olarak işlem k küçük elemanlar, ancak düzensiz) ve seçimi (işlem k inci en küçük elemanı). Bunlar, toplam sıralama ile verimsiz bir şekilde çözülebilir, ancak genellikle bir sıralama algoritmasının genelleştirilmesiyle elde edilen daha verimli algoritmalar mevcuttur. En dikkate değer örnek, quicksort ile ilgili olan quickselect'tir . Tersine, bazı sıralama algoritmaları, bir seçim algoritmasının tekrarlanan uygulamasıyla türetilebilir; hızlı sıralama ve hızlı seçim, yalnızca birinin her iki tarafta (hızlı sırala, böl ve yönet ) veya bir tarafta (hızlı seçim, azalt ve fethet ) yinelenmesinde farklılık gösteren aynı döndürme hareketi olarak görülebilir .

Sıralama algoritmasının bir tür zıttı karıştırma algoritmasıdır . Bunlar temelde farklıdır çünkü bir rasgele sayı kaynağı gerektirirler. Karıştırma ayrıca bir sıralama algoritması ile, yani rastgele bir sıralama ile gerçekleştirilebilir: listenin her bir öğesine rastgele bir sayı atama ve ardından rastgele sayılara göre sıralama. Ancak bu genellikle pratikte yapılmaz ve karıştırma için iyi bilinen basit ve etkili bir algoritma vardır: Fisher-Yates shuffle .

Ayrıca bakınız

• Harmanlama  – Yazılı bilgilerin standart bir düzende birleştirilmesi
• Schwartzian dönüşümü
• Arama algoritması  – Arama problemini çözen herhangi bir algoritma
• Kuantum sıralama  – Kuantum bilgisayarlar için sıralama algoritmaları

Referanslar

daha fazla okuma

• Knuth, Donald E. (1998), Sıralama ve Arama , Bilgisayar Programlama Sanatı, 3 (2. baskı), Boston: Addison-Wesley, ISBN 0-201-89685-0
• Sedgewick, Robert (1980), "Bilgisayarla Verimli Sıralama: Bir Giriş", Hesaplamalı Olasılık , New York: Academic Press, s.  101–130 , ISBN 0-12-394680-8

Dış bağlantılar

• Algoritma Animasyonlar Sıralama de Wayback Machine (2015 Mart 3 arşivlenmiş).
• Sıralı ve paralel sıralama algoritmaları – Birçok sıralama algoritmasının açıklamaları ve analizleri.
• Algoritmalar, Veri Yapıları ve Problemler Sözlüğü – Algoritmalar, teknikler, ortak işlevler ve problemler sözlüğü.
• Sıralama Algoritmaları Üzerine Biraz Şüpheci Bakış - Birkaç klasik algoritmayı tartışır ve hızlı sıralama algoritmasına alternatifleri teşvik eder .
• 6 Dakikada 15 Sıralama Algoritması (Youtube) – 6 Dakikada 15 Sıralama Algoritmasının Görselleştirilmesi ve "duyulması".
• OEIS veritabanındaki "Sıralama sayıları: n öğeyi sıralamak için gereken minimum karşılaştırma sayısı" başlıklı A036604 dizisi – Ford–Johnson algoritması tarafından gerçekleştirilir .
• Ünlü Tablolarda Kullanılan Sıralama Algoritmaları (Youtube) - Birçok Ünlü Tabloda Sıralama Algoritmalarının Görselleştirilmesi.
• Sıralama Algoritmalarının Karşılaştırılması - Python timeit ve Google Colab kullanarak 9 ana sıralama algoritmasının bir dizi testini çalıştırır.