Sortare Radix vs. Sortare prin numărare vs. Sortare în găleți. Care este diferența? (Programare, Algoritm, Sortare, Radix Sort, Bucket Sort, Counting Sort)

bună_seară a intrebat.

Citesc definițiile de radix, counting și bucket sort și se pare că toate sunt doar codul de mai jos:

public static void sort(int[] a, int maxVal){
    int [] bucket=new int[maxVal+1];

    for (int i=0; i<bucket.length; i++){
        bucket[i]=0;
    }

    for (int i=0; i<a.length; i++){
        bucket[a[i]]++;
    }

    int outPos=0;
    for (int i=0; i<bucket.length; i++){
        for (int j=0; j<bucket[i]; j++){
            a[outPos++]=i;
        }
    }
}

Știu că nu pot avea dreptate, deci ce îmi scapă? Arată codul dacă crezi că te poate ajuta să explici în Java sau C.

7 răspunsuri
Konstantin Vladimirov

Să începem cu o rescriere a codului dvs. în C, deoarece C mai familiar pentru mine pentru a explica. Deci, să reamintim codul tău cu câteva comentarii:

int
counting_sort(int a[], int a_len, int maxVal)
{
  int i, j, outPos = 0;
  int bucket_len = maxVal+1;
  int bucket[bucket_len]; /* simple bucket structure */

  memset(bucket, 0, sizeof(int) * bucket_len);

  /* one loop bucket processing */
  for (i = 0; i < a_len; i++)
    {
      bucket[a[i]]++; /* simple work with buckets */
    }

  for (i=0; i < bucket_len; i++)
    {
      for (j = 0; j < bucket[i]; j++)
        {
          a[outPos++] = i;
        }
    }

  return 0;
}

Acum hai să-i oferim acestui tip niște date realiste:

[126, 348, 343, 432, 316, 171, 556, 223, 670, 201]

La ieșire avem

[126, 171, 201, 223, 316, 343, 348, 432, 556, 670]

Se pare că totul este în regulă? Nu încă. Să ne uităm la maxVal. Este 670 (!) Pentru a sorta un array de 10 elemente, am folosit aici un array de 670 de elemente, în principal zerouri. Îngrozitor. Pentru a rezolva această problemă de sortare prin numărare, avem două modalități posibile de generalizare:

1) Prima modalitate — să facem sortarea în funcție de cifre. Aceasta se numește sortare radix. Să arătăm un cod, încercând să îl facem cât mai apropiat de codul de sortare prin numărare. Priviți din nou comentariile:

int
radix_sort(int a[], int a_len, int ndigits)
{
  int i;
  int b[a_len];
  int expn = 1;

  /* additional loop for digits */
  for (i = 0; i != ndigits; ++i)
    {
      int j;
      int bucket[10] = {0}; /* still simple buckets */

      /* bucket processing becomes tricky */
      for (j = 0; j != a_len; ++j)
        bucket[ a[j] / expn % 10 ]++;

      for (j = 1; j != 10; ++j)
        bucket[j] += bucket[j - 1];

      for (j = a_len - 1; j >= 0; --j)
        b[--bucket[a[j] / expn % 10]] = a[j];

      for (j = 0; j != a_len; ++j)
        a[j] = b[j];

      expn *= 10;
    }
}

Schimbăm multiplicatorul din apropierea lui N pentru memorie. Profitul? Poate. Dar, în unele cazuri, multiplicatorul de lângă N este foarte important. Programul, lucrul într-o zi și lucrul într-o săptămână sunt foarte diferite din punctul de vedere al utilizatorilor, chiar dacă ambele lucrează 1*O(N) și, respectiv, 7*O(N). Și astfel ajungem la o a doua generalizare:

2) A doua modalitate – de a face gălețile mai sofisticate. Aceasta se numește sortare a găleților.

Să începem din nou cu un cod. Prefer mai mult cod înainte de argumente filozofice. Priviți totuși comentariile, ele sunt esențiale.

