Tamsayı sıralama - Integer sorting

Gelen bilgisayar bilimleri , sıralama tamsayı olduğu algoritmik problemi sıralama ile veri değerlerinin bir koleksiyon tamsayı tuşları. Tamsayı sıralama için tasarlanmış algoritmalar, anahtarların kayan nokta sayıları, rasyonel sayılar veya metin dizileri olduğu sıralama problemlerine de sıklıkla uygulanabilir . Anahtarlar üzerinde tamsayı aritmetiği gerçekleştirme yeteneği , hesaplama modelinde hangi işlemlere izin verildiğinin ayrıntılarına ve sıralanacak tamsayıların ne kadar büyük olduğuna bağlı olarak, tamsayı sıralama algoritmalarının birçok durumda karşılaştırmalı sıralama algoritmalarından daha hızlı olmasına olanak tanır .

Güvercin deliği sıralama , sayma sıralama ve sayı tabanı sıralama gibi tamsayı sıralama algoritmaları yaygın olarak kullanılır ve pratiktir. Daha küçük en kötü durum zaman sınırlarına sahip diğer tamsayı sıralama algoritmalarının, kelime başına 64 veya daha az bit içeren bilgisayar mimarileri için pratik olmadığına inanılmaktadır. Performansı sıralanacak öğe sayısı, anahtar başına bit sayısı ve sıralama algoritmasını gerçekleştiren bilgisayarın kelime başına bit sayısı kombinasyonuna bağlı olan bu tür birçok algoritma bilinmektedir.

Genel Değerlendirmeler

hesaplama modelleri

Tamsayı sıralama algoritmaları için zaman sınırları tipik olarak üç parametreye bağlıdır: sıralanacak veri değerlerinin sayısı $n$ , sıralanacak olası en büyük anahtarın büyüklüğü $K$ ve tek bir makine sözcüğünde temsil edilebilen bitlerin $w$ sayısı . Algoritmanın gerçekleştirileceği bilgisayar. Tipik olarak, $w \geq log 2 (max(n, K) )$ ; yani, makine sözcükleri, giriş verileri dizisine bir dizini temsil edecek kadar büyük ve ayrıca tek bir anahtarı temsil edecek kadar büyük.

Tamsayı sıralama algoritmaları genellikle ya işaretçi makinesinde ya da rastgele erişimli makine bilgi işlem modellerinde çalışmak üzere tasarlanmıştır . Bu iki model arasındaki temel fark, belleğin nasıl ele alınabileceğidir. Rastgele erişim makinesi, bir kayıtta saklanan herhangi bir değerin, işlem başına birim maliyetle birlikte bellek okuma ve yazma işlemlerinin adresi olarak kullanılmasına izin verir. Bu yetenek, veriler üzerinde belirli karmaşık işlemlerin tablo aramaları kullanılarak hızla uygulanmasına olanak tanır. Buna karşılık, işaretçi makinesi modelinde, okuma ve yazma işlemleri, işaretçilerde depolanan adresleri kullanır ve bu işaretçiler üzerinde aritmetik işlemler yapılmasına izin verilmez. Her iki modelde de veri değerleri eklenebilir ve bit düzeyinde Boolean işlemleri ve ikili kaydırma işlemleri de tipik olarak bunlar üzerinde işlem başına birim zamanda gerçekleştirilebilir. Farklı tamsayı sıralama algoritmaları, bir birim zamanlı işlem olarak tamsayı çarpmasına da izin verilip verilmediği konusunda farklı varsayımlarda bulunur. Paralel rasgele erişim makinesi gibi diğer daha özel hesaplama modelleri de, bir yorumda ilk olarak rasgele, ikinci olarak deterministik olarak ele alınmıştır; sonraki çalışmalar şunlardır

Andersson, Miltersen & Thorup (1999) , bazı durumlarda, bazı tamsayı sıralama algoritmalarının gerektirdiği çarpmaların veya tablo aramalarının, donanımda daha kolay uygulanabilecek, ancak tipik olarak genel amaçlı bilgisayarlarda bulunmayan özelleştirilmiş işlemlerle değiştirilebileceğini gösterdi. Thorup (2003) , bu özel işlemlerin Pentium işlemcilerinde zaten mevcut olan bit alanı işleme talimatlarıyla nasıl değiştirileceğini göstererek bunu geliştirdi .

