Spreadsort (original) (raw)
Spreadsort is a sorting algorithm invented by Steven J. Ross in 2002. It combines concepts from distribution-based sorts, such as radix sort and bucket sort, with partitioning concepts from comparison sorts such as quicksort and mergesort. In experimental results it was shown to be highly efficient, often outperforming traditional algorithms such as quicksort, particularly on distributions exhibiting structure and string sorting. There is an open-source implementation with performance analysis and benchmarks, and HTML documentation.
| Property | Value |
|---|---|
| dbo:abstract | Spreadsort is a sorting algorithm invented by Steven J. Ross in 2002. It combines concepts from distribution-based sorts, such as radix sort and bucket sort, with partitioning concepts from comparison sorts such as quicksort and mergesort. In experimental results it was shown to be highly efficient, often outperforming traditional algorithms such as quicksort, particularly on distributions exhibiting structure and string sorting. There is an open-source implementation with performance analysis and benchmarks, and HTML documentation. Quicksort identifies a pivot element in the list and then partitions the list into two sublists, those elements less than the pivot and those greater than the pivot. Spreadsort generalizes this idea by partitioning the list into n/c partitions at each step, where n is the total number of elements in the list and c is a small constant (in practice usually between 4 and 8 when comparisons are slow, or much larger in situations where they are fast). It uses distribution-based techniques to accomplish this, first locating the minimum and maximum value in the list, and then dividing the region between them into n/c equal-sized bins.Where caching is an issue, it can help to have a maximum number of bins in each recursive division step, causing this division process to take multiple steps. Though this causes more iterations, it reduces cache misses and can make the algorithm run faster overall. In the case where the number of bins is at least the number of elements, spreadsort degenerates to bucket sort and the sort completes. Otherwise, each bin is sorted recursively. The algorithm uses heuristic tests to determine whether each bin would be more efficiently sorted by spreadsort or some other classical sort algorithm, then recursively sorts the bin. Like other distribution-based sorts, spreadsort has the weakness that the programmer is required to provide a means of converting each element into a numeric key, for the purpose of identifying which bin it falls in. Although it is possible to do this for arbitrary-length elements such as strings by considering each element to be followed by an infinite number of minimum values, and indeed for any datatype possessing a total order, this can be more difficult to implement correctly than a simple comparison function, especially on complex structures. Poor implementation of this value function can result in clustering that harms the algorithm's relative performance. (en) |
| dbo:wikiPageExternalLink | http://www.boostpro.com/vault/index.php%3Faction=downloadfile&filename=algorithm_sorting.zip&directory=& |
| dbo:wikiPageID | 7794578 (xsd:integer) |
| dbo:wikiPageLength | 11279 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1000481336 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quicksort dbr:Riemann_integrable dbr:Introsort dbc:Sorting_algorithms dbr:Total_order dbr:Flashsort dbr:Probability_density_function dbr:Sorting_algorithm dbr:Mergesort dbr:Bucket_sort dbr:Radix_sort |
| dbp:wikiPageUsesTemplate | dbt:COI dbt:Essay-like dbt:Multiple_issues dbt:Primary_sources dbt:Sqrt dbt:Sorting |
| dct:subject | dbc:Sorting_algorithms |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatSortingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:SortingAlgorithm105847658 |
| rdfs:comment | Spreadsort is a sorting algorithm invented by Steven J. Ross in 2002. It combines concepts from distribution-based sorts, such as radix sort and bucket sort, with partitioning concepts from comparison sorts such as quicksort and mergesort. In experimental results it was shown to be highly efficient, often outperforming traditional algorithms such as quicksort, particularly on distributions exhibiting structure and string sorting. There is an open-source implementation with performance analysis and benchmarks, and HTML documentation. (en) |
| rdfs:label | Spreadsort (en) |
| owl:sameAs | freebase:Spreadsort yago-res:Spreadsort wikidata:Spreadsort dbpedia-fa:Spreadsort dbpedia-sr:Spreadsort https://global.dbpedia.org/id/4vpH4 |
| prov:wasDerivedFrom | wikipedia-en:Spreadsort?oldid=1000481336&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Spreadsort |
| is dbo:wikiPageWikiLink of | dbr:Sorting_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Spreadsort |