Algoritmus řazení segmentů (Java, Python, C/C++ Code Příklady)

⚡ Chytré shrnutí

Bucket Sort roztřídí vstupní prvky do několika segmentů, seřadí každý segment nezávisle a shromáždí je, aby vytvořil finální seřazené pole.

🪣 Základní myšlenka: Bucket Sort rozděluje hodnoty mezi buckety, seřadí je a poté je zřetězí v pořadí.
📊 Nejlepší fit: Bucket Sort funguje nejlépe na rovnoměrně rozložených float číslech v rozsahu [0.0, 1.0] nebo rovnoměrně rozložených celých číslech.
⚡ Časová složitost: Průměrný a nejlepší případ dosahuje lineárního času O(n+k); nejhorší případ se zhoršuje na O(n²).
(Tj. Výhody: Buckety lze zpracovávat paralelně, což je vhodné pro externí třídění velkých datových sad.
🧪 Realizace: Code v C., C++, Python, a Java demonstruje varianty s plovoucí desetinnou čárkou i celočíselné varianty.

Přečíst více

Co je bucket Sort?

Bucket Sort, často nazývaný bin sort, je metoda distribučního třídění založená na porovnávání, která přijímá neseřazené pole jako vstup a jako výstup vytváří seřazené pole. Tato technika rozděluje prvky do několika košů a každý koš seřadí jednotlivě pomocí jiného třídicího algoritmu, jako je například vkládání. Poté se všechny koše sloučí dohromady a vytvoří finální seřazené pole.

Bucket Sort se běžně používá, když jsou prvky:

Hodnoty s pohyblivou řádovou čárkou
Rovnoměrně rozložené ve známém rozsahu

Časová složitost metody Bucket Sort závisí na počtu použitých košů a rovnoměrnosti rozdělení vstupů. Zatímco jiné třídicí algoritmy, jako například shell sort, sloučit řazení, hromadné řazení a rychlé řazení dosáhnout v nejlepším případě časové složitosti O(n*logn), může algoritmus Bucket Sort za příznivých podmínek dosáhnout lineární časové složitosti O(n).

Bucket Sort se řídí metodou shromažďování a rozptylu. Prvky jsou rozptýleny do odpovídajících košů, seřazeny uvnitř každého koše a v posledním kroku shromážděny do seřazeného pole. Tato metoda shromažďování a rozptylu je popsána v následující části.

Přístup rozptylu a shromáždění

Rozsáhlé a složité problémy může být občas náročné řešit přímo. Přístup rozptylu a shromažďování řeší takové problémy rozdělením celé datové sady do shluků. Každý shluk je zpracován samostatně a výsledky jsou shrnuty, aby se vytvořila konečná odpověď.

Zde je návod, jak algoritmus Bucket Sort implementuje metodu scatter-gather:

Jak funguje třídění kbelíků

Základní princip fungování Bucket Sort je následující:

Vytvoří se sada prázdných kontejnerů. Počet kontejnerů se může lišit v závislosti na zvolené zásadě.
Ze vstupního pole je každý prvek umístěn do odpovídajícího kontejneru.
Každý segment je seřazen jednotlivě pomocí sekundárního třídicího algoritmu.
Seřazené segmenty jsou zřetězeny a vytvoří jedno výstupní pole.

Nepravý 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: Algoritmus třídění segmentů pro plovoucí desetinnou čárku Numbers

Algoritmus Bucket Sort pro čísla s plovoucí desetinnou čárkou v rozsahu [0.0, 1.0]:

Krok 1) Vytvořte deset (10) prázdných kbelíků. První kbelík obsahuje čísla v rozsahu [0.0, 0.1]. Druhý kbelík obsahuje [0.1, 0.2) atd.

Krok 2) Pro každý prvek pole:

a. Vypočítejte index kbelíku pomocí vzorce:
bucket_index = počet_bucketů * prvek_pole
b. Vložte prvek do bucket[bucket_index]

Krok 3) Seřaďte každý segment jednotlivě pomocí řazení vložení.

Krok 4) Zřetězte všechny segmenty do jednoho seřazeného pole.

Projděme si příklad Bucket Sort. V tomto příkladu seřadíme následující pole:

Krok 1) Nejprve vytvoříme 10 prázdných kbelíků. První kbelík obsahuje čísla v rozsahu [0.0, 0.1). Druhý kbelík obsahuje [0.1, 0.2) atd.

Krok 2) Pro každý prvek pole vypočítejte index segmentu a umístěte prvek do tohoto segmentu.

Index kbelíku se vypočítá pomocí vzorce:
bucket_index = počet_bucketů * prvek_pole

Výpočet indexu segmentu:
a) 0.78
      bucket_index = počet_bucketů * prvek_pole
              = 10 0.78 * XNUMX
              = 7.8
Prvek 0.78 je tedy uložen v bucket[floor(7.8)] nebo bucket[7].

