Algoritam za sortiranje spremnika (Java, Python, C/C++ Code Primjeri)

⚡ Pametni sažetak

Bucket sortiranje raspršuje ulazne elemente u nekoliko bucketa, sortira svaki bucket neovisno i okuplja ih kako bi se dobio konačni sortirani niz.

🪣 Osnovna ideja: Sortiranje po skupinama dijeli vrijednosti po skupinama, sortira svaku od njih, a zatim ih spaja po redu.
📊 Najbolje odgovara: Bucket sort najbolje funkcionira na jednoliko raspoređenim float brojevima u [0.0, 1.0] ili jednoliko raspoređenim cijelim brojevima.
⚡ Složenost vremena: Prosječni i najbolji slučajevi dosežu linearno vrijeme O(n+k); najgori slučaj degradira na O(n²).
✅ Prednosti: Kante se mogu obrađivati paralelno, što je pogodno za vanjsko sortiranje velikih skupova podataka.
🧪 provedba: Code u C-u, C++, Pythoni Java prikazuje i varijante s pomičnim zarezom i cjelobrojne varijante.

Pročitaj više

Što je Bucket Sort?

Sortiranje po skupinama, često nazivano sortiranje po skupinama, metoda je sortiranja distribucijom temeljena na usporedbi koja prihvaća nesortirani niz kao ulaz, a kao izlaz proizvodi sortirani niz. Ova tehnika distribuira elemente u nekoliko skupina i sortira svaku skupinu pojedinačno pomoću drugog algoritma sortiranja, kao što je sortiranje umetanjem. Zatim se sve skupine spajaju kako bi se formirao konačni sortirani niz.

Bucket sort se obično koristi kada su elementi:

Vrijednosti s pomičnim zarezom
Ravnomjerno raspoređeno po poznatom rasponu

Vremenska složenost sortiranja po skupinama ovisi o broju korištenih skupina i ujednačenosti distribucije ulaznih podataka. Dok drugi algoritmi sortiranja, kao što su sortirati školjke, sortiranje spajanjem, heapsortiranje i živa sorta postići vremensku složenost u najboljem slučaju od O(n*logn), algoritam Bucket Sort može postići linearnu vremensku složenost O(n) pod povoljnim uvjetima.

Sortiranje po skupinama slijedi pristup raspršenja i sakupljanja. Elementi se raspršuju u odgovarajuće skupine, sortiraju unutar svake skupine i skupljaju u sortirani niz kao posljednji korak. Ovaj pristup raspršenja i sakupljanja raspravlja se u sljedećem odjeljku.

Pristup raspršivanja i sakupljanja

Veliki, složeni problemi ponekad mogu biti izazovni za izravno rješavanje. Pristup raspršenja i prikupljanja rješava takve probleme dijeljenjem cijelog skupa podataka u klastere. Svaki klaster se obrađuje zasebno, a rezultati se ponovno spajaju kako bi se dobio konačni odgovor.

Evo kako algoritam Bucket Sort implementira metodu raspršenja i sakupljanja:

Kako radi Bucket Sort

Osnovni princip rada Bucket sortiranja je sljedeći:

Izrađuje se skup praznih spremnika. Broj spremnika može varirati ovisno o odabranoj politici.
Iz ulaznog niza, svaki element se smješta u odgovarajuću skupinu.
Svaka se skupina sortira pojedinačno pomoću sekundarnog algoritma sortiranja.
Sortirane kante se spajaju kako bi se dobio jedan izlazni niz.

Nadimak 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

Metoda 1: Algoritam za sortiranje u segmentu za pokretni zarez Numbers

Algoritam Bucket Sort za brojeve s pomičnim zarezom unutar raspona [0.0, 1.0]:

Korak 1) Napravite deset (10) praznih kanti. Prva kanta sadrži brojeve unutar raspona [0.0, 0.1]. Druga kanta sadrži [0.1, 0.2) i tako dalje.

Korak 2) Za svaki element niza:

a. Izračunajte indeks skupine pomoću formule:
indeks_kategorije = broj_kategorija * element_arraya
b. Umetnite element u kantu[bucket_index]

Korak 3) Razvrstajte svaku kantu zasebno pomoću sortiranja umetanjem.

Korak 4) Spojite sve kontejnere u jedan sortirani niz.

Prođimo kroz primjer sortiranja pomoću bucketa. U ovom primjeru sortirat ćemo sljedeći niz:

Korak 1) Prvo stvaramo 10 praznih kanti. Prva kanta sadrži brojeve u [0.0, 0.1]. Druga kanta sadrži [0.1, 0.2) i tako dalje.

Korak 2) Za svaki element niza izračunajte indeks segmenta i smjestite element u taj segment.

Indeks košarice izračunava se pomoću formule:
indeks_kategorije = broj_kategorija * element_arraya