int
bucket_sort(int a[], int a_len, int maxVal)
{
  int i, aidx;

  typedef struct tag_list {
    int elem;
    struct tag_list *next;
  } list_t, *list_p;

  list_p bucket[10] = {0}; /* sophisticated buckets */

  /* one loop simple processing with one more inner loop 
    to get sorted buckets (insert-sort on lists, Cormen-style) */
  for (i = 0; i != a_len; ++i)
    {
      int bnum = (10 * a[i]) / maxVal;
      list_p bptr = bucket[bnum];
      list_p belem = malloc(sizeof(list_t));
      belem->elem = a[i];
      if (bptr == 0)
        {
          bucket[bnum] = belem;
          belem->next = 0;
          continue;
        }
      else if (a[i] <= bptr->elem)
        {
          belem->next = bptr;
          bucket[bnum] = belem;
          continue;
        }
      else
        {
          while (bptr != 0)
            {
              if ((bptr->elem <= a[i]) && ((bptr->next == 0) || (bptr->next->elem > a[i])))
                {
                  belem->next = bptr->next;
                  bptr->next = belem;
                  break;
                }
               bptr = bptr->next;
            }
         }
    }

  /* one loop (looks as two) to get all back */
  aidx = 0;

  for (i = 0; i != 10; ++i)
    {
      list_p bptr = bucket[i];
      while (bptr)
        {
          list_p optr = bptr;
          a[aidx] = bptr->elem;
          aidx += 1;
          bptr = bptr->next;
          free(optr);
        }
    }

  return 0;
}

Deci, ce avem aici? Schimbăm o structură sofisticată de găleți și o cerință pentru memorie alocată dinamic, dar câștigăm memorie statică și un multiplicator apropiat de N în medie.

Acum să ne amintim ce am văzut în cod:

  1. Sortare prin numărare – găleți simple, procesare simplă, cheltuieli de memorie.
  2. Sortare Radix — găleți simple, procesare sofisticată, costuri de viteză (și încă necesită memorie statică suplimentară).
  3. Bucket sort — găleți sofisticate, procesare simplă, necesită memorie dinamică, bună în medie.

Astfel, sortarea Radix și sortarea bucket sunt două generalizări utile ale sortării prin numărare. Acestea au multe în comun cu sortarea prin numărare și între ele, dar în fiecare caz pierdem ceva și câștigăm ceva. Ingineria software este despre un echilibru între aceste oportunități.

Peter Lawrey

Radix sort vs Counting sort vs Bucket sort. Care este diferența?

Bucket sort plasează cheile sau elementele care urmează să fie sortate în găleți. Modul în care acestea sunt plasate în găleți este arbitrar și poate fi vorba de porțiuni dintr-o cheie compozită și de orice distribuție doriți. S-ar putea ca gălețile individuale să trebuiască să fie sortate în continuare.

Sortarea în memorie este mai rapidă decât sortarea pe disc. Cu toate acestea, dacă aveți mai multe date decât încap în memorie, aveți nevoie de o altă opțiune. Ceea ce se poate face este o sortare de tip „bucket”, în cazul în care bucket-urile sunt suficient de mici pentru a încăpea în memorie, adică există un număr mare de intrări în fiecare bucket. Pe acestea le puteți sorta rapid și individual.

Sortarea Radix este un tip specific de sortare în găleți. Acesta începe cu primii n biți sau n cifre și poate sorta aceste găleți folosind o sortare radix etc., până când fiecare intrare este sortată.

Sortarea prin numărare este ca și cum ați folosi sortarea radix, cu excepția faptului că folosiți valoarea întreagă. În loc să înregistreze fiecare obiect, are o găleată pentru fiecare obiect și numără doar numărul de apariții. Acest lucru funcționează bine atunci când aveți un număr limitat de chei posibile și aveți multe duplicate.

kasavbere

Conform Geekviewpoint:

Radix: http://www.geekviewpoint.com/java/sorting/radixsort

Radix sort, ca și counting sort și bucket sort, este un algoritm bazat pe numere întregi (adică se presupune că valorile din matricea de intrare sunt numere întregi). Prin urmare, sortarea radix se numără printre cei mai rapizi algoritmi de sortare existenți, în teorie. Distincția specială pentru radix sort este că acesta creează o găleată pentru fiecare cifră (adică cifră); ca atare, similar cu bucket sort, fiecare găleată în radix sort trebuie să fie o listă crescătoare care poate admite chei diferite.

Bucket: http://www.geekviewpoint.com/java/sorting/bucketsort

Bucket sort este de fapt foarte bun, având în vedere că numărarea este, în mod rezonabil, limita sa superioară. Iar sortarea prin numărare este foarte rapidă. Distincția specifică pentru sortarea bucket este că utilizează o funcție hash pentru a împărți cheile din matricea de intrare, astfel încât mai multe chei pot fi asociate cu același bucket. Prin urmare, fiecare găleată trebuie să fie efectiv o listă crescătoare; similar cu sortarea radix.

Numărătoare: http://www.geekviewpoint.com/java/sorting/countingsort

Distincția specifică pentru sortarea prin numărare este că aceasta creează un bucket pentru fiecare valoare și păstrează un contor în fiecare bucket. Apoi, de fiecare dată când se întâlnește o valoare în colecția de intrare, contorul corespunzător este incrementat. Deoarece sortarea prin numărare creează o găleată pentru fiecare valoare, o restricție impusă este aceea ca valoarea maximă din colecția de intrare să fie cunoscută dinainte.

Pe site-ul lor se explică mai detaliat acest lucru.

Editați:

  • Dacă folosiți radix sort și numerele sunt zecimale, atunci aveți nevoie de 10 găleți, una pentru fiecare cifră de la 0 la 9.

  • Dacă folosiți sortare prin numărare, atunci aveți nevoie de o găleată pentru fiecare valoare unică din intrare (de fapt, aveți nevoie de o găleată pentru fiecare valoare între 0 și max).

  • Dacă folosiți bucketsort, nu știți câte găleți veți folosi. Orice funcție hash pe care o utilizați va determina numărul de găleți.

Comentarii

  • radix sort este similar cu counting sort și pentru că în ambele trebuie să știți numărul de găleți înainte de mâini. –  > Por Konsol Labapen.
  • Radix sort cu un radix de 10 este un nonsens. Întotdeauna ar trebui să se folosească o putere de doi ca radix, cum ar fi 16 sau 256. –  > Por Gunther Piez.
  • @hirschhornsalz Cred că, deoarece este un tutorial de sortare, autorul păstrează simplitatea folosind zecimalul în loc de binar. –  > Por kasavbere.
zch

Codul tău este o variantă simplă de counting sort fără date, doar chei.

Radix sort este sortarea bazată pe această metodă. Problema cu counting sort este cerința de memorie: int [] bucket=new int[maxVal+1];. Radix sort rezolvă această problemă. Ideea este de a folosi counting sort de mai multe ori, mai întâi pentru cifrele inferioare, apoi pentru cele superioare. De exemplu, pentru sortarea numerelor întregi pe 32 de biți, puteți utiliza:

sort(a, 65535) using lower half as key
sort(a, 65535) using higher half as key

Funcționează, deoarece sortarea prin numărare este stabilă – păstrează ordinea datelor cu chei egale. Este ca o sortare în foaia de calcul: sort by B; sort by A vă oferă elemente sortate după A și după B, atunci când As sunt egale.

Sortarea pe găleți este o generalizare a sortării prin numărare. O puteți utiliza pentru a sorta numere reale dintr-o anumită distribuție de probabilitate previzibilă (de exemplu, uniformă (0,1)). Ideea este de a utiliza sortarea prin numărare (folosind floor(x*N_BUCKETS) ca cheie) și apoi să sortați doar fiecare găleată în mod independent.

Comentarii

  • Sortarea prin numărare utilizează atât datele, cât și cheile? –  > Por Denys S..
  • @den-javamaniac – poate fi utilizat cu date. Trebuie atunci să rețineți elementele din fiecare găleată. Poate fi implementat cu o matrice suplimentară. –  > Por zch.
Vrashabh Irde

În primul rând, haideți să analizăm diferența dintre Radix Sort și Bucket Sort, pentru că, în general, este un lucru care creează confuzie, deoarece ideea pare aceeași. Apoi ne uităm la Counting Sort care este ca o versiune primară a acestor două și ce probleme cu Counting Sort determină utilizarea celorlalte două

Trecerea inițială atât a sortării Radix, cât și a sortării Bucket este aceeași: elementele sunt plasate în „Buckets”, adică 0-10, 11-20, … și așa mai departe, în funcție de numărul de cifre din cel mai mare număr, adică radix. Cu toate acestea, în următoarea trecere, sortarea în găleți ordonează aceste „găleți” și le adună într-o singură matrice. Cu toate acestea, metoda de sortare radix adaugă gălețile fără o altă sortare și le „rearanjează” în funcție de a doua cifră (locul zece) a numerelor. Prin urmare, sortarea în găleți este mai eficientă pentru array-uri „dense”, în timp ce sortarea radix se poate descurca bine cu array-uri rare.Gândiți-vă la sortarea în găleți astfel

Să presupunem că aveți o listă de n înregistrări, fiecare cu o cheie care este un număr de la 1 la k (generalizăm puțin problema, astfel încât k nu este neapărat egal cu n).

Putem rezolva această problemă făcând o matrice de liste legate. Mutăm fiecare înregistrare de intrare în listă în poziția corespunzătoare din matrice, apoi concatenăm toate listele împreună în ordine.

 bucket sort(L)
    {
    list Y[k+1]
    for (i = 0; i <= k; i++) Y[i] = empty
    while L nonempty
    {
        let X = first record in L
        move X to Y[key(X)]
    }
    for (i = 0; i <= k; i++)
    concatenate Y[i] onto end of L
    }

