Ryhmälajittelualgoritmi (Java, Python, C/C++ Code Esimerkkejä)

⚡ Älykäs yhteenveto

Bucket Sort sirottelee syöteelementit useisiin säilöihin, lajittelee jokaisen säilön erikseen ja kerää ne yhteen luodakseen lopullisen lajitellun taulukon.

🪣 Perusidea: Bucket Sort jakaa arvot säilöjen välillä, lajittelee jokaisen ja ketjuttaa ne sitten järjestykseen.
📊 Parhaiten sopiva: Ämpärilajittelu toimii parhaiten tasaisesti jakautuneilla liukulukuilla [0.0, 1.0] tai tasaisesti jakautuneilla kokonaisluvuilla.
⚡ Ajan monimutkaisuus: Keskimääräinen ja paras tapaus saavuttavat lineaarisen ajan O(n+k); pahin tapaus heikkenee arvoon O(n²).
✅ edut: Kauhoja voidaan käsitellä rinnakkain, mikä sopii suurten tietojoukkojen ulkoiseen lajitteluun.
🧪 toteutus: Code C-kielellä C++, Pythonja Java esittelee sekä liukuluku- että kokonaislukuvariantteja.

Lue lisää

Mikä on ämpärilajittelu?

Bucket Sort (säiliölajittelu), jota usein kutsutaan lokerolajitteluksi, on vertailuun perustuva jakaumalajittelumenetelmä, joka hyväksyy syötteeksi lajittelemattoman taulukon ja tuottaa tulosteeksi lajitellun taulukon. Tämä tekniikka jakaa elementit useisiin säilöihin ja lajittelee jokaisen säilön erikseen käyttämällä toista lajittelualgoritmia, kuten lisäyslajittelua. Sitten kaikki säilöt yhdistetään lopullisen lajitellun taulukon muodostamiseksi.

Kauhalajittelua käytetään yleisesti, kun elementit ovat:

Liukulukuarvot
Tasaisesti jakautunut tunnetulle alueelle

Kauhalajittelun aikavaativuus riippuu käytettyjen kauhojen lukumäärästä ja syötejakauman tasaisuudesta. Vaikka muut lajittelualgoritmit, kuten kuorityyppinen, yhdistä lajittelu, kasalajittelu ja pikalajittelu Parhaimmillaan aikakompleksisuuden ollessa O(n*logn), Bucket Sort -algoritmi voi suotuisissa olosuhteissa saavuttaa lineaarisen aikakompleksisuuden O(n).

Ämpärilajittelu noudattaa sironta-keräysmenetelmää. Elementit sirotellaan vastaaviin ämpäreihin, lajitellaan kunkin ämpärin sisällä ja kootaan viimeisessä vaiheessa lajitelluksi taulukoksi. Tätä sironta-keräysmenetelmää käsitellään seuraavassa osiossa.

Scatter-Getting-lähestymistapa

Laajamittaisten ja monimutkaisten ongelmien ratkaiseminen suoraan voi toisinaan olla haastavaa. Hajontamenetelmä ratkaisee tällaiset ongelmat jakamalla koko tietojoukon klustereihin. Jokainen klusteri käsitellään erikseen, ja tulokset yhdistetään lopullisen vastauksen tuottamiseksi.

Näin Bucket Sort -algoritmi toteuttaa scatter-gather-metodin:

Kuinka ämpärilajittelu toimii

Kauhalajittelun perusperiaate on seuraava:

Luodaan joukko tyhjiä säilöjä. Säilöjen määrä voi vaihdella valitun käytännön mukaan.
Syötetaulukosta jokainen elementti sijoitetaan vastaavaan säiliöön.
Jokainen ämpäri lajitellaan erikseen toissijaisen lajittelualgoritmin avulla.
Lajitellut säiliöt ketjutetaan yhteen tulostematriisiin.

Pseudo Code

Start
Create N empty buckets
For each array element:
    Calculate bucket index
    Put that element into the corresponding bucket
For each bucket:
    Sort elements within each bucket