b) 0.17
      bucket_index = počet_bucketů * prvek_pole
              = 10 0.17 * XNUMX
              = 1.7

Prvek pole 0.17 je uložen v bucket[floor(1.7)] nebo bucket[1].

c) 0.39
      bucket_index = počet_bucketů * prvek_pole
              = 10 0.39 * XNUMX
              = 3.9
Hodnota 0.39 je uložena v bucket[floor(3.9)] nebo bucket[3].

Po iteraci přes všechny prvky pole vypadají buckety takto:

Krok 3) Každý segment je poté seřazen pomocí řazení vložením. Po operaci třídění je výstup:

Krok 4) V posledním kroku jsou segmenty zřetězeny do jednoho pole. Toto pole je seřazeným výsledkem vstupu.

Každý segment je zřetězen s výstupním polem. Například zřetězení prvků druhého segmentu:

Zřetězení posledních prvků bucketu je znázorněno níže:

Po zřetězení je výsledné pole požadované seřazené pole.

Program třídění kbelíků v C/C++

Vstup:

//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ýstup:

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

Program třídění kbelíků v Python

Vstup:

# 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ýstup:

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

Kbelík Seřadit Java

Vstup:

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ýstup:

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

Metoda 2: Algoritmus třídění segmentu pro celočíselné prvky

Algoritmus Bucket Sort pro vstup obsahující čísla mimo rozsah [0.0, 1.0] se mírně liší od předchozího. algoritmusV tomto případě jsou nutné následující kroky:

Krok 1) Najděte maximální a minimální počet prvků v poli.

Krok 2) Vyberte počet kontejnerů, n, a inicializujte je jako prázdné.

Krok 3) Vypočítejte rozsah nebo rozsah každého segmentu pomocí vzorce:
span = (maximum - minimum) / n

Krok 4) Pro každý prvek pole:

1. Vypočítejte index kbelíku:
bucket_index = (element - minimum) / span
2. Vložte prvek do bucket[bucket_index]

Krok 5) Seřaďte každý segment pomocí řazení vložení.

Krok 6) Spojte všechny segmenty do jednoho pole.

Pojďme si ukázat příklad algoritmu Bucket Sort. V tomto příkladu seřadíme následující pole:

Krok 1) V prvním kroku najdeme maximální a minimální počet prvků daného pole. V tomto příkladu je maximum 24 a minimum 1.

Krok 2) Dále vybereme počet prázdných košů, n. V tomto příkladu použijeme 5 košů a inicializujeme je jako prázdné.

Krok 3) Rozpětí každého kbelíku se vypočítá pomocí vzorce:
span = (maximum - minimum) / n = (24 - 1) / 5 = 4

První kbelík tedy obsahuje čísla v rozsahu [0, 5]. Druhý kbelík obsahuje [5, 10) atd.

Krok 4) Pro každý prvek pole vypočítejte index segmentu a umístěte prvek do tohoto segmentu. Index segmentu se vypočítá pomocí vzorce:
bucket_index = (element - minimum) / span

Výpočet indexu segmentu:

a) 11
bucket_index = (prvek – minimum) / rozpětí
= (11 – 1) / 4
= 2

Prvek 11 je tedy uložen v bucketu[2].

b) 9
bucket_index = (prvek – minimum) / rozpětí
= (9 – 1) / 4
= 2

Poznámka: Protože 9 je hraniční prvek pro bucket[1], je připojen k bucket[1], místo aby byl umístěn do stejného bucketu jako předchozí prvek.

Po provedení operací pro každý prvek vypadají koše takto:

Krok 5) Nyní je každý segment seřazen pomocí vloženého řazení. Seřazení segmentů:

Krok 6) V posledním kroku jsou segmenty zřetězeny do jednoho pole. To řada je seřazený výsledek vstupu.

Program třídění kbelíků v C/C++

Vstup:

#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ýstup:

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

Program třídění kbelíků v Python

Vstup:

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ýstup:

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

Kbelík Seřadit Java

Vstup:

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ýstup:

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

Výhody a nevýhody třídění pomocí kbelíků

Klady	Nevýhody
Provádí rychlejší výpočty na rovnoměrně rozložených datech	Spotřebovává více místa ve srovnání s algoritmy třídění na místě
Lze použít jako externí metodu třídění pro velké datové sady	Funguje špatně, když data nejsou rovnoměrně distribuována
Kbelíky lze zpracovávat nezávisle i paralelně	Vyžaduje předem znalost rozsahu a distribuce dat

Analýza složitosti třídění segmentů

Časová složitost třídění v bucketu