Olarak işlem harici hafıza modelleri , bir sıralama algoritması daha hızlı karşılaştırma sıralama daha küçük bir tamsayı olduğu bilinmektedir. Araştırmacılar, bu modellerde, anahtarlarını nasıl değiştirecekleri konusunda sınırlı olan kısıtlı algoritma sınıflarının, karşılaştırmalı sıralamadan daha hızlı olamayacağını ve karşılaştırmalı sıralamadan daha hızlı bir tamsayı sıralama algoritmasının, standart bir varsayımın yanlışlığını ima edeceğini göstermiştir. ağ kodlama .

Tamsayı öncelik sıralarına karşı sıralama

Bir öncelik sırası , sayısal önceliklerle öğelerinden oluşan bir koleksiyonu muhafaza asgari öncelik değerine sahip öğeyi bulma ve çıkarma yönelik faaliyetleri bulunan bir veri yapısıdır. İkili yığın gibi karşılaştırmaya dayalı öncelik sıraları , güncelleme başına logaritmik zaman alır, ancak van Emde Boas ağacı veya kova kuyruğu gibi diğer yapılar , öncelikleri küçük tamsayılar olan girdiler için daha hızlı olabilir. Bu veri yapıları, koleksiyondaki en küçük öğeyi tekrar tekrar bulup çıkararak ve öğeleri bulundukları sırayla döndürerek bir öğe koleksiyonunu sıralayan seçim sıralama algoritmasında kullanılabilir . Bu algoritmadaki öğelerin koleksiyonunu korumak için bir öncelik sırası kullanılabilir ve bu algoritmanın $n$ öğeden oluşan bir koleksiyondaki zamanı, öncelik sırasını başlatma ve ardından $n$ bul ve kaldır işlemlerini gerçekleştirme süresi ile sınırlandırılabilir . Örneğin, seçim sıralamasında bir öncelik sırası olarak ikili bir yığın kullanılması , $O$ $($ $n$ $log$ $n$ $)$ zaman alan bir karşılaştırmalı sıralama algoritması olan yığın sıralama algoritmasına yol açar . Bunun yerine, bir kova kuyruğu ile seçim sıralamayı kullanmak, bir tür güvercin deliği sıralama biçimi verir ve van Emde Boas ağaçları veya diğer tamsayı öncelik sıralarını kullanmak, diğer hızlı tamsayı sıralama algoritmalarına yol açar.

Sıralama algoritmasında tamsayı öncelik sırası kullanmak yerine, diğer yöne gitmek ve tamsayı öncelik sırası veri yapısı içinde tamsayı sıralama algoritmalarını alt rutinler olarak kullanmak mümkündür. Thorup (2007) bu fikri, anahtar başına $T (n)$ zamanında tamsayı sıralaması yapmak mümkünse , o zaman aynı zaman sınırının bir öncelik sırası veri yapısındaki ekleme veya silme işlemi başına zaman için geçerli olduğunu göstermek için kullandı. Thorup'un indirgemesi karmaşıktır ve hızlı çarpma işlemlerinin veya tablo aramalarının kullanılabilirliğini varsayar, ancak aynı zamanda $T (n) + T (log n) + T (log log n)$ zamanı ile yalnızca toplama ve Boolean işlemlerini kullanarak alternatif bir öncelik sırası sağlar. $+ ...$ işlem başına, en fazla süreyi yinelenen bir logaritma ile çarparak .

kullanılabilirlik