Merge all the elements from each bucket
Output the sorted array
End

Tapa 1: Liukulukujen lajittelualgoritmi Numbers

Liukulukujen ämpärilajittelualgoritmi väliltä [0.0, 1.0]:

Vaihe 1) Luo kymmenen (10) tyhjää säiliötä. Ensimmäisessä säiliössä on numerot väliltä [0.0, 0.1]. Toisessa säiliössä on numerot väliltä [0.1, 0.2] ja niin edelleen.

Vaihe 2) Jokaiselle taulukon elementille:

a. Laske kategoriaindeksi kaavalla:
bucket_index = buckets_lukumäärä * taulukon_elementti
b. Lisää elementti bucket[bucket_index]-osioon

Vaihe 3) Lajittele kukin kauha yksitellen lisäyslajittelulla.

Vaihe 4) Yhdistä kaikki säiliöt yhdeksi lajitelluksi taulukoksi.

Käydään läpi esimerkki ämpärilajittelusta. Tässä esimerkissä lajittelemme seuraavan taulukon:

Vaihe 1) Ensin luomme 10 tyhjää ämpäriä. Ensimmäinen ämpäri sisältää luvut väliltä [0.0, 0.1]. Toinen ämpäri sisältää luvut väliltä [0.1, 0.2] ja niin edelleen.

Vaihe 2) Laske jokaiselle taulukon alkiolle sen säiliöindeksi ja sijoita alkio kyseiseen säiliöön.

Kauhaindeksi lasketaan kaavalla:
bucket_index = buckets_lukumäärä * taulukon_elementti

Ryhmäindeksin laskenta:
a) 0.78
      bucket_index = buckets_lukumäärä * taulukon_elementti
              = 10 0.78 * XNUMX
              = 7.8
Näin ollen alkio 0.78 on tallennettuna bucket[floor(7.8)]- tai bucket[7]-elementtiin.

b) 0.17
      bucket_index = buckets_lukumäärä * taulukon_elementti
              = 10 0.17 * XNUMX
              = 1.7

Taulukon alkio 0.17 on tallennettu bucket[floor(1.7)]- tai bucket[1]-kansioon.

c) 0.39
      bucket_index = buckets_lukumäärä * taulukon_elementti
              = 10 0.39 * XNUMX
              = 3.9
0.39 on varastoitu bucket[floor(3.9)]- tai bucket[3]-kenttään.

Kun kaikki taulukon alkiot on iteroitu, säiliöt näyttävät tältä:

Vaihe 3) Jokainen säiliö lajitellaan sitten lisäyslajittelulla. Lajitteluoperaation jälkeen tuloste on:

Vaihe 4) Viimeisessä vaiheessa säiliöt ketjutetaan yhdeksi taulukoksi. Tämä taulukko on syötteen lajiteltu tulos.

Jokainen säiliö ketjutetaan tulostaulukkoon. Esimerkiksi toisen säiliön elementtien ketjuttaminen:

Viimeisten ämpärielementtien ketjutus on esitetty alla:

Yhdistämisen jälkeen tuloksena oleva taulukko on haluttu lajiteltu taulukko.

ämpärilajitteluohjelma C/C++

input:

//Bucket Sort Program in C/C++
//For values without integer parts
#include <bits/stdc++.h>
#define BUCKET_SIZE 10
using namespace std;
void bucketSort(float input[], int array_size)
{
  vector <float>bucket[BUCKET_SIZE];
  for (int i = 0; i < array_size; i++) {
    int index = BUCKET_SIZE*input[i];
    bucket[index].push_back(input[i]);
  }
  for (int i = 0; i < BUCKET_SIZE; i++)
    sort(bucket[i].begin(), bucket[i].end());
  int out_index = 0;
  for (int i = 0; i < BUCKET_SIZE; i++)
    for (int j = 0; j < bucket[i].size(); j++)
      input[out_index++] = bucket[i][j];
}
int main()
{
  float input[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.69};
  int array_size = sizeof(input)/sizeof(input[0]);

  bucketSort(input, array_size);
  cout <<"Sorted Output: 
";
  for (int i = 0; i< array_size; i++)
    cout<<input[i]<<" ";
  return 0;
}