Izračun skupnog indeksa:
a) 0.78
      indeks_kategorije = broj_kategorija * element_arraya
              = 10 * 0.78
              = 7.8
Dakle, element 0.78 pohranjen je u bucket[floor(7.8)] ili bucket[7].

b) 0.17
      indeks_kategorije = broj_kategorija * element_arraya
              = 10 * 0.17
              = 1.7

Element polja 0.17 pohranjen je u bucket[floor(1.7)] ili bucket[1].

c) 0.39
      indeks_kategorije = broj_kategorija * element_arraya
              = 10 * 0.39
              = 3.9
0.39 se pohranjuje u bucket[floor(3.9)] ili bucket[3].

Nakon iteracije kroz sve elemente niza, kontejneri izgledaju ovako:

Korak 3) Svaka se sekcija zatim sortira pomoću sortiranja umetanjem. Nakon operacije sortiranja, izlaz je:

Korak 4) U završnom koraku, segmenti se spajaju u jedan niz. Taj niz je sortirani rezultat ulaza.

Svaka sekcija je spojena s izlaznim nizom. Na primjer, spajanje elemenata druge sekcija:

Spajanje elemenata posljednjeg kontejnera prikazano je u nastavku:

Nakon spajanja, rezultirajući niz je željeni sortirani niz.

Program za sortiranje spremnika u C/C++

Ulazni:

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

Izlaz:

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

Bucket Sort Program in Python

Ulazni:

# 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))

Izlaz:

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

Kanta Sortiraj u Java

Ulazni:

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]+" ");
        }
    }
}

Izlaz:

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

Metoda 2: algoritam sortiranja u segmentu za cjelobrojne elemente

Algoritam sortiranja po skupinama za unos koji sadrži brojeve izvan raspona [0.0, 1.0] malo se razlikuje od prethodnog. algoritamKoraci potrebni za ovaj slučaj su sljedeći:

Korak 1) Pronađite maksimalni i minimalni broj elemenata u nizu.

Korak 2) Odaberite broj kontejnera, n, i inicijalizirajte ih kao prazne.

Korak 3) Izračunajte raspon ili raspon svake kante pomoću formule:
span = (maximum - minimum) / n

Korak 4) Za svaki element niza:

1. Izračunajte indeks košarice:
bucket_index = (element - minimum) / span
2. Umetnite element u kantu[bucket_index]

Korak 5) Razvrstaj svaku kantu pomoću sortiranja umetanjem.

Korak 6) Spojite sve kante u jedno polje.

Pogledajmo primjer ovog algoritma Bucket Sort. Za ovaj primjer sortirat ćemo sljedeći niz:

Korak 1) U prvom koraku pronalazimo maksimalni i minimalni broj elemenata zadanog niza. Za ovaj primjer, maksimalni broj je 24, a minimalni 1.

Korak 2) Zatim odabiremo broj praznih kanti, n. U ovom primjeru koristimo 5 kanti i inicijaliziramo ih kao prazne.

Korak 3) Raspon svake kante izračunava se pomoću formule:
span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Dakle, prva kanta sadrži brojeve unutar [0, 5). Druga kanta sadrži [5, 10) i tako dalje.

Korak 4) Za svaki element polja izračunajte indeks segmenta i smjestite element u taj segment. Indeks segmenta izračunava se pomoću formule:
bucket_index = (element - minimum) / span

Izračun skupnog indeksa:

a) 11
bucket_index = (element – minimum) / raspon
= (11 – 1) / 4
= 2

Dakle, element 11 je pohranjen u spremniku[2].

b) 9
bucket_index = (element – minimum) / raspon
= (9 – 1) / 4
= 2

Bilješka: Budući da je 9 granični element za bucket[1], dodaje se bucket[1] umjesto da bude smješten u isti bucket kao i prethodni element.

Nakon izvođenja operacija za svaki element, kante izgledaju kako slijedi:

Korak 5) Sada je svaka kanta sortirana pomoću sortiranja umetanjem. Kante nakon sortiranja:

Korak 6) U završnom koraku, kante se spajaju u jedan niz. To poredak je sortirani ishod ulaza.

Program za sortiranje spremnika u C/C++

Ulazni:

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

Izlaz:

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

Bucket Sort Program in Python

Ulazni:

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)

Izlaz:

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

Kanta Sortiraj u Java

Ulazni:

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 + " ");
        }
    }
}

Izlaz:

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

Prednosti i nedostaci sortiranja po bucketima

Prednosti	Nedostaci
Brže izračunava na jednoliko raspoređenim podacima	Zauzima više prostora u usporedbi s algoritmima za sortiranje na mjestu
Može se koristiti kao vanjska metoda sortiranja za velike skupove podataka	Loše radi kada podaci nisu ravnomjerno raspoređeni
Kante se mogu obrađivati neovisno i paralelno	Zahtijeva unaprijed poznavanje raspona i distribucije podataka

