Bucket sort

13 Nov

Bucket sort, nebo také bin sort, je řadící algoritmus, který funguje na základě přihrádkovému řazení. Jednotlivé přihrádky jsou poté seřazeny za použití různých algoritmů.

Postup:

  1. Získá řadu čísel.
  2. Rozdělí daná čísla do jednotlivých přihrádek.
  3. Seřadí všechny využité přihrádky.

Postupně jde po přihrádkách a všechny elementy dá do původní řady.

Pseudokód:

function bucketSort(array, n) is
  buckets ← new array of n empty lists
  for i = 0 to (length(array)-1) do
    insert array[i] into buckets[msbits(array[i], k)]
  for i = 0 to n - 1 do
    nextSort(buckets[i])
  return the concatenation of buckets[0], ..., buckets[n-1]
__________________________________________________________________
array = řada, která má být seřazena
n = počet přihrádek k použití
funkce msbits(x,k) = vrátí k nejvýznamnější články x (floor(x/2^(size(x)-k)))

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: