Ämbri sortimise algoritm (Java, Python, C/C++ Code Näited)

⚡ Nutikas kokkuvõte

Bucket Sort hajutab sisendelemendid mitmesse ämbrisse, sorteerib iga ämbri eraldi ja kogub need kokku lõpliku sorteeritud massiivi loomiseks.

🪣 Põhiidee: Bucket Sort jagab väärtused ämbrite vahel, sorteerib iga ämbri ja seejärel liidab need järjekorda.
📊 Parim sobivus: Ämbrite sortimine toimib kõige paremini ühtlaselt jaotatud ujukoomade puhul vahemikus [0.0, 1.0] või ühtlaselt jaotatud täisarvude puhul.
⚡ Aja keerukus: Keskmine ja parim juhtum saavutavad O(n+k) lineaarse ajaga; halvim juhtum halveneb O(n²)-ni.
✅ Plussid: Ämbreid saab töödelda paralleelselt, mis sobib suurte andmekogumite väliseks sortimiseks.
🧪 Rakendamine: Code C-s C++, Pythonja Java demonstreerib nii ujukoma- kui ka täisarvulisi variante.

Loe rohkem

Mis on koppsorteerimine?

Ämbrisorteerimine, mida sageli nimetatakse prügikastisorteerimiseks, on võrdluspõhine jaotussorteerimismeetod, mis võtab sisendina vastu sortimata massiivi ja annab väljundiks sorteeritud massiivi. See tehnika jaotab elemendid mitmesse ämbrisse ja sorteerib iga ämbri eraldi, kasutades mõnda muud sortimisalgoritmi, näiteks lisamissortimist. Seejärel ühendatakse kõik ämbrid, et moodustada lõplik sorteeritud massiiv.

Ämbrite sortimist kasutatakse tavaliselt siis, kui elemendid on:

Ujukoma väärtused
Ühtlaselt jaotunud teadaolevas vahemikus

Ämbrite sortimise ajaline keerukus sõltub kasutatavate ämbrite arvust ja sisendjaotuse ühtlusest. Kuigi teised sortimisalgoritmid, näiteks kest sorteerida, liitmise sortimine, hunniku sortimine ja kiirsort Parima võimaliku ajalise keerukuse saavutamiseks O(n*logn) võib Bucket Sort algoritm soodsatel tingimustel saavutada lineaarse ajalise keerukuse O(n).

Ämbrite kaupa sortimine järgib hajutatud-kogutud meetodit. Elemendid hajutatakse vastavatesse ämbritesse, sorteeritakse iga ämbri sees ja kogutakse viimase sammuna sorteeritud massiivi moodustamiseks. Seda hajutatud-kogutud meetodit käsitletakse järgmises osas.

Hajutamise-kogumise lähenemisviis

Suuremahuliste ja keeruliste probleemide otsene lahendamine võib kohati olla keeruline. Hajutatud-kogutud lähenemisviis lahendab selliseid probleeme, jagades kogu andmestiku klastriteks. Iga klastrit töödeldakse eraldi ja tulemused koondatakse lõpliku vastuse saamiseks.

Nii rakendab Bucket Sort algoritm hajumis-kogumismeetodit:

Kuidas koppsortimine töötab

Bucket Sort'i põhiline tööpõhimõte on järgmine:

Luuakse tühjade ämbrite komplekt. Olenevalt valitud poliitikast võib ämbrite arv varieeruda.
Sisendmassiivist paigutatakse iga element vastavasse ämbrisse.
Iga ämber sorteeritakse eraldi, kasutades teisese sortimise algoritmi.
Sorteeritud ämbrid liidetakse kokku, et luua üks väljundmassiiv.

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

1. meetod: ujukomaga sortimise algoritm Numbers

Ujukomaarvude ämbrisorteerimise algoritm vahemikus [0.0, 1.0]:

Step 1) Loo kümme (10) tühja ämbrit. Esimene ämber sisaldab numbreid vahemikus [0.0, 0.1]. Teine ämber sisaldab numbreid [0.1, 0.2] jne.

