Bucketsort

Bucket sort ( bucket of engl. "Bucket ") is a sorting process, the input list sorted for certain values ​​distributions in linear time. The algorithm is divided in three phases:

The method therefore works out-of -place.

Algorithm

The input of bucket sort is a list of items and a function which maps each element of the list in the interval. The output is an ordered list, where the sort key calculated from an element. During the sorting of the Algorithm " buckets " which are arranged in an array is used. The distribution of the elements is done through this array, each of these elements is added to the -th bucket. Then one after the other, each bucket is sorted. In the last phase the bucket lists are in the same order as they are arranged in the array concatenated, which as a result is the sorted output.

In pseudocode:

Bucket_sort (l, f)     n = l.size     buckets = array (s)     foreach (s in l )       buckets [ floor ( f (s) * n) ]. add ( e)     r = []     foreach (b in buckets )       x = insertion_sort ( b )       r.append (x )     return r The algorithm sorts stable if the sorting algorithm used for sorting the buckets here insertion_sort is stable.

Complexity

The distribution of the values ​​of the function determines the running time of bucket sort. The term is ( O - notation ), the number of elements in th bucket respectively. In a uniform distribution, the total run time because the sum of the squares of the Bucketgrößen is linear. Intuitively, this is viewed directly since for an equal distribution of elements to buckets each bucket in the expected case contains a constant number of elements and thus a sort of complexity generated. The effective life of given not only to a uniform distribution, but in all distributions, after which the sum term is asymptotically linear.

For other values ​​of the duration of the distributions Bucketsortalgorithmus of the duration of the sorting algorithm is dominant, which is used for sorting of a bucket. Such a worst-case occurs when, for example, to be assigned to exactly one bucket all elements. When using insertion sort for sorting the buckets for the entire duration that this would do.

If the values ​​are distributed in accordance with each bucket sort of time call and all calls is the effective duration of a worst-case or average-case run-time.

The memory requirement is.