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

Mikä on ämpärilajittelu?

Sämpärilajittelu, jota usein kutsutaan roskalajitteluksi, on vertailulajittelumenetelmä, joka hyväksyy lajittelemattoman taulukon syötteenä ja tuottaa tuloksena lajitellun taulukon. Tämä menetelmä toimii jakamalla elementit useisiin segmentteihin ja lajittelemalla kukin näistä säilöistä erikseen millä tahansa lajittelualgoritmilla, kuten lisäyslajittelulla. Sitten kaikki kauhat yhdistetään yhteen lajiteltuun taulukkoon.

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

  1. Liukulukuarvot
  2. Tasaisesti jakautunut alueelle

Sämpärilajittelun aikamonimutkaisuus riippuu käytettyjen kauhojen määrästä ja syöttöjakauman tasaisuudesta. Vaikka erilaiset lajittelualgoritmit, kuten kuorityyppinen, yhdistä lajittelu, kasalajittelu ja pikalajittelu voi saavuttaa parhaan mahdollisen aikamonimutkaisuuden O(n*logn), ämpärilajittelualgoritmi voi saavuttaa saman lineaarisessa aikakompleksisuudessa tai O(n).

Sämpärilajittelu noudattaa haja-kerää-lähestymistapaa. Tätä lähestymistapaa käytettäessä elementit hajallaan vastaaviin ryhmiin, lajitellaan ämpäriin ja kootaan viimeisenä vaiheena lajiteltuun taulukkoon. Tätä haja-kerää-lähestymistapaa käsitellään seuraavassa osiossa

Hajaa-kerää-lähesty

Laajamittainen, monimutkainen ongelma voi toisinaan olla haastavaa ratkaista. Scatter-gather-lähestymistapa yrittää ratkaista tällaiset ongelmat jakamalla koko tietojoukon klustereihin. Sitten jokainen klusteri käsitellään erikseen ja tuodaan kaikki takaisin yhteen lopullisen vastauksen saamiseksi.

Näin ämpärilajittelualgoritmi toteuttaa sironta-keräysmenetelmän:

Hajaa-kerää-lähesty

Kuinka ämpärilajittelu toimii

Kauhalajittelun toimintaperiaate on seuraava:

  1. Luodaan joukko tyhjiä kauhoja. Eri käytäntöjen mukaan ämpärien määrä voi vaihdella.
  2. Aseta syöttötaulukosta jokainen elementti sitä vastaavaan ryhmään.
  3. Lajittele ne kauhat yksitellen.
  4. Yhdistä lajitellut ryhmät luodaksesi yhden tulostusjonon.

Yksityiskohtaiset työvaiheet esitetään seuraavissa osioissa.

Pseudokoodi

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

Ryhmälajittelualgoritmi liukulukuille alueella 0.0–1.0:

Vaihe 1) Luo kymmenen(10) tyhjää ryhmää siten, että ensimmäinen ryhmä sisältää numeroita välillä [0.0, 0.1). Sitten toinen segmentti sisältää sisällä [0.1, 0.2) ja niin edelleen.

Vaihe 2) Jokaiselle taulukon elementille:

      a. Laske kauhaindeksi kaavalla:
      bucket index= no_of_buckets *array_element
      b. Lisää elementti ämpäriin[bucket_index]

Vaihe 3) Lajittele kukin kauha yksitellen lisäyslajittelulla.

Vaihe 4) Yhdistä kaikki ryhmät yhdeksi taulukoksi.

Katsotaanpa ämpärilajitteluesimerkkiä. Tässä esimerkissä lajittelemme seuraavan taulukon käyttämällä ämpärilajittelualgoritmia-

Liukupisteen lajittelualgoritmi Numbers

Vaihe 1) Ensin luomme 10 tyhjää ämpäriä. Ensimmäinen ryhmä sisältää numerot välillä [0.0, 0.1). Sitten toinen ryhmä sisältää numerot välillä [0.1, 0.2) ja niin edelleen.

Liukupisteen lajittelualgoritmi Numbers

Vaihe 2) Laskemme jokaiselle taulukon elementille sarjaindeksin ja sijoitamme elementin kyseiseen ryhmään.

Sämpäriindeksi voidaan laskea kaavalla:
              bucket_index= no_of_buckets*array_element

Ryhmäindeksin laskenta:
a) 0.78
      bucket_index = no_of_buckets*array_element
                   = 10 * 0.78
                   = 7.8
Näin ollen elementti 0.78 tallennetaan kauhaan[lattia(7.8)] tai kauhaan[7].

Liukupisteen lajittelualgoritmi Numbers

b) 0.17
      bucket_index = no_of_buckets * taulukkoelementti
                   = 10 * 0.17
                   = 1.7

Taulukkoelementti 0.17 tallennetaan ämpäri[floor(1.7)] tai bucket[1].

Liukupisteen lajittelualgoritmi Numbers

c) 0.39
      bucket_index = no_of_buckets * taulukkoelementti
                   = 10*0.39
                   = 3.9
   0.39 säilytetään kauhassa[lattia(3.9)] tai kauhassa[3].

Liukupisteen lajittelualgoritmi Numbers

Kun kaikki taulukon elementit on iteroitu, ryhmät ovat seuraavat:

Liukupisteen lajittelualgoritmi Numbers

Vaihe 3) Tämän jälkeen jokainen ryhmä lajitellaan lisäyslajittelulla. Lajittelun jälkeen tulos olisi:

Liukupisteen lajittelualgoritmi Numbers

