webentwicklung-frage-antwort-db.com.de

Radix sort vs Counting sort vs Bucket sort. Was ist der Unterschied?

Ich lese die Definitionen von radix, counting und bucket sorts und es scheint, dass sie alle nur den folgenden Code haben:

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;
        }
    }
}

Ich weiß, ich kann nicht richtig liegen, also was vermisse ich? Zeigen Sie den Code an, wenn Sie der Meinung sind, dass dies bei der Erklärung in Java oder C.

52
good_evening

Beginnen wir damit, Ihren Code in C umzuschreiben, weil mir C näher bekannt ist. Rufen wir also Ihren Code mit einigen Kommentaren auf:

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;
}

Lassen Sie uns diesem Typen nun einige realistische Daten anbieten:

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

Am Ausgang haben wir

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

Es scheint, dass alles in Ordnung ist? Noch nicht. Schauen wir uns maxVal an. Es ist 670 (!) Um hier ein Array von 10 Elementen zu sortieren, haben wir ein Array von 670 Elementen verwendet, hauptsächlich Nullen. Furchtbar. Um dieses Problem der Sortenzählung zu lösen, haben wir zwei Möglichkeiten der Verallgemeinerung:

1) Erster Weg - Sortieren nach Ziffern. Dies nennt man Radix-Sort. Lassen Sie uns einen Code zeigen, der versucht, ihn so nah wie möglich an den Zählsortiercode heranzuführen. Nochmals Kommentare anschauen:

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;
    }
}

Wir tauschen den Multiplikator in der Nähe von N gegen Speicher. Profitieren? Könnte sein. In einigen Fällen ist jedoch ein Multiplikator in der Nähe von N sehr wichtig. Programm, Arbeitstag und Arbeitswoche unterscheiden sich stark von der Benutzeransicht, auch wenn beide Funktionen 1 * O (N) bzw. 7 * O (N) ausführen. Und so kommen wir zu einer zweiten Verallgemeinerung:

2) Zweiter Weg - um Eimer raffinierter zu machen. Dies wird als Eimersortierung bezeichnet.

Fangen wir noch einmal mit einigem Code an. Ich bevorzuge mehr Code als philosophische Argumente. Schauen Sie sich noch Kommentare an, sie sind unerlässlich.

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;
}

Also, was haben wir hier? Wir handeln mit einer ausgeklügelten Bucket-Struktur und der Forderung nach dynamisch zugewiesenem Speicher, gewinnen jedoch statischen Speicher und einen Multiplikator nahe N im Durchschnitt.

Erinnern wir uns jetzt daran, was wir im Code gesehen haben:

  1. Zählsortierung - einfache Eimer, einfache Verarbeitung, Speicheraufwand
  2. Radix-Sortierung - einfache Buckets, ausgefeilte Verarbeitung, Overhead-Geschwindigkeit (und immer noch zusätzlicher statischer Speicher erforderlich)
  3. Eimersortierung - Hochentwickelte Eimer, einfache Verarbeitung, erfordern dynamischen Speicher, durchschnittlich gut

Radix- und Bucket-Sortierungen sind somit zwei nützliche Verallgemeinerungen für das Zählen von Sortierungen. Sie haben viel gemeinsam mit Zählen und miteinander, aber in jedem Fall verlieren wir etwas und gewinnen etwas. Bei der Softwareentwicklung geht es um ein Gleichgewicht zwischen diesen Möglichkeiten.

61

Radix sort vs Counting sort vs Bucket sort. Was ist der Unterschied?

Bucket-Sortierung platziert die zu sortierenden Schlüssel oder Elemente in Buckets. Wie sie in Buckets platziert werden, ist willkürlich und kann Teil eines zusammengesetzten Schlüssels und einer beliebigen Verteilung sein. Die einzelnen Eimer müssen möglicherweise weiter sortiert werden.

Das Sortieren im Speicher ist schneller als das Sortieren auf der Festplatte. Wenn Sie jedoch mehr Daten haben, als in den Speicher passen, benötigen Sie eine andere Option. Was Sie tun können, ist eine Eimersorte, bei der die Eimer klein genug sind, um in den Speicher zu passen. es gibt eine große Anzahl von Einträgen in jedem Bucket. Diese können Sie schnell einzeln sortieren.

Radix-Sortierung ist eine bestimmte Art von Bucket-Sortierung. Es beginnt mit dem obersten n-Bit oder den obersten n-Ziffern und kann diese Buckets mit einer Radix-Sortierung usw. sortieren, bis jeder Eintrag sortiert ist.

Das Zählen von sort entspricht der Verwendung von radix sort, mit der Ausnahme, dass Sie den gesamten Wert verwenden. Anstatt jedes Objekt aufzuzeichnen, verfügt es über einen Bucket für jedes Objekt und zählt nur die Anzahl der Vorkommen. Dies funktioniert gut, wenn Sie eine begrenzte Anzahl möglicher Schlüssel und viele Duplikate haben.