Güvercin deliği sıralama , sayma sıralama ve sayı tabanı sıralama gibi klasik tamsayı sıralama algoritmaları yaygın olarak kullanılır ve pratiktir. Tamsayı sıralama algoritmaları üzerine yapılan sonraki araştırmaların çoğu, pratikliğe daha az ve en kötü durum analizindeki teorik gelişmelere daha fazla odaklanmıştır ve bu araştırma hattından gelen algoritmaların, mevcut 64-bit bilgisayar mimarileri için pratik olduğuna inanılmamaktadır. deneyler, bu yöntemlerden bazılarının, anahtar başına 128 veya daha fazla bit içeren veriler için sayı tabanı sıralamasında bir gelişme olabileceğini göstermiştir. Ek olarak, büyük veri kümeleri için, birçok tamsayı sıralama algoritmasının neredeyse rasgele bellek erişim modelleri , bellek hiyerarşisi göz önünde bulundurularak tasarlanmış karşılaştırmalı sıralama algoritmalarına kıyasla bunları engelleyebilir .

Tamsayı sıralama , DARPA High Productivity Computing Systems Discrete Mathematics karşılaştırma paketindeki altı kriterden birini ve NAS Parallel Benchmarks paketindeki on bir kriterden birini sağlar .

pratik algoritmalar

Güvercin deliği sıralama veya sayma sıralama , $O$ $($ $n$ $+$ $K$ $)$ zamanında $0$ ila $K$ $-1$ aralığında anahtarlara sahip $n$ veri öğesini sıralayabilir . In pigeonhole tür (genellikle denilen kova sıralama), veri öğelerine işaretçileri olarak temsil kovalar bir tablo, dağıtılır toplama gibi veri tipleri bağlantılı listeler tabloya endeksleri olarak tuşlarını kullanarak. Ardından, çıktı listesini oluşturmak için tüm kovalar bir araya getirilir. Sayma sıralaması, her bir tuşla öğe sayısını belirlemek için bir kova tablosu yerine bir sayaç tablosu kullanır. Ardından, her bir anahtara sahip değerlerin yerleştirilmesi gereken sıralanmış çıktıdaki konum aralığını belirlemek için bir önek toplamı hesaplaması kullanılır. Son olarak, giriş üzerinden ikinci bir geçişte, her öğe çıkış dizisindeki anahtarının konumuna taşınır. Her iki algoritma da giriş verileri ( $O$ $($ $n$ $)$ zamanını alır ) ve olası anahtarlar kümesi ( $O$ $($ $K$ $)$ zamanını alır $)$ üzerinde yalnızca basit döngüler içerir ve bunların $O$ $($ $n$ $+$ $K$ $)$ genel zaman sınırlarını verir.

Radix sıralama , veriler üzerinde birden çok geçiş gerçekleştirerek güvercin deliği sıralama veya sayma sıralamadan daha büyük anahtarlar için çalışan bir sıralama algoritmasıdır. Her geçiş, yalnızca küçük tuşlar için uygun olan farklı bir sıralama algoritması (güvercin deliği sıralama veya sayma sıralama gibi) kullanarak, tuşların yalnızca bir kısmını kullanarak girişi sıralar. Bölüme anahtarlarını kırmak için, basamağa göre sıralama algoritması hesaplar konumsal notasyonu bazı seçilmiş göre, her tuş için tabanda ; Daha sonra, anahtarın bir parçası için kullanılan $i$ algoritma inci geçişte olduğu $I$ tam anahtar için konumsal gösterimde inci basamak, en az önemli basamak başlayarak ve en önemli ilerleyen. Bu algoritmanın doğru çalışması için, veri üzerinden her geçişte kullanılan sıralama algoritmasının kararlı olması gerekir : basamakları eşit olan öğelerin birbirleriyle konumlarını değiştirmemeleri gerekir. En yüksek verimlilik için, sayı tabanı, $n$ veri öğelerinin sayısına yakın olacak şekilde seçilmelidir . Ek olarak, sayı tabanı olarak $n'ye$ yakın iki gücün kullanılması, yalnızca hızlı ikili kaydırma ve maskeleme işlemleri kullanılarak her geçiş için anahtarların hızlı bir şekilde hesaplanmasına olanak tanır. Bu seçeneklerle ve temel algoritma olarak güvercin deliği sıralama veya sayma sıralama ile, sayı tabanı sıralama algoritması, $O$ $($ $n$ $log$ $n$ $K$ $)$ zamanında $0$ ila $K$ $- 1$ aralığında anahtarlara sahip $n$ veri öğesini sıralayabilir .