Step 2) Iga massiivi elemendi jaoks:

a. Arvutage rühmindeksit järgmise valemi abil:
bucket_index = buckets_of_buckets * massiivi_element
b. Lisa element ämbrisse[ämbri_index]

Step 3) Sorteerige iga ämber eraldi, kasutades sisestussortimist.

Step 4) Ühenda kõik ämbrid üheks sorteeritud massiiviks.

Vaatame näidet ämbrite sortimisest. Selles näites sorteerime järgmise massiivi:

Step 1) Esmalt loome 10 tühja ämbrit. Esimene ämber sisaldab numbreid vahemikus [0.0, 0.1]. Teine ämber sisaldab numbreid vahemikus [0.1, 0.2) jne.

Step 2) Arvutage iga massiivi elemendi jaoks ämbri indeks ja asetage element sellesse ämbrisse.

Kaubaindeksi arvutamiseks kasutatakse valemit:
bucket_index = buckets_of_buckets * massiivi_element

Salvestusindeksi arvutamine:
a) 0.78
      bucket_index = buckets_of_buckets * massiivi_element
              = 10 * 0.78
              = 7.8
Seega element 0.78 on salvestatud kas bucket[floor(7.8)] või bucket[7].

b) 0.17
      bucket_index = buckets_of_buckets * massiivi_element
              = 10 * 0.17
              = 1.7

Massiivi element 0.17 on salvestatud kas bucket[floor(1.7)] või bucket[1].

c) 0.39
      bucket_index = buckets_of_buckets * massiivi_element
              = 10 * 0.39
              = 3.9
0.39 on salvestatud kas ämbrisse[põrand(3.9)] või ämbrisse[3].

Pärast kõigi massiivi elementide üle käimist näevad ämbrid välja järgmised:

Step 3) Seejärel sorteeritakse iga ämber lisamissortimise abil. Pärast sortimisoperatsiooni on väljund:

Step 4) Viimases etapis liidetakse ämbrid üheks massiiviks. See massiiv on sisendi sorteeritud tulemus.

Iga ämber liidetakse väljundmassiiviga. Näiteks teise ämbri elementide liitmine:

Viimaste ämbrielementide liitmine on näidatud allpool:

Pärast liitmist on saadud massiiv soovitud sorteeritud massiiv.

Koppsorteerimisprogramm keeles C/C++

sisend:

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

Väljund:

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

Koppsorteerimise programm Python

sisend:

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

Väljund:

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

Kopp Sorteeri sisse Java

sisend:

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

Väljund:

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

2. meetod: täisarvuliste elementide ämbrisorteerimise algoritm

Sisendi puhul, mis sisaldab numbreid väljaspool vahemikku [0.0, 1.0], on ämbrite sortimise algoritm eelmisest algoritmist veidi erinev. algoritmSellisel juhul on vajalikud järgmised sammud:

Step 1) Leia massiivi maksimaalsed ja minimaalsed elemendi arvud.

Step 2) Valige ämbrite arv n ja initsialiseerige need tühjadeks.

Step 3) Arvutage iga ämbri vahemik või ulatus järgmise valemi abil:
span = (maximum - minimum) / n

Step 4) Iga massiivi elemendi jaoks:

1. Arvutage ämbriindeks:
bucket_index = (element - minimum) / span
2. Lisa element ämbrisse[ämbri_index]

Step 5) Sorteerige iga ämber sisestussortimise abil.

Step 6) Ühendage kõik ämbrid üheks massiiviks.

Vaatame selle ämbrisortimise algoritmi näidet. Selles näites sorteerime järgmise massiivi:

Step 1) Esimeses etapis leiame antud massiivi elementide maksimaalse ja minimaalse arvu. Selle näite puhul on maksimaalne arv 24 ja minimaalne 1.

Step 2) Järgmisena valime tühjade ämbrite arvu n. Selles näites kasutame 5 ämbrit ja initsialiseerime need tühjadena.

Step 3) Iga ämbri ulatus arvutatakse järgmise valemi abil:
span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Seega esimene ämber sisaldab numbreid vahemikus [0, 5]. Teine ämber sisaldab numbreid vahemikus [5, 10) jne.

Step 4) Iga massiivi elemendi jaoks arvutage ämbriindeks ja asetage element sellesse ämbrisse. Ämbriindeks arvutatakse järgmise valemi abil:
bucket_index = (element - minimum) / span

Salvestusindeksi arvutamine:

a) 11
bucket_index = (element – miinimum) / span
= (11 – 1) / 4
= 2

Seega on element 11 salvestatud ämbrisse[2].

b) 9
bucket_index = (element – miinimum) / span
= (9 – 1) / 4
= 2

Märge: Kuna 9 on elemendi bucket[1] piirielement, lisatakse see elemendile bucket[1], selle asemel et paigutada see eelmise elemendiga samasse ämbrisse.

Pärast iga elemendi toimingute tegemist näevad ämbrid välja järgmised:

Step 5) Nüüd sorteeritakse iga ämber lisamissortimise abil. Ämbrid pärast sortimist:

Step 6) Viimases etapis liidetakse ämbrid üheks massiiviks. See massiivi on sisendi sorteeritud tulemus.

Koppsorteerimisprogramm keeles C/C++

sisend:

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

Väljund:

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

Koppsorteerimise programm Python

sisend:

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)

Väljund:

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

Kopp Sorteeri sisse Java

sisend:

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

Väljund:

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

Bucket Sort'i plussid ja miinused

Plusse	Miinused
Teeb kiiremaid arvutusi ühtlaselt jaotatud andmete puhul	Tarbib rohkem ruumi võrreldes kohapealsete sortimisalgoritmidega
Saab kasutada suurte andmekogumite välise sortimismeetodina	Toimib halvasti, kui andmed pole ühtlaselt jaotunud
Kopasid saab töödelda nii iseseisvalt kui ka paralleelselt	Nõuab eelnevat teadmist andmevahemiku ja jaotuse kohta

Koppsortimise keerukuse analüüs

Ämbrite sortimise aja keerukus

Parima juhtumi keerukus: Kui kõik massiivi elemendid on igas ämbris ühtlaselt jaotatud ja eelnevalt sorteeritud, kulub elementide hajutamiseks vastavatesse ämbritesse O(n) aega. Seejärel sorteeritakse iga ämber, kasutades sisestamise sort maksab O(k). Seega on üldine keerukus O(n+k).
Juhtumi keskmine keerukus: Keskmiste juhtumite puhul eeldame, et sisendid on ühtlaselt jaotatud. Seega saavutab ämbrisortimise algoritm lineaarse aja keerukuse O(n+k). Siin kulub elementide hajutamiseks O(n) aega ja nende sortimiseks lisamissortimise abil O(k) aega.
Halvima juhtumi keerukus: Halvimal juhul ei ole elemendid ühtlaselt jaotunud ja koonduvad ühte või kahte ämbrisse. Sellisel juhul käitub ämbrite kaupa sortimine sarnaselt mullide sortimise algoritmSeega on halvimal juhul Bucket Sort'i ajaline keerukus O(n²).

Koppsortimise ruumi keerukus

Bucket Sort'i ruumi keerukus on O(n*k). Siin on n elementide arv ja k on ämbrite arv, mis on vajalik nende hoidmiseks sortimise ajal.

KKK

Kasutage ämbrisortimist (Bucket Sort), kui sisendväärtused on ühtlaselt jaotunud teadaolevas vahemikus, eriti ujukomaarvude puhul vahemikus [0.0, 1.0]. See annab selliste andmete puhul lineaarse aja, kuid toimib halvasti klasterdatud või tundmatute jaotuste korral.