14
Peter Lawrey

Laut Geekviewpoint:

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

Die Radix-Sortierung ist wie die Zählsortierung und die Bucket-Sortierung ein Algorithmus auf Ganzzahlbasis (d. H. Es wird angenommen, dass die Werte des Eingabearrays Ganzzahlen sind). Daher gehört die Radix-Sortierung theoretisch zu den schnellsten Sortieralgorithmen überhaupt. Der besondere Unterschied bei der Radix-Sortierung besteht darin, dass für jede Chiffre (d. H. Ziffer) ein Bucket erstellt wird. Daher muss ähnlich wie bei der Bucket-Sortierung jeder Bucket in der Radix-Sortierung eine erweiterbare Liste sein, die möglicherweise andere Schlüssel zulässt.

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

Bucket-Sortierung ist eigentlich sehr gut, wenn man bedenkt, dass das Zählen der Sortierung vernünftigerweise die Obergrenze darstellt. Und die Sortierung ist sehr schnell. Die besondere Unterscheidung für die Bucket-Sortierung besteht darin, dass eine Hash-Funktion zum Partitionieren der Schlüssel des Eingabearrays verwendet wird, sodass mehrere Schlüssel auf dasselbe Bucket gehasht werden können. Daher muss jeder Eimer effektiv eine erweiterbare Liste sein; ähnlich wie radix sort.

Zählung: http://www.geekviewpoint.com/Java/sorting/countingsort

Der besondere Unterschied beim Zählen von sort besteht darin, dass für jeden Wert ein Bucket erstellt wird und in jedem Bucket ein Zähler gespeichert wird. Jedes Mal, wenn ein Wert in der Eingabeauflistung gefunden wird, wird der entsprechende Zähler inkrementiert. Da beim Zählsortieren für jeden Wert ein Bucket erstellt wird, besteht eine auferlegte Einschränkung darin, dass der Maximalwert im Eingabearray im Voraus bekannt ist.

Sie erklären es ausführlicher auf ihrer Site.

Bearbeiten:

  • Wenn Sie die Radix-Sortierung verwenden und Ihre Zahlen dezimal sind, benötigen Sie 10 Buckets, einen für jede Ziffer von 0 bis 9.

  • Wenn Sie die Zählsortierung verwenden, benötigen Sie einen Bereich für jeden eindeutigen Wert in der Eingabe (tatsächlich benötigen Sie einen Bereich für jeden Wert zwischen 0 und max).

  • Wenn Sie Bucketsort verwenden, wissen Sie nicht, wie viele Buckets Sie verwenden werden. Welche Hash-Funktion Sie verwenden, bestimmt die Anzahl der Eimer.

7
kasavbere

Ihr Code ist eine einfache Variante des Zählens ohne Daten, nur Schlüssel.

Die Radix-Sortierung basiert auf dieser Methode. Das Problem beim Zählen der Sortierung ist der Speicherbedarf: int [] bucket=new int[maxVal+1];. Radix Sort löst dieses Problem. Die Idee ist, die Zählsortierung mehrmals zu verwenden, zuerst für niedrigere Stellen, dann für höhere. Zum Sortieren von 32-Bit-Ganzzahlen könnten Sie beispielsweise Folgendes verwenden:

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

Es funktioniert, weil die Zählsortierung stabil ist - die Reihenfolge der Daten bleibt bei gleichen Schlüsseln erhalten. Es ist wie beim Sortieren in einer Tabelle: sort by B; sort by A Gibt Ihnen Elemente, die nach A und nach B sortiert sind, wenn As gleich sind.

Die Bucket-Sortierung ist eine Verallgemeinerung der Zählsortierung. Sie können es verwenden, um reelle Zahlen anhand einer vorhersagbaren Wahrscheinlichkeitsverteilung zu sortieren (z. B. einheitlich (0,1)). Die Idee ist, Zählsortierung zu verwenden (mit floor(x*N_BUCKETS) als Schlüssel) und dann nur jeden Eimer unabhängig zu sortieren.

6
zch

Betrachten wir zunächst den Unterschied zwischen Radix Sort und Bucket Sort, da dies im Allgemeinen verwirrend ist, da die Idee gleich zu sein scheint. Dann schauen wir uns Counting Sort an, das wie eine primäre Version dieser beiden ist, und welche Probleme beim Zählen von Sortierungen dazu führen, dass die anderen beiden verwendet werden

Der anfängliche Durchlauf von Radix und Bucket ist der gleiche. Die Elemente werden in 'Buckets' abgelegt, dh 0-10, 11-20, ... usw., abhängig von der Anzahl der Ziffern in der größten Nr., Dh der radix. Im nächsten Durchgang werden diese "Buckets" jedoch in Bucket-Sortierreihenfolgen angeordnet und zu einem Array angehängt. Bei der Radix-Sortiermethode werden die Buckets jedoch ohne weitere Sortierung angehängt und anhand der zweiten Ziffer (Zehnerstelle) der Zahlen erneut sortiert. Aus diesem Grund ist die Bucket-Sortierung für "dichte" Arrays effizienter, während Radix Sort spärliche Arrays gut verarbeiten kann. Nun denken Sie an Eimersorte wie diese

Angenommen, Sie haben eine Liste von n Datensätzen mit einem Schlüssel, der eine Zahl von 1 bis k ist (wir verallgemeinern das Problem ein wenig, sodass k nicht unbedingt gleich n ist).

Wir können dieses Problem lösen, indem wir eine Reihe verknüpfter Listen erstellen. Wir verschieben jeden Eingabedatensatz in die Liste an die entsprechende Position des Arrays und verknüpfen dann alle Listen in der angegebenen Reihenfolge.

 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
    }

Was tun, wenn k groß ist? Denken Sie an die Dezimaldarstellung einer Zahl x = a + 10 b + 100 c + 1000 d + ... wobei a, b, c usw. alle im Bereich 0..9 liegen. Diese Ziffern sind leicht klein genug, um eine Bucket-Sortierung durchzuführen.

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

oder einfacher

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

Warum sortieren wir zuerst die unwichtigste Ziffer? Warum machen wir eigentlich mehr als eine Bucket-Sortierung, da die letzte diejenige ist, die alles in Ordnung bringt? Antwort: Wenn wir versuchen, Dinge von Hand zu sortieren, neigen wir dazu, etwas anderes zu tun: Zuerst eine Bucket-Sortierung und dann rekursiv die Werte zu sortieren, die eine gemeinsame erste Ziffer haben. Dies funktioniert, ist jedoch weniger effizient, da es das Problem in viele Teilprobleme aufteilt. Im Gegensatz dazu wird die Liste bei der Radix-Sortierung nie aufgeteilt. Es wird lediglich eine mehrmalige Bucket-Sortierung auf dieselbe Liste angewendet. Bei der Radix-Sortierung hat der letzte Durchgang der Bucket-Sortierung die größte Auswirkung auf die Gesamtreihenfolge. Wir wollen also, dass es derjenige ist, der die wichtigsten Ziffern verwendet. Die vorherigen Durchgänge zum Sortieren von Eimern werden nur verwendet, um den Fall zu behandeln, dass zwei Elemente im letzten Durchgang denselben Schlüssel (Mod 10) haben.

Nun, da wir das haben, ist alles, was Counting sort macht, dass es ein Hilfsarray C mit k Elementen behält, die alle auf 0 initialisiert sind.

Wir machen einen Durchgang durch das Eingabearray A, und für jedes Element i in A, das wir sehen, erhöhen wir C [i] um 1. Nachdem wir die n Elemente von A durchlaufen und C aktualisiert haben, entspricht der Wert am Index j von C bis wie oft j in A aufgetaucht ist. Dieser Schritt benötigt O(n) Zeit, um A zu durchlaufen. Sobald wir C haben, können wir die sortierte Version von A konstruieren, indem wir C durchlaufen und einfügen Jedes Element ist insgesamt C [j] -mal in einer neuen Liste (oder A selbst). Das Durchlaufen von C dauert O(k) time. Das Endergebnis ist ein sortiertes A und insgesamt ist es hat O (n + k) Zeit dafür gebraucht.

Der Nachteil des Zählens ist, dass es möglicherweise nicht zu praktisch ist, wenn der Bereich der Elemente zu groß ist. Wenn zum Beispiel der Bereich der n Elemente, die wir sortieren müssen, von 1 bis n 3 reicht, dauert die einfache Erstellung des Hilfsarrays C 0 (n ^ 3), und die Zählsortierung ist asymptotisch schlechter als die Einfügungssortierung. Dies erfordert auch O (n ^ 3) Platz, der bedeutend größer ist als der Platz, der von einem anderen Sortieralgorithmus verwendet wird, den wir bisher kennengelernt haben. Radix Sort hilft, dieses Problem zu lösen, indem die Elemente ziffernweise sortiert werden

Hinweis: Quellen zur Beantwortung und weiteren Lektüre:

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

Die erste Antwort auf: Was ist der Unterschied zwischen Bucket Sort und Radix Sort?

3
Slartibartfast

Radix-Sortierung verwendet eine Form der Zählsortierung als Unterroutine (ok, kann verwendet werden, aber am häufigsten wird die Sortierung gezählt).

Countingsort ist eine spezielle Form der Eimersorte, wie kasavbere antwortete.

Und Bucketsort unterteilt die Schlüssel in Eimer und sortiert die Eimer dann einzeln.

2
kutschkem

So sortieren Sie ein Array mit 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;
}

Dies ist nur O(MAX_INPUT), also in linearer Zeit sortiert. Bei der Eimersorte ist das ganz anders. Hier ist eine Implementierung

1
user586399