teorik algoritmalar

Teorik analizleri, sıralanacak öğelerin sayısını, anahtar aralığını ve makine sözcük boyutunu tanımlayan parametrelerin yeterince büyük kombinasyonları için karşılaştırmalı sıralama, güvercin deliği sıralama veya sayı tabanı sıralamadan daha iyi davrandıklarını gösteren birçok tamsayı sıralama algoritması geliştirilmiştir. Hangi algoritmanın en iyi performansa sahip olduğu bu parametrelerin değerlerine bağlıdır. Bununla birlikte, teorik avantajlarına rağmen, bu algoritmalar, pratik sıralama problemlerinde ortaya çıkan bu parametrelerin tipik aralıkları için bir gelişme değildir.

Küçük tuşlar için algoritmalar

Bir Van Emde Boas ağacı , $O$ zamanında $($ $n$ $log log$ $K$ $)$ her biri $0$ ile $K$ $- 1$ aralığında olan bir dizi $n$ anahtarı sıralamak için bir öncelik sırası olarak kullanılabilir . Bu, $K$ yeterince büyük olduğunda radix sıralamaya göre teorik bir gelişmedir . Bununla birlikte, bir Van Emde Boas ağacını kullanmak için, ya doğrudan adreslenebilir bir $K$ kelime hafızasına ihtiyaç vardır ya da bir hash tablosu kullanarak , uzayı doğrusala indirgemek ama algoritmayı rastgele hale getirmek için simüle etmek gerekir . (Karma tablo şeklinde rasgele dağıtım için ihtiyaç dahil olmak üzere), benzer bir performans ile diğer bir öncelik sırası olan Y-hızlı tray arasında Willard (1983) .

Kirkpatrick & Reisch (1984) tarafından benzer bir tada ve daha iyi teorik performansa sahip daha sofistike bir teknik geliştirilmiştir . Her bir sayı tabanı sıralama geçişinin, doğrusal zamanda maksimum anahtar boyutunu $n$ faktörü kadar azaltan bir menzil azaltma tekniği olarak yorumlanabileceğini gözlemlediler ; bunun yerine, teknikleri, anahtar boyutunu, yine doğrusal zamanda önceki değerinin kareköküne (bir anahtarı temsil etmek için gereken bit sayısını yarıya indirerek) azaltır. Taban sıralamasında olduğu gibi, tuşları yaklaşık olarak $\sqrt$ $K$ olan bir $b$ tabanı için iki basamaklı taban- $b$ sayıları olarak yorumlarlar . Daha sonra, büyük ancak başlatılmamış doğrudan adresli bir bellek veya bir karma tablo kullanarak doğrusal zamanda, yüksek rakamlarına göre sıralanacak öğeleri kovalar halinde gruplandırırlar. Her kovanın bir temsilcisi vardır, kovadaki en büyük anahtara sahip öğe; daha sonra temsilciler için yüksek rakamları ve temsilci olmayanlar için düşük rakamları anahtar olarak kullanarak öğelerin listesini sıralarlar. Bu listedeki öğeleri tekrar kovalar halinde gruplayarak, her bir kova sıralı düzene yerleştirilebilir ve temsilciler sıralanmış listeden çıkarılarak kovalar sıralı düzende birleştirilebilir. Böylece, lineer zamanda, sıralama problemi, önceki büyüklüklerinin karekökü olan anahtarların çok daha küçük olduğu başka bir özyinelemeli sıralama problemine indirgenir. Anahtarlar kova sıralama için yeterince küçük olana kadar bu aralık azaltmayı tekrarlamak, çalışma süresi $O($ $n$ $log log$ $n$ $K$ $)$ olan bir algoritmaya yol açar .

Bir karışık randomize algoritma Han ve THORUP (2002) içinde bir kelime RAM hesaplama modeli bu zaman sınırları için, daha da uzağa azaltılabilir sağlar $O (n, \sqrt log K)$ .

Büyük kelimeler için algoritmalar

