Szükséges előismeret: Függvények aszimptotikus viselkedése, Jelölések

Algoritmusok és adatszerkezetek 1. > Rendezések lineáris időben > Edényrendezés

Edényrendezés (Bucket sort)

Az edényrendezés nem helyben rendező algoritmus, amely $[0..1)$ közötti valós kulcsokkal dolgozik, annyi edénybe szétosztva őket, amennyi listaelem van. Ha szerencsénk van, akkor egyenletesen oszlanak el, és minden edényben csak egy elem lesz, ekkor lináris műveletigényű. Ha nem, akkor amiben több van, azt le kell rendezni valamilyen korábbról ismert rendezéssel. Végül a listák összefűzéséből előállítjuk a rendezett kimenetet.

Működése:

Az algoritmus először létrehoz annyi edényt (listát), ahány számot rendezni szeretnénk. Ezek az edények egy $B$ nevű tömbben tárolódnak. A számokat a $B[ \lfloor n \cdot k \rfloor ]$ képlet alapján helyezzük a megfelelő edénybe. Például ha a 0,78-at szeretnénk elhelyezni egy edényben és 10 darab számot rendezünk, akkor $\lfloor 10 \cdot 0,78 \rfloor = \lfloor 7,8 \rfloor = 7$. Tehát a 7-es indexen lévő edénybe kerül az elem. Viszont, ha mondjuk 11 számot kell rendeznünk, akkor $\lfloor 11 \cdot 0,78 \rfloor = \lfloor 8,58 \rfloor = 8$, tehát a 8-as indexen lévő edénybe kerül.

Az edényeket listák reprezentálják. Ha ezek a listák S1L-ek, akkor a lista elejére sokkal könnyebb beszúrni, mint a lista végére, ezért a lista elejére helyezzük az elemet. Ha ezek a listák C2L-ek, akkor a lista végére is szúrhatjuk az elemet (az animációban is a lista végére szúrjuk az elemeket).

Miután minden elemet elhelyeztünk egy edényben utána valamilyen korábbról ismert rendezéssel (merge sort) lerendezzük és ezeket a rendezett edényeket fűzzük össze.

Műveletigény:

$MT(n)$ a rendezéstől függ, amit használunk, beszúró rendezést használva $MT(n) \in \Theta(n^2)$, viszont összefésülő rendezést használva $MT(n) \in \Theta(n \cdot log \space n)$
$AT(n) \in \Theta (n)$
$mT(n) \in \Theta(n)$

Animáció

Struktogram

$BucketSort(L : list)$

$n :=$ the length of $L$
$B : list[n]$
	$j:= 0 \space to \space n-1$
	Let $B[j]$ be empty list
	$L \neq \emptyset$
	Remove the first element of list $L$
	Insert this element according to its key $k$ into list $B[ \lfloor n \cdot k \rfloor ]$
	$j := 0 \space to \space n-1$
	Sort list $B[j]$ nondecreasingly
Append lists $B[0], B[1], ... , B[n-1]$ in order into list $L$

Animáció

Struktogram

$BucketSort(L : list)$

$n :=$ the length of $L$
$B : list[n]$
	$j:= 0 \space to \space n-1$
	Let $B[j]$ be empty list
	$L \neq \emptyset$
	Remove the first element of list $L$
	Insert this element according to its key $k$ into list $B[ \lfloor n \cdot k \rfloor ]$
	$j := 0 \space to \space n-1$
	Sort list $B[j]$ nondecreasingly
Append lists $B[0], B[1], ... , B[n-1]$ in order into list $L$

Feladatok

Az alábbi feladatok a gyakorlatokon elvégzendő kötelező, illetve gyakorló feladatok.