lähtö:

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

Sämpärilajitteluohjelma sisään Python

input:

# Bucket Sort Program in Python
# For values without integer parts
def bucketSort(input):
    output = []
    bucket_size = 10
    for bucket in range(bucket_size):
        output.append([])
    for element in input:
        index = int(bucket_size * element)
        output[index].append(element)
    for bucket in range(bucket_size):
        output[bucket] = sorted(output[bucket])
    out_index = 0
    for bucket in range(bucket_size):
        for element in range(len(output[bucket])):
            input[out_index] = output[bucket][element]
            out_index += 1
    return input

input = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.69]
print("Sorted Output:")
print(bucketSort(input))

lähtö:

Sorted Output:
[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]

Kauha Lajittele Java

input:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    private static final int BUCKET_SIZE = 10;
    public static void bucketSort(float[] input, int arraySize) {
        List<Float>[] bucket = new ArrayList[BUCKET_SIZE];
        for (int i = 0; i < arraySize; i++) {
            int index = (int)(BUCKET_SIZE * input[i]);
            if (bucket[index] == null) {
                bucket[index] = new ArrayList<>();
            }
            bucket[index].add(input[i]);
        }
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                Collections.sort(bucket[i]);
            }
        }
        int outIndex = 0;
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                for (float value: bucket[i]) {
                    input[outIndex++] = value;
                }
            }
        }
    }
    public static void main(String[] args) {
        float[] input = {0.78f,0.17f,0.39f,0.26f,0.72f,0.94f,0.21f,0.12f,0.23f,0.69f};
        int arraySize = input.length;
        bucketSort(input, arraySize);
        System.out.println("Sorted Output:");
        for (int i = 0; i < arraySize; i++) {
            System.out.print(input[i]+" ");
        }
    }
}

lähtö:

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

Tapa 2: Kokonaislukuelementtien sarjalajittelualgoritmi

Syötteen lajittelualgoritmi, joka sisältää lukuja välin [0.0, 1.0] ulkopuolella, eroaa hieman edellisestä algoritmiTässä tapauksessa tarvittavat vaiheet ovat seuraavat:

Vaihe 1) Etsi taulukon suurimmat ja pienimmät alkiot.

Vaihe 2) Valitse säilöjen lukumäärä n ja alusta ne tyhjiksi.

Vaihe 3) Laske kunkin segmentin alue tai jänneväli käyttämällä kaavaa:
span = (maximum - minimum) / n

Vaihe 4) Jokaiselle taulukon elementille:

1. Laske kategoriaindeksi:
bucket_index = (element - minimum) / span
2. Lisää elementti bucket[bucket_index]-osioon

Vaihe 5) Lajittele kukin segmentti lisäyslajittelulla.

Vaihe 6) Yhdistä kaikki kauhat yhdeksi taulukoksi.

Käydään läpi esimerkki tästä Bucket Sort -algoritmista. Tässä esimerkissä lajittelemme seuraavan taulukon:

Vaihe 1) Ensimmäisessä vaiheessa etsitään annetun taulukon suurin ja pienin alkioiden määrä. Tässä esimerkissä suurin on 24 ja pienin on 1.

Vaihe 2) Seuraavaksi valitsemme tyhjien säiliöiden lukumäärän, n. Tässä esimerkissä käytämme viittä säiliötä ja alustamme ne tyhjiksi.

Vaihe 3) Kunkin kauhan jänneväli lasketaan kaavalla:
span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Näin ollen ensimmäinen säiliö sisältää numerot väliltä [0, 5]. Toinen säiliö sisältää numerot väliltä [5, 10), ja niin edelleen.

Vaihe 4) Laske jokaiselle taulukon alkiolle sen säiliöindeksi ja sijoita alkio kyseiseen säiliöön. Säiliöindeksi lasketaan kaavalla:
bucket_index = (element - minimum) / span

Ryhmäindeksin laskenta:

a) 11
bucket_index = (elementti – minimi) / span
= (11 – 1) / 4
= 2

Näin ollen elementti 11 on tallennettuna säiliössä [2].

b) 9
bucket_index = (elementti – minimi) / span
= (9 – 1) / 4
= 2

Huomautus: Koska 9 on bucket[1]:n rajaava elementti, se liitetään bucket[1]:een sen sijaan, että se sijoitettaisiin samaan bucketiin edellisen elementin kanssa.

Kun kunkin elementin toiminnot on suoritettu, säiliöt näyttävät seuraavalta:

Vaihe 5) Nyt jokainen säiliö lajitellaan lisäyslajittelua käyttäen. Säiliöt lajittelun jälkeen:

Vaihe 6) Viimeisessä vaiheessa säiliöt ketjutetaan yhdeksi taulukoksi. ryhmä on syötteen lajiteltu tulos.

ämpärilajitteluohjelma C/C++

input:

#include<bits/stdc++.h>
using namespace std;
void bucketSort(vector < double > & input, int No_Of_Buckets)
{
  double max_value = * max_element(input.begin(), input.end());
  double min_value = * min_element(input.begin(), input.end());
  double span = (max_value - min_value) / No_Of_Buckets;
  vector<vector <double>> output;
  for (int i = 0; i < No_Of_Buckets; i++)
    output.push_back(vector <double>());
  for (int i = 0; i < input.size(); i++)
  {
    double difference = (input[i] - min_value) / span
     - int((input[i] - min_value) / span);
    if (difference == 0 && input[i] != min_value)
      output[int((input[i] - min_value) / span) - 1].push_back(input[i]);
    else
      output[int((input[i] - min_value) / span)].push_back(input[i]);
  }
  for (int i = 0; i < output.size(); i++)
  {
    if (!output[i].empty())
      sort(output[i].begin(), output[i].end());
  }
  int index = 0;
  for (vector <double> & bucket: output)
  {
    if (!bucket.empty())
    {
      for (double i: bucket)
      {
        input[index] = i;
        index++;
      }
    }
  }
}
int main()
{
  vector <double> input ={11,9,21,8,17,19,13,1,24,12};
  int No_Of_Buckets = 5;
  bucketSort(input, No_Of_Buckets);
  cout<<"Sorted Output:";
  for (int i=0; i < input.size(); i++)
    cout <<input[i]<<" ";
  return 0;
}

lähtö:

Sorted Output:1 8 9 11 12 13 17 19 21 24

Sämpärilajitteluohjelma sisään Python

input:

def bucketSort(input, No_Of_Buckets):
    max_element = max(input)
    min_element = min(input)
    span = (max_element - min_element) / No_Of_Buckets
    output = []
    for bucket in range(No_Of_Buckets):
        output.append([])
    for element in range(len(input)):
        diff = (input[element] - min_element) / span - int(
            (input[element] - min_element) / span
        )
        if diff == 0 and input[element] != min_element:
            output[int((input[element] - min_element) / span) - 1].append(
                input[element]
            )
        else:
            output[int((input[element] - min_element) / span)].append(input[element])
    for bucket in range(len(output)):
        if len(output[bucket]) != 0:
            output[bucket].sort()
    index = 0
    for bucket in output:
        if bucket:
            for element in bucket:
                input[index] = element
                index = index + 1
input = [11, 9, 21, 8, 17, 19, 13, 1, 24, 12]
No_Of_Buckets = 5
bucketSort(input, No_Of_Buckets)
print("Sorted Output:
", input)

lähtö:

Sorted Output:
[1, 8, 9, 11, 12, 13, 17, 19, 21, 24]

Kauha Lajittele Java

input:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    public static void bucketSort(List < Double > input, int No_Of_Buckets) {
        double max_value = Collections.max(input);
        double min_value = Collections.min(input);
        double span =(max_value - min_value) / No_Of_Buckets;
        List<List<Double>> output = new ArrayList<>();
        for (int i = 0; i < No_Of_Buckets; i++) {
            output.add(new ArrayList<>());
        }
        for (Double value: input) {
            double difference = (value - min_value) / span - ((value - min_value) / span);
            if (difference == 0 && value != min_value) {
                output.get((int)((value - min_value) / span) - 1).add(value);
            } else {
                output.get((int)((value - min_value) / span)).add(value);
            }
        }
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
                Collections.sort(bucket);
            }
        }
        int index = 0;
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
                for (Double value: bucket) {
                    input.set(index,value);
                    index++;
                }
            }
        }
    }
    public static void main(String[] args) {
        List <Double> input = new ArrayList<>();
        input.add(11.0);
        input.add(9.0);
        input.add(21.0);
        input.add(8.0);
        input.add(17.0);
        input.add(19.0);
        input.add(13.0);
        input.add(1.0);
        input.add(24.0);
        input.add(12.0);
        int No_Of_Buckets = 5;
        bucketSort(input, No_Of_Buckets);
        System.out.println("Sorted Output:");
        for (Double value: input) {
            System.out.print(value + " ");
        }
    }
}

lähtö:

Sorted Output:
1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0

Bucket Sort -menetelmän plussat ja miinukset

Plussat	MIINUKSET
Suorittaa nopeampaa laskentaa tasaisesti jakautuneella datalla	Kuluttaa enemmän tilaa verrattuna paikallisiin lajittelualgoritmeihin
Voidaan käyttää ulkoisena lajittelumenetelmänä suurille tietojoukoille	Toimii huonosti, kun tiedot eivät ole jakautuneet tasaisesti
Kauhoja voidaan käsitellä itsenäisesti ja rinnakkain	Edellyttää etukäteen tietoa data-alueesta ja -jakaumasta

Sämpärilajittelun monimutkaisuusanalyysi

Kauhan lajitteluajan monimutkaisuus

Paras tapauksen monimutkaisuus: Jos kaikki taulukon alkiot on jaettu tasaisesti ja esilajiteltu kussakin säiliössä, alkioiden hajottaminen vastaaviin säiliöihin vaatii O(n) aikaa. Sitten jokainen säiliö lajitellaan käyttämällä lisäyslaji maksaa O(k). Näin ollen kokonaiskompleksisuus on O(n+k).
Keskimääräinen tapauksen monimutkaisuus: Keskimääräisissä tapauksissa oletamme, että syötteet ovat tasaisesti jakautuneita. Täten Bucket Sort -algoritmi saavuttaa lineaarisen aikakompleksisuuden O(n+k). Tässä elementtien hajottamiseen tarvitaan O(n) aikaa ja niiden lajitteluun lisäyslajittelulla tarvitaan O(k) aikaa.
Pahimman tapauksen monimutkaisuus: Pahimmassa tapauksessa elementit eivät ole tasaisesti jakautuneet ja keskittyvät yhteen tai kahteen ämpäriin. Tässä tapauksessa ämpärilajittelu toimii samankaltaisesti kuin kuplalajittelualgoritmiNäin ollen pahimmassa tapauksessa Bucket Sort -menetelmän aikavaativuus on O(n²).

Kauhalajittelun tilan monimutkaisuus

Bucket Sort -menetelmän avaruusvaativuus on O(n*k). Tässä n on elementtien lukumäärä ja k on niiden säilyttämiseen lajittelun aikana tarvittavien säiliöiden lukumäärä.

UKK

Käytä säiliölajittelua (bucket sort), kun syöttöarvot ovat tasaisesti jakautuneet tunnetulle alueelle, erityisesti liukulukujen ollessa välillä [0.0, 1.0]. Se tarjoaa lineaarisen ajan tällaisille tiedoille, mutta toimii huonosti klusteroituneiden tai tuntemattomien jakaumien kanssa.

Ämpärilajittelu on vakaa, kun kunkin ämpärin sisällä käytetty sisempi lajittelualgoritmi on vakaa. Lisäyslajittelu säilyttää yhtä suurten elementtien suhteellisen järjestyksen, joten lisäyslajittelua käyttävää ämpärilajittelun vakiototeutusta pidetään vakaana.