Bir tamsayı sıralama algoritmasının, $log max($ $n$ $,$ $K$ $)$ değerinden önemli ölçüde daha büyük bir kelime boyutu $w$ gerektiriyorsa, muhafazakar olmadığı söylenir . Uç bir örnek olarak, eğer $w$ $\geq$ $K$ ve tüm anahtarlar farklıysa , o zaman anahtar seti, onu bir bitvektör olarak temsil ederek doğrusal zamanda sıralanabilir , $i$ giriş anahtarlarından biri olduğunda $i$ konumunda 1 bit ile , ve ardından en önemsiz biti tekrar tekrar çıkarma.

Ve konservatif olmayan dolu sıralama algoritması Albers ve Hagerup (1997) göre, bir alt yordam kullanan Ken Besleyici sitesindeki bitonic sıralama ağı için birleştirme ikişer yeterince kısa bir makine sözcüğü içinde paketlenecek olan tuşların sekansları sıralanır. Paketlenmiş sıralama algoritmasının girdisi, kelime başına bir tane depolanan bir öğe dizisi, her birine paketlenmiş öğelerin sayısını iki katına çıkarmak için bu alt yordamı tekrar tekrar kullanarak, her biri sıralanmış sırada birden fazla öğeyi tutan bir sözcük dizisi olan paketlenmiş bir forma dönüştürülür. kelime. Dizi paketlenmiş formda olduğunda, Albers ve Hagerup sıralamak için bir birleştirme sıralama biçimi kullanır ; iki dizi tek bir uzun dizi oluşturmak için birleştirildiğinde, iki dizinin kalan en küçük öğelerinden oluşan paketlenmiş sözcükleri tekrar tekrar çıkarmak için aynı bitonik sıralama alt rutini kullanılabilir. Bu algoritma, tek bir kelimenin $Ω(log n log log n)$ anahtarlarını içermesi mümkün olduğunda, girdisini doğrusal zamanda sıralamak için paketlenmiş gösteriminden yeterince hız kazanır ; yani, bir $c$ $> 0$ sabiti için $log K log n log log n \leq cw olduğunda$ .

Birkaç öğe için algoritmalar

Güvercin deliği sıralama, sayma sıralama, taban sıralama ve Van Emde Boas ağaç sıralama, anahtar boyutu küçük olduğunda en iyi sonucu verir; yeterince büyük anahtarlar için karşılaştırmalı sıralama algoritmalarından daha yavaş olurlar. Bununla birlikte, anahtar boyutu veya sözcük boyutu, öğe sayısına göre çok büyük olduğunda (veya öğelerin sayısı küçük olduğunda eşdeğer olarak), doğasında bulunan paralellikten yararlanan farklı algoritmalar kullanarak yeniden hızlı bir şekilde sıralama yapmak mümkün olabilir. büyük kelimeler üzerinde aritmetik işlemler yapma becerisinde.

Bu yönde erken bir sonuç Ajtai, Fredman & Komlós (1984) tarafından hücre-sonda hesaplama modeli (bir algoritmanın karmaşıklığının yalnızca gerçekleştirdiği bellek erişimlerinin sayısı ile ölçüldüğü yapay bir model ) kullanılarak sağlandı . Çalışmalarında, üzerine inşa Fredman'in ve Willard (1994) , bir rasgele erişim makinesinde uygulanabilir olan iki veri yapıları, S-öbek ve atomik yığın, tarif. Q-yığın ikili bir bit paralel sürümüdür traya ve öncelikli kuyruk operasyonları ve halefi ve selefi sorguları hem kümeleri için sabit zamanda gerçekleştirilmesine olanak tanır $O ((log N) 1/4)$ öğeleri, $N \leq 2 w$ , veri yapısını uygulamak için gereken önceden hesaplanmış tabloların boyutudur. Atomik yığın, her ağaç düğümünün bir Q-yığın olarak temsil edildiği bir B-ağacıdır ; $(log N) O (1)$ öğe kümeleri için sabit zaman öncelikli kuyruk işlemlerine (ve dolayısıyla sıralamaya) izin verir .