Ämbrite kaupa sortimine on stabiilne, kui iga ämbri sees kasutatav sisemine sortimisalgoritm on stabiilne. Lisamissortimine säilitab võrdsete elementide suhtelise järjestuse, seega peetakse lisamissortimist kasutavat standardset ämbrite kaupa sortimise rakendust stabiilseks.

Ämbrite sortimine (Bucket Sort) grupeerib elemendid väärtusvahemiku järgi ja sorteerib iga ämbri teise algoritmi abil. Radix Sort (Radix Sort) grupeerib numbrid numbrite kaupa ja kasutab sisemiselt loendavat sortimist. Ämbrite sortimine eelistab ühtlaselt jaotatud ujukomaarve; Radix Sort (Radix Sort) eelistab fikseeritud laiusega täisarve või stringe.

Ämbrisortimise halvimal juhul on ajaline keerukus O(n²). See juhtub siis, kui kõik sisendelemendid langevad ühte ämbrisse, sundides sisemist sortimist (tavaliselt lisamissortimist) käituma ruutsortimise põhimõttel. Ühtlane jaotus väldib seda stsenaariumi.

Jah. Negatiivsete väärtuste käsitlemiseks leidke nii miinimum kui ka maksimum ning seejärel arvutage ämbriindeks, kasutades valemit (element – miinimum) / span. See nihutab negatiivsed väärtused mittenegatiivsesse indeksruumi ja laseb standardsel ämbrisortimise loogikal muutumatult jätkuda.

Tehisintellektil põhinevad platvormid nagu VisuAlgo, Algorithm Visualizer ja ChatGPT loodud samm-sammult juhised traces aitavad õppijatel visualiseerida ämbrite sortimist. Need animeerivad hajumise, sortimise ja kogumise etappe, muutes ämbrite indeksi matemaatika ja jaotamise loogika arusaadavamaks.

Tehisintellektil põhinevad soovitajad analüüsivad andmestiku suurust, väärtuste jaotust ja mälupiiranguid, et soovitada sobivat algoritmi. Ühtlaselt jaotunud ujukomaarvude puhul eelistavad sellised süsteemid ämbrisortimist (Bucket Sort). Segatud täisarvude vahemike puhul võivad nad soovitada kiirsortimist või radiksisortimist (Radix Sort).

Ämbri sortimise algoritm (Java, Python, C/C++ Code Näited)

Mis on koppsorteerimine?

Hajutamise-kogumise lähenemisviis

Kuidas koppsortimine töötab

Pseudo Code

1. meetod: ujukomaga sortimise algoritm Numbers

Koppsorteerimisprogramm keeles C/C++

Koppsorteerimise programm Python

Kopp Sorteeri sisse Java

2. meetod: täisarvuliste elementide ämbrisorteerimise algoritm

Koppsorteerimisprogramm keeles C/C++

Koppsorteerimise programm Python

Kopp Sorteeri sisse Java

Bucket Sort'i plussid ja miinused

Koppsortimise keerukuse analüüs

Ämbrite sortimise aja keerukus

Koppsortimise ruumi keerukus

KKK

Võta see postitus kokku järgmiselt:

Tellige uudiskiri

Mis on koppsorteerimine?

Hajutamise-kogumise lähenemisviis

Kuidas koppsortimine töötab

Pseudo Code

1. meetod: ujukomaga sortimise algoritm Numbers

SEOTUD ARTIKLID

Koppsorteerimisprogramm keeles C/C++

Koppsorteerimise programm Python

Kopp Sorteeri sisse Java

2. meetod: täisarvuliste elementide ämbrisorteerimise algoritm

Koppsorteerimisprogramm keeles C/C++

Koppsorteerimise programm Python

Kopp Sorteeri sisse Java

Bucket Sort'i plussid ja miinused

Koppsortimise keerukuse analüüs

Ämbrite sortimise aja keerukus

Koppsortimise ruumi keerukus

KKK

Võta see postitus kokku järgmiselt:

Tellige uudiskiri