Ce trebuie făcut atunci când k este mare? Gândiți-vă la reprezentarea zecimală a unui număr x = a + 10 b + 100 c + 1000 d + …unde a,b,c etc. sunt toate în intervalul 0…9. Aceste cifre sunt suficient de mici pentru a face o sortare în găleată.

   radix sort(L):
    {
    bucket sort by a
    bucket sort by b
    bucket sort by c
    ...
    }

sau mai simplu

radix sort(L):
{
while (some key is nonzero)
{
    bucket sort(keys mod 10)
    keys = keys / 10
}
}

De ce sortăm mai întâi cea mai puțin importantă cifră? De altfel, de ce facem mai mult de o sortare în găleată, din moment ce ultima este cea care pune totul la locul lui?Răspuns: Dacă încercăm să sortăm lucrurile manual, avem tendința de a face ceva diferit: mai întâi facem o sortare în găleți, apoi sortăm recursiv valorile care au o primă cifră comună. Acest lucru funcționează, dar este mai puțin eficient, deoarece împarte problema în mai multe subprobleme. În schimb, sortarea radix nu împarte niciodată lista; doar aplică sortarea în găleți de mai multe ori aceleiași liste.În cazul sortării radix, ultima trecere a sortării în găleți este cea care are cel mai mare efect asupra ordinii generale. Așadar, dorim ca aceasta să fie cea care utilizează cele mai importante cifre. Trecerile anterioare de sortare a găleților sunt folosite doar pentru a avea grijă de cazul în care două elemente au aceeași cheie (mod 10) la ultima trecere.

Acum că am eliminat această problemă, tot ceea ce face sortarea prin numărare este să păstreze o matrice auxiliară C cu k elemente, toate inițializate la 0.

Facem o trecere prin matricea de intrare A și pentru fiecare element i din A pe care îl vedem, creștem C[i] cu 1. După ce parcurgem cele n elemente din A și actualizăm C, valoarea de la indicele j din C corespunde numărului de apariții ale lui j în A. Acest pas durează O(n) timp pentru a parcurge A. Odată ce avem C, putem construi versiunea sortată a lui A prin parcurgerea lui C și inserarea fiecărui element j de un număr total de ori C[j] într-o nouă listă (sau în A însuși). Iterarea prin C durează O(k) timp.Rezultatul final este un A sortat și, în total, a durat O(n + k) timp pentru a face acest lucru.

Dezavantajul sortării prin numărare este că s-ar putea să nu fie prea practic dacă intervalul de elemente este prea mare. De exemplu, dacă intervalul celor n elemente pe care trebuie să le sortăm ar fi de la 1 la n3 , atunci simpla creare a tabloului auxiliar C va dura O(n^3), iar sortarea prin numărare va fi asimetric mai puțin bună decât sortarea prin inserție. Acest lucru necesită, de asemenea, un spațiu O(n^3), care este semnificativ mai mare decât oricare dintre spațiile utilizate de oricare alt algoritm de sortare pe care l-am învățat până acum. Sortarea Radix ajută la rezolvarea acestei probleme prin sortarea elementelor cifră cu cifră

Notă: Surse pentru răspuns și lectură suplimentară:

http://htmltolatex.sourceforge.net/samples/sample4.html

Primul răspuns la: Care este diferența dintre bucket sort și radix sort?

kutschkem

Radix sort folosește o formă de counting sort ca subrutină (ok, se poate folosi, dar cel mai adesea va fi counting sort).

Countingsort este o formă specială de bucket sort, după cum a răspuns kasavbere.

Iar Bucketsort împarte cheile în găleți și apoi sortează gălețile individual.

user586399

Pentru a sorta o matrice folosind count sort:

#define MAX_INPUT 1000

void sort(int arr[100], int n)
{
    static int hash[MAX_INPUT], i, j;

    memset(hash, 0, sizeof hash);

    for (i = 0; i < n; ++i) ++hash[arr[i]];

    j = 0;
    for (i = 0; i < MAX_INPUT; ++i)
        while (hash[i]--)
           arr[j++] = i;
}

Aceasta este doar O(MAX_INPUT), sortând astfel în timp liniar. Pentru bucket sort, este foarte diferit. Aici este o implementare

Comentarii

  • Aceasta nu răspunde la întrebare: Radix sort vs Counting sort vs Bucket sort. What's the difference? –  > Por amit.
  • Întrebarea doar a confundat sortarea în găleți cu sortarea prin numărare. Tocmai i-am arătat codul său – user586399
  • Timpul de execuție este de fapt O(MAX_INPUT + n) . –  > Por Ivaylo Toskov.
  • Omiterea lui n deoarece este relativ mică în comparație cu MAX_INPUT (ar trebui să fie) – user586399