Bucket Sort Complexity Analiza

Vremenska složenost sortiranja po segmentima

Složenost u najboljem slučaju: Ako su svi elementi niza ravnomjerno raspoređeni i prethodno sortirani unutar svake ćelije, potrebno je O(n) vremena za raspršivanje elemenata u odgovarajuće ćelije. Zatim se svaka ćelija sortira pomoću umetanje sortirati košta O(k). Stoga je ukupna složenost O(n+k).
Prosječna složenost slučaja: Za prosječne slučajeve pretpostavljamo da su ulazi jednoliko raspoređeni. Stoga algoritam Bucket Sort postiže linearnu vremensku složenost od O(n+k). Ovdje je potrebno O(n) vremena za raspršivanje elemenata i O(k) vremena za njihovo sortiranje pomoću sortiranja umetanjem.
Složenost u najgorem slučaju: U najgorem slučaju, elementi nisu jednoliko raspoređeni i koncentriraju se u jednoj ili dvije kante. U tom slučaju, Bucket Sort se ponaša slično kao algoritam sortiranja mjehurićimaDakle, u najgorem slučaju, vremenska složenost Bucket sortiranja je O(n²).

Prostorna složenost bucket sortiranja

Prostorna složenost sortiranja po skupinama (Bucket Sort) je O(n*k). Ovdje je n broj elemenata, a k broj skupina potrebnih za njihov smještaj tijekom sortiranja.

Pitanja i odgovori

Koristite Bucket sort kada su ulazne vrijednosti ravnomjerno raspoređene u poznatom rasponu, posebno za brojeve s pomičnim zarezom u [0.0, 1.0]. Pruža linearno vrijeme na takvim podacima, ali slabo funkcionira na klasteriranim ili nepoznatim distribucijama.

Sortiranje pomoću kanti je stabilno kada je unutarnji algoritam sortiranja koji se koristi unutar svake kante stabilan. Sortiranje umetanjem čuva relativni redoslijed jednakih elemenata, pa se standardna implementacija sortiranja pomoću kanti smatra stabilnom.

Bucket Sort grupira elemente prema rasponu vrijednosti i sortira svaku ćeliju drugim algoritmom. Radix Sort grupira brojeve znamenku po znamenku i interno koristi sortiranje brojanjem. Bucket Sort preferira jednoliko raspoređene float brojeve; Radix Sort preferira cijele brojeve ili nizove fiksne širine.

Vremenska složenost sortiranja po skupinama u najgorem slučaju je O(n²). To se događa kada svi ulazni elementi padnu u jednu skupinu, prisiljavajući unutarnje sortiranje (obično sortiranje umetanjem) da se ponaša kvadratno. Uniformna distribucija izbjegava ovaj scenarij.

Da. Za obradu negativnih vrijednosti, pronađite i minimum i maksimum, a zatim izračunajte indeks spremnika koristeći (element – minimum) / raspon. To pomiče negativne vrijednosti u nenegativni indeksni prostor i omogućuje standardnoj logici sortiranja spremnika da nastavi nepromijenjena.

Platforme pokretane umjetnom inteligencijom kao što su VisuAlgo, Algorithm Visualizer i ChatGPT-generirani korak-po-korak tracPomažu učenicima da vizualiziraju Bucket Sort. Animiraju faze raspršivanja, sortiranja i sakupljanja, što olakšava razumijevanje matematike indeksiranja i logike particioniranja.

Preporučitelji vođeni umjetnom inteligencijom analiziraju veličinu skupa podataka, distribuciju vrijednosti i ograničenja memorije kako bi predložili odgovarajući algoritam. Za jednoliko raspoređene float brojeve, takvi sustavi preferiraju Bucket Sort. Za miješane cjelobrojne raspone, mogu predložiti quicksort ili Radix Sort.

Algoritam za sortiranje spremnika (Java, Python, C/C++ Code Primjeri)

Što je Bucket Sort?

Pristup raspršivanja i sakupljanja

Kako radi Bucket Sort

Nadimak Code

Metoda 1: Algoritam za sortiranje u segmentu za pokretni zarez Numbers

Program za sortiranje spremnika u C/C++

Bucket Sort Program in Python

Kanta Sortiraj u Java

Metoda 2: algoritam sortiranja u segmentu za cjelobrojne elemente

Program za sortiranje spremnika u C/C++

Bucket Sort Program in Python

Kanta Sortiraj u Java

Prednosti i nedostaci sortiranja po bucketima

Bucket Sort Complexity Analiza

Vremenska složenost sortiranja po segmentima

Prostorna složenost bucket sortiranja

Pitanja i odgovori

Sažmite ovu objavu uz:

Prijavite se za bilten