Ryhmälajittelualgoritmi (Java, Python, C/C++ Esimerkkejä koodista)
Sarah Chen
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
- Liukulukuarvot
- 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:
Kuinka ämpärilajittelu toimii
Kauhalajittelun toimintaperiaate on seuraava:
- Luodaan joukko tyhjiä kauhoja. Eri käytäntöjen mukaan ämpärien määrä voi vaihdella.
- Aseta syöttötaulukosta jokainen elementti sitä vastaavaan ryhmään.
- Lajittele ne kauhat yksitellen.
- 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-
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.
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].
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].
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].
Kun kaikki taulukon elementit on iteroitu, ryhmät ovat seuraavat:
Vaihe 3) Tämän jälkeen jokainen ryhmä lajitellaan lisäyslajittelulla. Lajittelun jälkeen tulos olisi:
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:
Viimeisten kauhan elementtien ketjutus on seuraava:
Yhdistyksen jälkeen tuloksena oleva taulukko on haluttu lajiteltu matriisi.
ä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-
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.
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].
-
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.
Kun toiminnot on suoritettu kullekin elementille, kauhat ovat seuraavat:
Vaihe 5) Nyt jokainen ryhmä lajitellaan lisäyslajittelulla. Kauhat lajittelun jälkeen-
Vaihe 6) Viimeisessä vaiheessa kauhat yhdistetään yhdeksi taulukoksi. Että 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; 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ä.