Bu algoritmanın time complexity'si : O(n+k)
Elimizde yukarıdaki gibi bir array var ve bu arraydeki sayıları küçükten büyüğe sıralamak istiyoruz.Bu array'deki en küçük sayı 0 en büyük sayı ise 5. Dolayısıyla 0'dan 5'e kadar olan tüm sayıların frekanslarını bulup yazalım: Bunun için bize 6 kutu gerekecek.
Frekansları bulmamız 1.aşamaıdr.
2.aşamada en baştan başlayarak her sayıya kendinden önce gelen sayı eklenir.
Resmin sol üst köşesinden itibaren okumaya başlayın.Orada da dendiği gibi array'in üzerinde sağdan sola doğru ilerliyoruz. Bu sırada sıralı sayılarımızı başlangıçta boş olan array'imize yerleştiriyoruz. Ayrıca resimdeki y array'ini de her adımda güncelliyoruz.
Kaynaklar :
http://www.cs.miami.edu/~burt/learning/Csc517.091/workbook/countingsort.html
Hiç yorum yok:
Yorum Gönder