Üdvözlöm, Ön a
bucket sort szó jelentését keresi. A DICTIOUS-ban nem csak a
bucket sort szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a
bucket sort szót egyes és többes számban mondani. Minden, amit a
bucket sort szóról tudni kell, itt található. A
bucket sort szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A
bucket sort és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.
Főnév
bucket sort (tsz. bucket sorts)
- (informatika) Bucket sort egy hatékony, nem összehasonlító rendezési algoritmus, amely főleg valós számok (floatok, decimálisak) rendezésére alkalmas, ha azok nagyjából egyenletesen oszlanak el egy adott intervallumban. Az eljárás a teljes elemtömeget kisebb “vödrökbe” (bucketekbe) szortírozza, majd ezeket a vödröket külön-külön rendezi, végül összefűzi az eredményeket.
🪣 Hogyan működik a bucket sort?
1. Intervallum felosztása
- A bemeneti adathalmaz teljes tartományát (például [0, 1)) k darab vödörre osztjuk fel.
- Minden vödör egy adott értéktartományt fed le.
2. Szétosztás a vödrökbe
- Minden elemet egy olyan vödörbe helyezünk, amelynek intervallumába tartozik (pl. ha 0–1 között vannak, akkor 0.2-nkénti vödör).
- Példa: az 0.13 a 0.1–0.2 közötti vödörbe, az 0.85 a 0.8–0.9 közötti vödörbe kerül.
3. Vödrökön belüli rendezés
- Minden vödröt külön-külön rendezünk – jellemzően insertion sorttal vagy más egyszerű, hatékony algoritmussal, mivel kevés elemet tartalmaznak.
4. Összefűzés
- A vödröket sorban összefűzzük, így kapjuk a rendezett listát.
⚡ Működési elv (lépésről lépésre)
Tegyük fel, hogy 10 float számunk van [0, 1) intervallumban:
Lépések:
- 5 vödör: [0,0.2), [0.2,0.4), [0.4,0.6), [0.6,0.8), [0.8,1.0)
- Mindegyik szám a megfelelő vödörbe kerül:
- az első vödörbe, a másodikba stb.
- Minden vödröt megrendezünk külön.
- Az összefűzött eredmény a teljes rendezett sorozat.
💻 Egyszerű Python példa
def bucket_sort(arr):
n = len(arr)
buckets = for _ in range(n)] # n vödör
for val in arr:
idx = int(val * n) # bucket index (feltételezve, hogy [0,1) intervallumban)
buckets.append(val)
# Minden vödör rendezése és összefűzés
sorted_arr =
for bucket in buckets:
sorted_arr.extend(sorted(bucket))
return sorted_arr
# Teszt
A =
print(bucket_sort(A))
📈 Időbonyolultság
- Átlagos eset: O(n) Ha az adatok egyenletesen oszlanak el, és megfelelő a vödörszám.
- Legrosszabb eset: O(n²) Ha minden elem ugyanabba a vödörbe kerül, ekkor egy lassabb belső rendezés történik.
📝 Jellemzők, alkalmazási területek
- Nem összehasonlító algoritmus – különösen hatékony, ha az eloszlás ismert.
- Gyorsan működik lebegőpontos (float/double) értékekre egyenletes eloszlás esetén.
- Használható például nagy adathalmazok gyors rendezésére, statisztikai adatok feldolgozására.
- Nem stabil, de könnyen stabilizálható, ha a belső rendezés stabil.
Összefoglalás (TL;DR)
- Bucket sort: az elemeket több vödörbe sorolja, azokat külön rendezi, majd összefűzi.
- Átlagban nagyon gyors, ha az adatok jól eloszlanak.
- Nem általános célú: főleg lebegőpontos számokra használják, ismert intervallum és eloszlás esetén.