User:Earlster/Sandbox: Difference between revisions
←Created page with '{{Infobox Algorithm |class=Sorting algorithm |image= |data=Array |time= |space= |optimal= O(''n'') }} [[Image:Bucket sort 1.png|right|...' |
No edit summary |
||
Line 10: | Line 10: | ||
[[Image:Bucket sort 1.png|right|frame|Elements are distributed among bins]] |
[[Image:Bucket sort 1.png|right|frame|Elements are distributed among bins]] |
||
[[Image:Bucket sort 2.png|right|frame|Then, elements are sorted within each bin]] |
[[Image:Bucket sort 2.png|right|frame|Then, elements are sorted within each bin]] |
||
'''Proxmap Sort''', or '''Proxmap''', is a [[sorting algorithm]] that works by partitioning an [[Array data structure|array]] into a number of [[bucket (computing)|bucket]]s. Each bucket is then sorted individually |
'''Proxmap Sort''', or '''Proxmap''', is a [[sorting algorithm]] that works by partitioning an [[Array data structure|array]] into a number of [[bucket (computing)|bucket]]s. Each bucket is then sorted individually by [[insertion sort]]. Since bucket sort is not a [[comparison sort]], the Ω(''n'' log ''n'') lower bound is inapplicable. The [[computational complexity]] estimates involve the number of buckets. |
||
Bucket sort works as follows: |
Bucket sort works as follows: |
||
# Set up an array of initially empty "buckets." |
# Set up an array of initially empty "buckets." |
||
# '''Scatter''': Go over the original array, putting each object in its bucket. |
# '''Scatter''': Go over the original array, putting each object in its bucket. |
||
# Sort each non-empty bucket. |
# [[Insertion Sort]] each non-empty bucket. |
||
# '''Gather''': Visit the buckets in order and put all elements back into the original array. |
# '''Gather''': Visit the buckets in order and put all elements back into the original array. |
||
==Pseudocode== |
==Pseudocode== |
||
'''function''' |
'''function''' proxmap-sort(array, n) '''is''' |
||
buckets ← new array of n empty lists |
buckets ← new array of n empty lists |
||
'''for''' i = 0 '''to''' (length(array)-1) '''do''' |
'''for''' i = 0 '''to''' (length(array)-1) '''do''' |
||
Line 45: | Line 45: | ||
<references /> |
<references /> |
||
* Thomas A. Standish [http://delivery.acm.org/10.1145/1120000/1113874/p41-standish.pdf?key1=1113874&key2=5601886821&coll=GUIDE&dl=GUIDE&CFID=105420888&CFTOKEN=23673255 "Using O(n) ProxmapSort and O(1) ProxmapSearch to Motivate CS2 Students (Part I)"] from [[Donald Bren School of Information and Computer Sciences]] at [[University_of_California,_Irvine|UC Irvine]]. |
|||
* Paul E. Black [http://www.nist.gov/dads/HTML/postmansort.html "Postman's Sort"] from [[Dictionary of Algorithms and Data Structures]] at [[National Institute of Standards and Technology|NIST]]. |
|||
* Norman Jacobson [http://www.ics.uci.edu/~jacobson/ics23/ProxmapHandout.pdf "A Synopsis of ProxmapSort & ProxmapSearch"] from [[Donald Bren School of Information and Computer Sciences]] at [[University_of_California,_Irvine|UC Irvine]]. |
|||
* Robert Ramey [http://www.rrsd.com/software_development/postmans_sort/cuj/cuj.htm '"The Postman's Sort"] ''C Users Journal'' Aug. 1992 |
|||
* [http://www.nist.gov/dads/HTML/bucketsort.html NIST's Dictionary of Algorithms and Data Structures: bucket sort] |
|||
== External links== |
== External links== |
||
* |
* http://www.cs.uah.edu/~rcoleman/CS221/Sorting/ProxMapSort.html |
||
{{sorting}} |
{{sorting}} |
Revision as of 11:32, 12 October 2010
Class | Sorting algorithm |
---|---|
Data structure | Array |
Optimal | O(n) |
![](http://upload.wikimedia.org/wikipedia/commons/6/61/Bucket_sort_1.png)
![](http://upload.wikimedia.org/wikipedia/commons/3/39/Bucket_sort_2.png)
Proxmap Sort, or Proxmap, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually by insertion sort. Since bucket sort is not a comparison sort, the Ω(n log n) lower bound is inapplicable. 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.
- Insertion Sort each non-empty bucket.
- Gather: Visit the buckets in order and put all elements back into the original array.
Pseudocode
function proxmap-sort(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 next-sort(buckets[i]) return the concatenation of buckets[0], ..., buckets[n-1]
Here array is the array to be sorted and n is the number of buckets to use. The function msbits(x,k) returns the k most significant bits of x (floor(x/2^(size(x)-k))); different functions can be used to translate the range of elements in array to n buckets, such as translating the letters A–Z to 0–25 or returning the first character (0–255) for sorting strings. The function next-sort is a sorting function; using bucket-sort itself as next-sort produces a relative of radix sort; in particular, the case n = 2 corresponds to quicksort (although potentially with poor pivot choices).
Optimizations
A common optimization is to put the elements back in the original array first, then run insertion sort over the complete array; because insertion sort's runtime is based on how far each element is from its final position, the number of comparisons remains relatively small, and the memory hierarchy is better exploited by storing the list contiguously in memory.[1]
Variants
Generic bucket sort
The most common variant of bucket sort operates on a list of n numeric inputs between zero and some maximum value M and divides the value range into n buckets each of size M/n. If each bucket is sorted using insertion sort, the sort can be shown to run in expected linear time (where the average is taken over all possible inputs).[2] However, the performance of this sort degrades with clustering; if many values occur close together, they will all fall into a single bucket and be sorted slowly.
Comparison with other sorting algorithms
References
- ^ Corwin, E. and Logar, A. "Sorting in linear time — variations on the bucket sort". Journal of Computing Sciences in Colleges, 20, 1, pp.197–202. October 2004.
- ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.4: Bucket sort, pp.174–177.
- Thomas A. Standish "Using O(n) ProxmapSort and O(1) ProxmapSearch to Motivate CS2 Students (Part I)" from Donald Bren School of Information and Computer Sciences at UC Irvine.
- Norman Jacobson "A Synopsis of ProxmapSort & ProxmapSearch" from Donald Bren School of Information and Computer Sciences at UC Irvine.
External links