Bucket Sort (säiliölajittelu) ryhmittelee elementit arvoalueen mukaan ja lajittelee jokaisen säiliön eri algoritmilla. Radix Sort (kantalajittelu) ryhmittelee numerot numero kerrallaan ja käyttää sisäisesti laskevaa lajittelua. Bucket Sort (säiliölajittelu) suosii tasaisesti jakautuneita liukulukuja; Radix Sort (kantalajittelu) suosii kiinteäleveydeisiä kokonaislukuja tai merkkijonoja.

Ämpärilajittelun pahimman mahdollisen aikavaativuuden arvo on O(n²). Tämä tapahtuu, kun kaikki syötealkiot kuuluvat yhteen ämpäriin, jolloin sisälajittelu (yleensä lisäyslajittelu) pakotetaan toimimaan kvadraattisesti. Tasainen jakauma välttää tämän skenaarion.

Kyllä. Negatiivisten lukujen käsittelemiseksi etsi sekä minimi että maksimi ja laske sitten ämpäri-indeksi käyttämällä kaavaa (elementti – minimi) / span. Tämä siirtää negatiiviset arvot ei-negatiiviseen indeksiavaruuteen ja antaa vakiomuotoisen ämpärilajittelulogiikan jatkua muuttumattomana.

Tekoälypohjaiset alustat, kuten VisuAlgo, Algorithm Visualizer ja ChatGPT:n luomat vaiheittaiset ohjeet traces auttavat oppijoita visualisoimaan ämpärilajittelua. Ne animoivat hajonta-, lajittelu- ja keräysvaiheita, mikä helpottaa ämpäri-indeksin matematiikan ja osiointilogiikan ymmärtämistä.

Tekoälypohjaiset suosittelijat analysoivat tietojoukon kokoa, arvojakaumaa ja muistirajoja ehdottaakseen sopivaa algoritmia. Tasaisesti jakautuneille liukulukuille tällaiset järjestelmät suosivat Bucket Sort -menetelmää. Sekalaisten kokonaislukuvälien kohdalla ne voivat ehdottaa pikalajittelua tai Radix-lajittelua.

Ryhmälajittelualgoritmi (Java, Python, C/C++ Code Esimerkkejä)

Mikä on ämpärilajittelu?

Scatter-Getting-lähestymistapa

Kuinka ämpärilajittelu toimii

Pseudo Code

Tapa 1: Liukulukujen lajittelualgoritmi Numbers

ämpärilajitteluohjelma C/C++

Sämpärilajitteluohjelma sisään Python

Kauha Lajittele Java

Tapa 2: Kokonaislukuelementtien sarjalajittelualgoritmi

ämpärilajitteluohjelma C/C++

Sämpärilajitteluohjelma sisään Python

Kauha Lajittele Java

Bucket Sort -menetelmän plussat ja miinukset

Sämpärilajittelun monimutkaisuusanalyysi

Kauhan lajitteluajan monimutkaisuus

Kauhalajittelun tilan monimutkaisuus

UKK

Tiivistä tämä viesti seuraavasti:

Tilaa uutiskirje

Mikä on ämpärilajittelu?

Scatter-Getting-lähestymistapa

Kuinka ämpärilajittelu toimii

Pseudo Code

Tapa 1: Liukulukujen lajittelualgoritmi Numbers

AIHEESEEN LIITTYVÄT ARTIKKELIT

ämpärilajitteluohjelma C/C++

Sämpärilajitteluohjelma sisään Python

Kauha Lajittele Java

Tapa 2: Kokonaislukuelementtien sarjalajittelualgoritmi

ämpärilajitteluohjelma C/C++

Sämpärilajitteluohjelma sisään Python

Kauha Lajittele Java

Bucket Sort -menetelmän plussat ja miinukset

Sämpärilajittelun monimutkaisuusanalyysi

Kauhan lajitteluajan monimutkaisuus

Kauhalajittelun tilan monimutkaisuus

UKK

Tiivistä tämä viesti seuraavasti:

Tilaa uutiskirje