Andersson ve ark. (1998) , herhangi bir sabit $ε > 0$ için bir seferde en fazla $2 O ((log w) 1/2 - ε)$ öğeden oluşan kümelerin doğrusal zaman sıralamasına izin veren, imza sıralama adı verilen rastgele bir algoritma sağlar . Kirkpatrick ve Reisch'in algoritmasında olduğu gibi , dikkatli bir $b$ seçimi için anahtarların $b$ tabanında sayılar olarak temsilini kullanarak menzil azaltma gerçekleştirirler . Menzil azaltma algoritmaları, her basamağı , farklı basamak değerleri farklı imzalara sahip olacak şekilde $O$ $(log$ $n$ $)$ bitleriyle karma bir değer olan bir imza ile değiştirir. Eğer $n$ yeterince küçükse, bu değiştirme işlemi tarafından oluşturulan sayılar orijinal anahtarlardan önemli ölçüde daha küçük olacak ve Albers & Hagerup'un (1997) konservatif olmayan paketlenmiş sıralama algoritmasının değiştirilen sayıları doğrusal zamanda sıralamaya izin verecektir . Değiştirilen sayıların sıralanmış listesinden, doğrusal zamanda anahtarların sıkıştırılmış bir denemesini oluşturmak mümkündür ve üçlüdeki her bir düğümün çocukları, yalnızca $b$ boyutundaki anahtarlar kullanılarak özyinelemeli olarak sıralanabilir , ardından bir ağaç geçişi sonucu üretir. öğelerin sıralı düzeni.

Trans-ikiye dayalı algoritmalar

Fredman ve Willard (1993) , tamsayı sıralama algoritmaları için, tamsayı anahtarlarının aralığı hakkında hiçbir şeyin varsayılmadığı ve algoritmanın performansının yalnızca veri değerlerinin bir fonksiyonu ile sınırlandırılması gereken transdichotomous analiz modelini tanıttı . Alternatif olarak, bu modelde, bir algoritma için $n$ öğe kümesi üzerindeki çalışma süresinin, olası herhangi bir $K$ ve $w$ değerleri kombinasyonu için en kötü durum çalışma süresi olduğu varsayılır . Bu türdeki ilk algoritma, Fredman ve Willard'ın $O($ $n$ $log$ $n$ $/ log log$ $n$ $)$ zamanında çalışan füzyon ağacı sıralama algoritmasıydı ; bu, herhangi bir $K$ ve $w$ seçimi için karşılaştırmalı sıralamaya göre bir gelişmedir . Algoritmalarının rastgele sayılar ve tamsayı bölme işlemlerini içeren alternatif bir versiyonu, bunu $O($ $n$ $\sqrt$ $log$ $n$ $) olarak geliştirir$ .

Çalışmalarından bu yana daha da iyi algoritmalar geliştirildi. Örneğin, anahtarlar Albers-Hagerup paketlenmiş sıralama algoritmasını uygulamak için yeterince küçük olana kadar Kirkpatrick-Reisch menzil azaltma tekniğini tekrar tekrar uygulayarak, $O$ zamanında sıralama yapmak mümkündür $($ $n$ $log log$ $n$ $)$ ; bununla birlikte, bu algoritmanın menzil azaltma kısmı, ya büyük bir bellek ( $\sqrt K ile$ orantılı ) ya da hash tabloları biçiminde rasgeleleştirme gerektirir.

Han ve Thorup (2002) , $O(n \sqrt log log n)$ rasgele zamanda nasıl sıralanacağını gösterdi . Teknikleri, verileri, imza sıralamanın her birini verimli bir şekilde sıralayabileceği kadar küçük birçok küçük alt listeye bölmek için imza sıralama ile ilgili fikirleri kullanmayı içerir. Tamsayıları $O (n log log n)$ ve lineer uzayda deterministik olarak sıralamak için benzer fikirleri kullanmak da mümkündür . Yalnızca basit aritmetik işlemleri kullanarak (çarpma veya tablo araması yok $)$ , herhangi bir sabit $ε > 0$ için $O (n log log n)$ rastgele beklenen zamanında veya $O (n (log log n) 1 + ε)$ zamanında deterministik olarak sıralama yapmak mümkündür. .