Nejlepší složitost případu: Pokud jsou všechny prvky pole rovnoměrně rozloženy a předem seřazeny v každém koši, pak je potřeba čas O(n) k rozptýlení prvků do odpovídajících košů. Poté se každý koš setřídí pomocí řazení řazení stojí O(k). Celková složitost je tedy O(n+k).
Průměrná složitost případu: Pro průměrné případy předpokládáme, že vstupy jsou rovnoměrně rozloženy. Algoritmus Bucket Sort tak dosahuje lineární časové složitosti O(n+k). Zde je pro rozptýlení prvků potřeba O(n) času a pro jejich seřazení pomocí vkládání času O(k).
Složitost nejhoršího případu: V nejhorším případě nejsou prvky rovnoměrně rozloženy a koncentrují se v jednom nebo dvou kbelících. V takovém případě se Bucket Sort chová podobně jako algoritmus bublinového tříděníV nejhorším případě je tedy časová složitost metody Bucket Sort O(n²).

Prostorová složitost třídění lopatek

Prostorová složitost metody Bucket Sort je O(n*k). Zde n je počet prvků a k je počet košů potřebných k jejich uložení během třídění.

Nejčastější dotazy

Bucket Sort použijte, když jsou vstupní hodnoty rovnoměrně rozloženy ve známém rozsahu, zejména u čísel s plovoucí desetinnou čárkou v rozsahu [0.0, 1.0]. U takových dat dosahuje lineárního času, ale u klastrovaných nebo neznámých rozdělení dosahuje nízkých výsledků.

Bucket Sort je stabilní, když je stabilní i vnitřní třídicí algoritmus použitý uvnitř každého bucketu. Vkládací řazení zachovává relativní pořadí stejných prvků, takže standardní implementace Bucket Sort využívající vkládací řazení je považována za stabilní.

Bucket Sort seskupuje prvky podle rozsahu hodnot a třídí jednotlivé segmenty pomocí jiného algoritmu. Radix Sort seskupuje čísla číslici po číslici a interně používá řazení počítáním. Bucket Sort upřednostňuje rovnoměrně rozložené desetinné čárky; Radix Sort upřednostňuje celá čísla nebo řetězce s pevnou šířkou.

Časová složitost metody Bucket Sort v nejhorším případě je O(n²). K tomu dochází, když všechny vstupní prvky spadají do jedné kategorie, což nutí vnitřní řazení (obvykle vkládací řazení) chovat se kvadraticky. Rovnoměrné rozdělení tomuto scénáři zabrání.

Ano. Pro zpracování záporných hodnot je nutné najít minimum i maximum a poté vypočítat index segmentu pomocí funkce (element – minimum) / span. Tím se záporné hodnoty posunou do nezáporného indexového prostoru a standardní logika třídění segmentů pokračuje beze změny.

Platformy s umělou inteligencí, jako jsou VisuAlgo, Algorithm Visualizer a ChatGPT, generované krok za krokem tracPomáhají studentům vizualizovat Bucket Sort. Animují fáze rozptylu, řazení a shromažďování, což usnadňuje pochopení matematických výpočtů indexu v bucketech a logiky dělení.

Doporučovací systémy řízené umělou inteligencí analyzují velikost datové sady, rozložení hodnot a limity paměti, aby navrhly vhodný algoritmus. Pro rovnoměrně rozložené float čísla takové systémy upřednostňují Bucket Sort. Pro smíšené celočíselné rozsahy mohou místo toho doporučit quicksort nebo Radix Sort.

Algoritmus řazení segmentů (Java, Python, C/C++ Code Příklady)

Co je bucket Sort?

Přístup rozptylu a shromáždění

Jak funguje třídění kbelíků

Nepravý Code

Metoda 1: Algoritmus třídění segmentů pro plovoucí desetinnou čárku Numbers

Program třídění kbelíků v C/C++

Program třídění kbelíků v Python

Kbelík Seřadit Java

Metoda 2: Algoritmus třídění segmentu pro celočíselné prvky

Program třídění kbelíků v C/C++

Program třídění kbelíků v Python

Kbelík Seřadit Java

Výhody a nevýhody třídění pomocí kbelíků

Analýza složitosti třídění segmentů

Časová složitost třídění v bucketu

Prostorová složitost třídění lopatek

Nejčastější dotazy

Shrňte tento příspěvek takto:

Přihlaste se k odběru newsletteru

Co je bucket Sort?

Přístup rozptylu a shromáždění

Jak funguje třídění kbelíků

Nepravý Code

Metoda 1: Algoritmus třídění segmentů pro plovoucí desetinnou čárku Numbers

SOUVISEJÍCÍ ČLÁNKY

Program třídění kbelíků v C/C++

Program třídění kbelíků v Python

Kbelík Seřadit Java

Metoda 2: Algoritmus třídění segmentu pro celočíselné prvky

Program třídění kbelíků v C/C++

Program třídění kbelíků v Python

Kbelík Seřadit Java

Výhody a nevýhody třídění pomocí kbelíků

Analýza složitosti třídění segmentů

Časová složitost třídění v bucketu

Prostorová složitost třídění lopatek

Nejčastější dotazy

Shrňte tento příspěvek takto:

Přihlaste se k odběru newsletteru