This shows you the differences between two versions of the page.

— |
bucket_sort [2015/07/28 21:32] (current) will created |
||
---|---|---|---|

Line 1: | Line 1: | ||

+ | ====== Bucket sort ====== | ||

+ | Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm. The computational complexity estimates involve the number of buckets. | ||

+ | |||

+ | Bucket sort works as follows: | ||

+ | |||

+ | * Set up an array of initially empty "buckets". | ||

+ | * Scatter: Go over the original array, putting each object in its bucket. | ||

+ | * Sort each non-empty bucket. | ||

+ | * Gather: Visit the buckets in order and put all elements back into the original array. | ||

+ | |||

+ | [[https://en.wikipedia.org/wiki/Bucket_sort]] | ||

+ | |||

+ | [algorithm Bucket Sort] |

bucket_sort.txt ยท Last modified: 2015/07/28 21:32 by will