Referanslar

Dipnotlar

İkincil kaynaklar

Chowdhury, Rezaul A. (2008), "Öncelik sıraları ve sıralama arasındaki denklik" , Kao, Ming-Yang (ed.), Encyclopedia of Algorithms , Springer, s. 278–281, ISBN 9780387307701.
Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. ; Stein, Clifford (2001), Algoritmalara Giriş (2. baskı), MIT Press ve McGraw-Hill , ISBN 0-262-03293-7.
Goodrich, Michael T. ; Tamassia, Roberto (2002), "4.5 Bucket-Sort ve Radix-Sort", Algoritma Tasarımı: Temeller, Analiz ve İnternet Örnekleri , John Wiley & Sons, s. 241–243.

Birincil kaynaklar

Aggarwal, Alok; Vitter, Jeffrey S. (Eylül 1988), "Sıralama ve ilgili problemlerin giriş/çıkış karmaşıklığı", Communications of the ACM , 31 (9): 1116–1127, doi : 10.1145/48529.48535
Ajtai, M. ; Fredman, M. ; Komlós, J. (1984), "Öncelik kuyrukları için karma fonksiyonlar", Bilgi ve Kontrol , 63 (3): 217–225, doi : 10.1016/S0019-9958(84)80015-7 , MR 0837087.
Albers, Susanne ; Hagerup, Torben (1997), "Eşzamanlı yazma olmadan iyileştirilmiş paralel tamsayı sıralama", Information and Computation , 136 (1): 25–51, CiteSeerX 10.1.1.53.498 , doi : 10.1006/inco.1997.2632 , MR 1457693.
Anderson, Arne; Hagerup, Torben; Nilsson, Stefan; Raman, Rajeev (1998), "Doğrusal zamanda sıralama?", Journal of Computer and System Sciences , 57 (1): 74–93, doi : 10.1006/jcss.1998.1580 , MR 1649809.
Anderson, Arne; Nilsson, Stefan (1998), "Implementing radixsort", ACM Journal of Experimental Algorithmics , 3 : 7–es, CiteSeerX 10.1.1.54.4536 , doi : 10.1145/297096.297136 , MR 1717389.
Anderson, Arne; Miltersen, Peter Bro; Thorup, Mikkel (1999), "Füzyon ağaçları yalnızca $AC 0$ komutlarıyla uygulanabilir ", Theoretical Computer Science , 215 (1–2): 337–344, CiteSeerX 10.1.1.32.9401 , doi : 10.1016/S0304-3975( 98)00172-8 , MR 1678804.
Bhatt, PCP; Diks, K.; Hagerup, T.; Prasad, VC; Radzik, T.; Saxena, S. (1991), "Geliştirilmiş deterministik paralel tamsayı sıralama", Information and Computation , 94 (1): 29–47, doi : 10.1016/0890-5401(91)90031-V , MR 1123154.
Cole, R.; Vishkin, U. (1986), "Optimum paralel liste sıralamasına uygulamalarla deterministik yazı tura atma", Information and Control , 70 (1): 32–53, doi : 10.1016/S0019-9958(86)80023-7.
Comrie, LJ (1929-1930), "Hollerith ve Powers tablolama makineleri", Çev. Ofis Mak. Kullanıcılar Doç., LTD. : 25–37. Alıntılanma (2007) THORUP için erken kaynak olarak radix tür .
Farhadi, Alireza; Hajiaghayi, Mohammad Taghi ; Larsen, Kasper Yeşil; Shi, Elaine (Eylül 2020), "Ağ kodlaması yoluyla harici bellek tamsayı sıralaması için alt sınırlar", Communications of the ACM , 63 (10): 97–105, arXiv : 1811.01313 , doi : 10.1145/3416268.
Fredman, Michael L. ; Willard, Dan E. (1993), "Füzyon ağaçlarıyla bağlantılı bilgi kuramını aşma ", Journal of Computer and System Sciences , 47 (3): 424–436, doi : 10.1016/0022-0000(93)90040-4 , MR 1248864.
Fredman, Michael L. ; Willard, Dan E. (1994), "Minimum yayılan ağaçlar ve en kısa yollar için trans-ikilemli algoritmalar", Journal of Computer and System Sciences , 48 (3): 533–551, doi : 10.1016/S0022-0000(05)80064 -9 , MR 1279413.
Hagerup, Torben (1987), "Optimal paralel kova sıralamaya doğru", Bilgi ve Hesaplama , 75 (1): 39–51 , doi : 10.1016/0890-5401(87)90062-9 , MR 0910976.
Han, Yijie (2004), " $O (n log log n)$ zaman ve doğrusal uzayda deterministik sıralama ", Journal of Algorithms , 50 (1): 96–105, doi : 10.1016/j.jalgor.2003.09.001 , MR 2028585.
Han, Yijie; Thorup, M. (2002), " $O(n \sqrt log log n)$ beklenen zaman ve doğrusal uzayda tamsayı sıralama ", 43. Yıllık Bilgisayar Bilimlerinin Temelleri Sempozyumu Bildiriler Kitabı (FOCS 2002) , IEEE Computer Society, s. 135 –144, doi : 10.1109/SFCS.2002.1181890.
Kirkpatrick, David ; Reisch, Stefan (1984), "Rastgele erişimli makinelerde tam sayıları sıralamak için üst sınırlar", Theoretical Computer Science , 28 (3): 263–276, doi : 10.1016/0304-3975(83)90023-3 , MR 0742289.
McIlroy, Peter M.; Bostic, Keith; McIlroy, M. Douglas (1993), "Mühendislik Radix Sıralaması" (PDF) , Bilgi İşlem Sistemleri , 6 (1): 5-27.
Pedersen, Morten Nicolaj (1999), Dahili tamsayı sıralama için kelime RAM algoritmalarının pratik önemi üzerine bir çalışma , Yüksek Lisans tezi, Bilgisayar Bilimleri Bölümü, Kopenhag Üniversitesi, Danimarka, orijinalinden arşivlendi 2012-03-16 , alındı 2011 -04-21.
Rahman, Naila; Raman, Rajeev (1998), "Bazı sıralama algoritmalarında kelime düzeyinde paralellik üzerine deneysel bir çalışma", Algoritma Mühendisliği, 2. Uluslararası Çalıştay, WAE '92, Saarbrücken, Almanya, 20-22 Ağustos 1998, Bildiriler (PDF) , Maks. Planck Bilgisayar Bilimleri Enstitüsü , s. 193–203.
Reif, John H. (1985), "Tamsayı sıralama için optimal bir paralel algoritma", Bilgisayar Biliminin Temelleri üzerine 26. Yıllık Sempozyumu Bildiriler Kitabı (FOCS 1985) , IEEE Computer Society, s. 496–504, doi : 10.1109/SFCS .1985.9.
Thorup, Mikkel (2002), " $O (n log log n)$ zaman ve doğrusal uzayda toplama, kaydırma ve bit düzeyinde Boole işlemleri kullanarak rastgele sıralama ", Journal of Algorithms , 42 (2): 205–230, CiteSeerX 10.1 .1.55.4443 , doi : 10.1006/jagm.2002.1211 , MR 1895974.
Thorup, Mikkel (2003), " Füzyon ağaçlarının ve atomik yığınların $AC 0$ uygulamaları hakkında", Ayrık Algoritmalar Üzerine Ondördüncü Yıllık ACM-SIAM Sempozyumu Bildirileri (Baltimore, MD, 2003) , New York: ACM, s. 699-707 , MR 1974982.
Thorup, Mikkel (2007), "Öncelik sıraları ve sıralama arasındaki denklik", Journal of the ACM , 54 (6): Art. 28, doi : 10.1145/1314690.1314692 , MR 2374029.
Willard, Dan E. (1983), "Log-logaritmik en kötü durum aralığı sorguları uzayda mümkündür $Θ(N)$ ", Information Processing Letters , 17 (2): 81–84, doi : 10.1016/0020-0190(83 )90075-3 , MR 0731126.

Languages

In other projects