Dieser auch als Schwerkraftsortierung bekannte Algorithmus wurde von natürlichen Phänomenen inspiriert und wurde unter Berücksichtigung von Objekten (oder Perlen) entwickelt, die unter dem Einfluss der Schwerkraft fallen.

Die Idee: Positive Zahlen werden durch eine Reihe von Perlen wie auf einem Abakus dargestellt.

BSV

Sortieren von {7, 2, 1, 4, 2} mit Bead Sort. Perlen fallen eine nach der anderen herunter, wenn darunter Platz ist.

  1. Wie im obigen Bild stellen die Perlen die folgenden Zahlen von oben nach unten dar: 7, 2, 1, 4, 2. Stellen Sie sich nun vor, dass dies die Position der Perlen zum Zeitpunkt t = 0 ist , und mit jeder verstreichenden Sekunde werden die Perlen fallen um eine Ebene nach unten, sofern sich darunter nicht bereits eine Sicke befindet. In einem solchen Fall ruhen sie einfach auf der darunter liegenden Perle. (Die Stangen sind von links nach rechts nummeriert und die Ebenen sind von unten mit 1, 2, ……… nummeriert. n.)
  2. Nun bleiben zur Zeit t = 1 die unteren 2 Perlen in den ersten beiden Stangen von links an ihren Positionen, während die zweite Perle von oben von der zweiten Stange um eine Ebene nach unten kommt, um auf der Perle darunter zu ruhen. Die Perlen in der 3. und 4. Stange auf Stufe 2 sinken auf Stufe 1. Gleichzeitig sinken die Perlen in den Stangen 3 bis 7 um eine Stufe. Jetzt werden die Zahlen von oben nach unten: 2, 6, 2, 2, 4.
  3. Dies geht so weiter bis zum Zeitpunkt t = 4 , wo wir die sortierte Zahlenfolge von oben nach unten erhalten, die lautet: 1, 2, 2, 4, 7.

Warum heißt es so?

Wenn man versucht, sich diesen Algorithmus vorzustellen, sieht es so aus, als würden Perlen unter dem Einfluss der Schwerkraft auf die unterste Ebene fallen, die sie erreichen können, was dazu führt, dass der Satz von Perlen in absteigender Reihenfolge von unten nach oben angeordnet ist. Wenn Sie Probleme haben, dies zu visualisieren, besuchen Sie diesen Link

Nehmen wir an, wir müssen die Zahlen 3, 4, 1, 2 sortieren. Der obige Algorithmus würde so funktionieren.

Perlensortierung funktioniert

Unten ist der Code, versuchen Sie ihn selbst zu implementieren, bevor Sie sich den Code ansehen.

Der Code:

// C++ program to implement gravity/bead sort
#include <bits/stdc++.h>
using namespace std;
  
#define BEAD(i, j) beads[i * max + j]
  
// function to perform the above algorithm
void beadSort(int *a, int len)
{
    // Find the maximum element
    int max = a[0];
    for (int i = 1; i < len; i++)
        if (a[i] > max)
           max = a[i];
  
    // allocating memory
    unsigned char beads[max*len];
    memset(beads, 0, sizeof(beads));
  
    // mark the beads
    for (int i = 0; i < len; i++)
        for (int j = 0; j < a[i]; j++)
            BEAD(i, j) = 1;
  
    for (int j = 0; j < max; j++)
    {
        // count how many beads are on each post
        int sum = 0;
        for (int i=0; i < len; i++)
        {
            sum += BEAD(i, j);
            BEAD(i, j) = 0;
        }
  
        // Move beads down
        for (int i = len - sum; i < len; i++)
            BEAD(i, j) = 1;
    }
  
    // Put sorted values in array using beads
    for (int i = 0; i < len; i++)
    {
        int j;
        for (j = 0; j < max && BEAD(i, j); j++);
  
        a[i] = j;
    }
}
  
// driver function to test the algorithm
int main()
{
    int a[] = {5, 3, 1, 7, 4, 1, 1, 20};
    int len = sizeof(a)/sizeof(a[0]);
  
    beadSort(a, len);
  
    for (int i = 0; i < len; i++)
        printf("%d ", a[i]);
  
    return 0;
}

Ausgabe:

1 1 1 3 4 5 7 20

Zeitkomplexität:
Die Laufzeitkomplexität des Algorithmus reicht von O(1) bis O(S) (S ist die Summe der eingegebenen Ganzzahlen), abhängig von der Perspektive des Benutzers. Abschließend werden drei mögliche Implementierungen vorgeschlagen.

  1. O(1)  : Alle Perlen zusammen als eine einzige (gleichzeitige) Operation fallen lassen. Diese Komplexität ist in der Praxis nicht umsetzbar.
  2. O(n^1^/^2 ): In einem realistischen physikalischen Modell, das die Schwerkraft nutzt, ist die Zeit, die benötigt wird, um die Perlen fallen zu lassen, proportional zur Quadratwurzel der maximalen Höhe, die wiederum proportional zu n ist.
  3. O(n)  : Ablegen der Perlenreihe im Rahmen (die eine Zahl darstellt) als separater Vorgang, da die Anzahl der Reihen gleich n ist.
  4. O(S)  : Fallenlassen jeder einzelnen Perle als separate Operation, da S die Summe aller Perlen ist.

Wie die Pigeonhole-Sortierung ist die Perlensortierung insofern ungewöhnlich, als sie im schlimmsten Fall schneller als O( n log n) arbeiten kann, was im schlimmsten Fall die schnellstmögliche Leistung für eine Vergleichssortierung ist. Dies ist möglich, da der Schlüssel für eine Perlensortierung immer eine positive Ganzzahl ist und die Perlensortierung ihre Struktur ausnutzt.

Raumkomplexität: Die Perlensortierung ist der Rekordhalter beim Abfall. Die Kosten für den zusätzlichen Speicher übersteigen die Kosten für die Speicherung des Arrays selbst. Seine Speicherkomplexität ist O(n^2 )

Verweise:

Dieser Artikel wurde von Palash Nigam beigesteuert . Wenn Ihnen GeeksforGeeks gefällt und Sie einen Beitrag leisten möchten, können Sie auch einen Artikel über Contribute.geeksforgeeks.org schreiben oder Ihren Artikel per E-Mail an Contribute@geeksforgeeks.org senden. Sehen Sie, wie Ihr Artikel auf der Hauptseite von GeeksforGeeks erscheint, und helfen Sie anderen Geeks.

Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .