Dağıtım dizisini Dağıtım-Sayma sıralama algoritmasında sağdan sola doğru işlemek neden daha iyidir?

Question

İşte algoritma

yazar

diyor bulunuyor "sağdan sola giriş dizisi işlemek için daha uygundur."

Diziyi 0'dan n-1'e okumaktan nasıl farklıdır?

Answer 1

Girdi dizisinin son adımda işlenme sırası önemli değil. Yazar yanlış.

Çıktı dizisindeki "bölmeler" ini sağdan sola doğru doldurmak daha uygun olur. Bunları soldan sağa doğru doldurmak, D'daki indeksleri azaltmak yerine artırmak da mümkündür, ancak bu, kümülatif frekansların biraz daha karmaşık hesaplandığı üçüncü adımı yapar.

Answer 2

Fark göremiyorum. Gerçekten, A öğelerinin hangi sırasına sahip olursa olsun, sonuç aynıdır. Yazar, belki de bazı özel uygulamaları ima etmiş olabilir. Örneğin. C++ for(size_t i = n; i--;), biri için daha kısa ve daha uygundur.

Answer 3

Soldan sağa, basit bir seçenek D [] bir öğeyi daha büyük yapmaktır. D'nin büyüklüğü [] = u + 2 - l. Son giriş dağıtım için kullanılmaz, ancak A [] == u vakalarını atlamak veya iki yerel değişken kullanarak bir kontrol kullanarak kaydedilir. nihai hedef D [0] = 0, D [1] = u içinde örneklerini, D [2] = u içinde örneklerini + # u örneklerinin + 1, ...

for j ← 0 to u+1-l do D[j] = 0      // reset counts 
    for i ← 0 to n-1 do D[A[i]+1-l] = D[A[i]+1-l]+1 // set counts 
    for j ← 2 to u-l do D[j] ← D[j-1] + D[j]   // convert to indicies 
    for i ← 0 to n-1 do        // distribute 
     j ← A[i] - l 
     S[D[j]] ← A[i] 
     D[j] ← D[j] + 1 
    return S 

iki Kullanılması olduğunu yerine yerel değişkenler:

for j ← 0 to u+l do D[j] = 0      // reset counts 
    for i ← 0 to n-1 do D[A[i]-l] = D[A[i]-l]+1  // set counts 
    k = 0            // k == sum 
    for j ← 0 to u-l do        // convert to indicies 
     i ← D[j] 
     D[j] ← k 
     k ← k + i 
    for i ← 0 to n-1 do        // distribute 
     j ← A[i] - l 
     S[D[j]] ← A[i] 
     D[j] ← D[j] + 1 
    return S 

yerine dağılımın, sadece bir sayım sıralama olabilir: "daha uygun" "daha iyi" arasında bir fark

for j ← 0 to u-l do C[j] = 0      // reset counts 
    for i ← 0 to n-1 do C[A[i]-l] = C[A[i]-l]+1  // set counts 
    i = 0            // generate sorted array 
    for j ← 0 to u-l do 
     while(C[j] != 0) do 
      S[i] ← j-l 
      i ← i+1 
      C[j] ← C[j]-1 
    return S