Vödör rendezési algoritmus (Java, Python, C/C++ Code Példák)

Mi az a Bucket Sort?

A vödrös rendezés (Bucket Sort), amelyet gyakran bináris rendezésnek is neveznek, egy összehasonlításon alapuló eloszláson alapuló rendezési módszer, amely bemenetként egy rendezetlen tömböt fogad el, kimenetként pedig egy rendezett tömböt hoz létre. Ez a technika az elemeket több vödörbe osztja el, és minden egyes vödört egyenként rendez egy másik rendezési algoritmus, például a beszúrós rendezés segítségével. Ezután az összes vödör összevonásra kerül a végső rendezett tömb létrehozásához.

A vödörrendezést általában akkor használják, ha az elemek:

1. Lebegőpontos értékek
2. Egyenletesen oszlik el egy ismert tartományban

A vödörrendezés időbeli komplexitása a használt vödrök számától és a bemeneti eloszlás egyenletességétől függ. Míg más rendezési algoritmusok, mint például a shell fajta, Merge sort, Heapsort és gyorshajtás Ha a legjobb esetben O(n*logn időbonyolultságot ér el, a Bucket Rendezés algoritmus kedvező feltételek mellett O(n) lineáris időbonyolultságot is elérhet.

A vödörrendezés a szórás-gyűjtés módszerét követi. Az elemeket megfelelő vödrökbe szórjuk, az egyes vödrökön belül rendezzük, majd egy rendezett tömb létrehozásához gyűjtjük össze az utolsó lépésben. Ezt a szórás-gyűjtés módszert a következő szakasz tárgyalja.

Szétszóródásos-gyűjtési megközelítés

A nagyméretű, összetett problémák közvetlen megoldása időnként kihívást jelenthet. A szórásos-gyűjtéses megközelítés az ilyen problémákat úgy oldja meg, hogy a teljes adathalmazt klaszterekre osztja. Minden klasztert külön dolgoz fel, és az eredményeket összesítve kapjuk meg a végső választ.

Így valósítja meg a Bucket Sort algoritmus a szórás-gyűjtés módszert:

Hogyan működik a vödör rendezés

A Bucket Sort alapvető működési elve a következő:

1. Létrejön egy halmaz üres tárolókból. A kiválasztott szabályzattól függően a tárolók száma változhat.
2. A bemeneti tömb minden eleme a megfelelő vödörbe kerül.
3. Minden egyes vödör egyenként rendeződik egy másodlagos rendező algoritmus segítségével.
4. A rendezett vödröket összefűzzük egyetlen kimeneti tömb létrehozásához.

Pszeudo 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. módszer: Vödör szerinti rendezési algoritmus lebegőpontoshoz Numbers

A Bucket Rendezés algoritmusa a [0.0, 1.0] tartományon belüli lebegőpontos számokra:

Step 1) Hozz létre tíz (10) üres gyűjtőt. Az első gyűjtő a [0.0, 0.1] tartományba eső számokat tartalmazza. A második gyűjtő a [0.1, 0.2] tartományba eső számokat tartalmazza, és így tovább.

Step 2) Minden tömbelemhez:

• a. Számítsa ki a vödörindexet a következő képlettel:
  vödör_index = vödrök_száma * tömb_elem
• b. Helyezze be az elemet a vödörbe [vödör_index]

Step 3) Az egyes gyűjtőket külön-külön rendezze be a beillesztési rendezés segítségével.

Step 4) Összefűzi az összes tárolót egyetlen rendezett tömbbe.

Nézzünk végig egy vödörrendezési példát. Ebben a példában a következő tömböt fogjuk rendezni:

Step 1) Először 10 üres vödröt hozunk létre. Az első vödör a [0.0, 0.1] tartományban lévő számokat tartalmazza. A második vödör a [0.1, 0.2] tartományban lévő számokat tartalmazza, és így tovább.

Step 2) Minden tömbelemhez számítsd ki a vödörindexet, és helyezd el az elemet ebbe a vödörbe.

A vödörindexet a következő képlettel számítjuk ki:
        vödör_index = vödrök_száma * tömb_elem

Csoportindex számítása:
a) 0.78
      vödör_index = vödrök_száma * tömb_elem
              = 10 0.78 * XNUMX
              = 7.8
Így a 0.78-as elem a bucket[floor(7.8)] vagy a bucket[7] tárolóban található.

b) 0.17
      vödör_index = vödrök_száma * tömb_elem
              = 10 0.17 * XNUMX
              = 1.7

A 0.17 tömbelem a bucket[floor(1.7)] vagy a bucket[1] mappában található.

c) 0.39
      vödör_index = vödrök_száma * tömb_elem
              = 10 0.39 * XNUMX
              = 3.9
0.39 a vödör[floor(3.9)] vagy a vödör[3] értékben van tárolva.

Miután végigmentünk az összes tömbelemen, a vödrök a következőképpen néznek ki:

Step 3) Minden egyes vödör ezután beszúrásos rendezést használva rendeződik. A rendezési művelet után a kimenet a következő:

Step 4) Az utolsó lépésben a vödröket egyetlen tömbbé fűzzük össze. Ez a tömb a bemenet rendezett eredménye.

Minden egyes vödör összefűzésre kerül a kimeneti tömbbel. Például a második vödör elemeinek összefűzése:

Az utolsó vödörelemek összefűzése az alábbiakban látható:

Az összefűzés után a kapott tömb a kívánt rendezett tömb.

Vödör rendezés program C/C++

Bemenet:

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

output:

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

Vödör rendezési program be Python

Bemenet:

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

output:

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

Vödör Rendezés Java

Bemenet:

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

output:

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

2. módszer: Vödör rendezési algoritmus egész számú elemekhez

A [0.0, 1.0] tartományon kívüli számokat tartalmazó bemenetekre vonatkozó vödörrendezési algoritmus kissé eltér az előzőtől algoritmusAz ebben az esetben szükséges lépések a következők:

Step 1) Keresd meg a tömb maximális és minimális elemeit.

Step 2) Válassza ki a vödrök számát, n-et, és inicializálja őket üresként.

Step 3) Számítsa ki az egyes gyűjtőhelyek tartományát a következő képlet segítségével:
        span = (maximum - minimum) / n

Step 4) Minden tömbelemhez:

• 1. Számítsa ki a vödörindexet:
          bucket_index = (element - minimum) / span
• 2. Helyezze be az elemet a vödörbe[vödör_index]

Step 5) Rendezze az egyes gyűjtőket a beillesztési rendezés segítségével.

Step 6) Összefűzze az összes tárolót egyetlen tömbbe.

Nézzünk egy példát erre a Bucket Rendezési algoritmusra. Ebben a példában a következő tömböt fogjuk rendezni:

Step 1) Az első lépésben megkeressük az adott tömb maximális és minimális elemeit. Ebben a példában a maximum 24, a minimum pedig 1.

Step 2) Ezután kiválasztjuk az üres vödrök számát, n-et. Ebben a példában 5 vödröt használunk, és üresként inicializáljuk őket.

Step 3) Az egyes vödrök fesztávolságát a következő képlettel számítjuk ki:
        span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Tehát az első kosár a [0, 5] tartományon belüli számokat tartalmazza. A második kosár az [5, 10] tartományon belüli számokat tartalmazza, és így tovább.

Step 4) Minden tömbelemhez számítsd ki a vödörindexet, és helyezd el az elemet a vödörben. A vödörindex a következő képlettel számítható ki:
        bucket_index = (element - minimum) / span

Csoportindex számítása:

a) 11
bucket_index = (elem – minimum) / span
        = (11 – 1) / 4
        = 2

Így a 11-es elem a [2]-es vödörben található.

b) 9
bucket_index = (elem – minimum) / span
        = (9 – 1) / 4
        = 2

Jegyzet: Mivel a 9 a vödör[1] határoló eleme, ezért hozzáfűzésre kerül a vödör[1]-hez, ahelyett, hogy az előző elemmel azonos vödörbe kerülne.

Az egyes elemeken végrehajtott műveletek után a vödrök a következőképpen néznek ki:

Step 5) Most minden egyes vödör beszúrásos rendezéssel van rendezve. A vödrök a rendezés után:

Step 6) Az utolsó lépésben a vödröket egyetlen tömbbé fűzzük össze. Ez sor a bemenet rendezett eredménye.

Vödör rendezés program C/C++

Bemenet:

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

output:

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

Vödör rendezési program be Python

Bemenet:

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)

output:

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

Vödör Rendezés Java

Bemenet:

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

output:

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

A vödrös rendezés előnyei és hátrányai

Vödör rendezés összetettségének elemzése

Vödörrendezési idő összetettsége

• Legjobb eset összetettsége: Ha az összes tömbelem egyenletesen van elosztva és előre rendezve az egyes vödrökön belül, akkor O(n) időre van szükség az elemek megfelelő vödrökbe való szétszórásához. Ezután az egyes vödröket a következőképpen rendezzük: beszúrási rendezés A folyamat O(k)-ba kerül. Így az összbonyolultság O(n+k).
• Átlagos ügykomplexitás: Átlagos esetekben feltételezzük, hogy a bemenetek egyenletesen oszlanak el. Így a Bucket Rendezés algoritmus O(n+k) lineáris időkomplexitást ér el. Itt O(n) idő szükséges az elemek szétszórásához, és O(k) idő a beszúrós rendezés használatával történő rendezéshez.
• A legrosszabb eset összetettsége: A legrosszabb esetben az elemek nem egyenletesen oszlanak el, és egy vagy két vödörben koncentrálódnak. Ebben az esetben a vödörrendezés hasonló viselkedést mutat, mint egy buborékrendezési algoritmusTehát a legrosszabb esetben a vödörrendezés időbonyolultsága O(n²).

A vödör rendezés térbeli összetettsége

A vödrös rendezés (Bucket Sort) térbonyolultsága O(n*k). Itt n az elemek száma, k pedig a rendezés során azok tárolására szolgáló vödrök száma.

GYIK