Vaihe 4) Viimeisessä vaiheessa kauhat yhdistetään yhdeksi taulukoksi. Tämä matriisi on syötteen lajiteltu tulos.

Jokainen segmentti ketjutetaan tulostusjonoon. Esimerkiksi - toisen kauhan elementtien ketjuttaminen:

Liukupisteen lajittelualgoritmi Numbers

Viimeisten kauhan elementtien ketjutus on seuraava:

Liukupisteen lajittelualgoritmi Numbers

Yhdistyksen jälkeen tuloksena oleva taulukko on haluttu lajiteltu matriisi.

Liukupisteen lajittelualgoritmi Numbers

ämpärilajitteluohjelma C/C++

input:

//Bucket Sort Program in C/C++
//For not having 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: \n";
 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 not having 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

Alueen [0.0, 1.0] ulkopuolella olevia lukuja sisältävän syötteen ämpärilajittelualgoritmi on hieman erilainen kuin edellinen algoritmi. Tässä tapauksessa vaadittavat vaiheet ovat seuraavat:

Vaihe 1) Etsi enimmäis- ja vähimmäiselementit.

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 ryhmäindeksi:
                   bucket_index = (element - minimum)/span
    2.Lisää elementti ämpäriin[bucket_index]

Vaihe 5) Lajittele kukin segmentti lisäyslajittelulla.

Vaihe 6) Yhdistä kaikki kauhat yhdeksi taulukoksi.

Katsotaanpa esimerkkiä tästä segmentin lajittelualgoritmista. Tässä esimerkissä lajittelemme seuraavan taulukon käyttämällä ämpärilajittelualgoritmia-

Kokonaislukuelementtien sarjalajittelualgoritmi

Vaihe 1) Ensimmäisessä vaiheessa on löydettävä annetun taulukon enimmäis- ja minimielementit. Tässä esimerkissä maksimi on 24 ja pienin on 1.

Vaihe 2) Nyt meidän on valittava joukko tyhjiä kauhoja, n. Tässä esimerkissä otamme 5 ämpäriä. Sitten alustamme ne tyhjiksi.

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

Näin ollen ensimmäinen ryhmä sisältää numerot välillä [0, 5). Toinen ryhmä sisältää numerot välillä [5, 10) ja niin edelleen.

Kokonaislukuelementtien sarjalajittelualgoritmi

Vaihe 4) Laskemme jokaiselle taulukon elementille sarjaindeksin ja sijoitamme elementin kyseiseen ryhmään. Sämpäriindeksi voidaan laskea kaavalla:
               bucket_index = (element - minimum)/span

Ryhmäindeksin laskenta:

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

Siten elementti 11 tallennetaan ämpäriin[2].

Kokonaislukuelementtien sarjalajittelualgoritmi

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

Huomautus: Koska 9 on lohkon[1] rajaelementti, se on lisättävä ryhmään[1] sen sijaan, että se lisättäisiin edellisen elementin samaan ryhmään.

Kokonaislukuelementtien sarjalajittelualgoritmi

Kun toiminnot on suoritettu kullekin elementille, kauhat ovat seuraavat:

Kokonaislukuelementtien sarjalajittelualgoritmi

Vaihe 5) Nyt jokainen ryhmä lajitellaan lisäyslajittelulla. Kauhat lajittelun jälkeen-

Kokonaislukuelementtien sarjalajittelualgoritmi

Vaihe 6) Viimeisessä vaiheessa kauhat yhdistetään yhdeksi taulukoksi. Että ryhmä on syötteen lajiteltu tulos.

Kokonaislukuelementtien sarjalajittelualgoritmi

ä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; 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:\n", 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

Plussaa ja miinusta

Plussat MIINUKSET
Suorita nopeampi laskenta Vie enemmän tilaa verrattuna muihin algoritmeihin
Sitä voidaan käyttää ulkoisena lajittelumenetelmänä Toimii huonosti, kun tiedot eivät ole jakautuneet tasaisesti
Kauhat voidaan käsitellä itsenäisesti

Sämpärilajittelun monimutkaisuusanalyysi

Bucket Lajittelun aika monimutkaisuus

  • Paras tapauksen monimutkaisuus:Jos kaikki taulukon elementit jaetaan ja lajitellaan etukäteen tasaisesti, elementtien sirottaminen vastaaviin ämpäriin vaatisi O(n) aikaa. Lajittele sitten kukin ämpäri käyttämällä lisäyslaji maksaisi O(k). Siten kokonaiskompleksisuus olisi O(n+k).
  • Keskimääräinen tapauksen monimutkaisuus:Keskimääräisissä tapauksissa oletetaan, että syötteet ovat jakautuneet tasaisesti. Siten ämpärilajittelualgoritmi saavuttaa lineaarisen aikakompleksisuuden O(n+k). Tässä tarvitaan O(n) aikaa elementtien sirottamiseen ja O(k) aikaa näiden elementtien lajitteluun lisäyslajittelulla.
  • Pahimman tapauksen monimutkaisuus:Pahimmassa tapauksessa elementit eivät ole tasaisesti jakautuneet ja keskittyneet yhteen tai kahteen tiettyyn kauhaan. Siinä tapauksessa ämpärilajittelu toimii a kuplalajittelualgoritmi. Siten pahimmassa tapauksessa kauhalajittelun aikamonimutkaisuus olisi O(n^2).

Kauhalajittelun tilan monimutkaisuus

Kauhalajittelun tilakompleksisuus on O(n*k). Tässä n on elementtien lukumäärä ja k on vaadittujen kauhojen lukumäärä.