| dbo:abstract |
Samplesort ist ein Sortieralgorithmus, der 1970 von W. D. Frazer und A. C. McKellar in der wissenschaftlichen Publikation Samplesort: A Sampling Approach to Minimal Storage Tree Sorting veröffentlicht wurde. Der Algorithmus arbeitet ähnlich wie Quicksort und verfolgt wie dieser das Teile-und-herrsche-Verfahren. Der Algorithmus teilt die Eingabesequenz in mehrere Teilsequenzen auf, die dann rekursiv sortiert werden. (de) Samplesort is a sorting algorithm that is a divide and conquer algorithm often used in parallel processing systems. Conventional divide and conquer sorting algorithms partitions the array into sub-intervals or buckets. The buckets are then sorted individually and then concatenated together. However, if the array is non-uniformly distributed, the performance of these sorting algorithms can be significantly throttled. Samplesort addresses this issue by selecting a sample of size s from the n-element sequence, and determining the range of the buckets by sorting the sample and choosing p−1 < s elements from the result. These elements (called splitters) then divide the array into p approximately equal-sized buckets. Samplesort is described in the 1970 paper, "Samplesort: A Sampling Approach to Minimal Storage Tree Sorting", by W. D. Frazer and A. C. McKellar. (en) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/Parallelersamplesort.svg?width=300 |
| dbo:wikiPageExternalLink |
http://citeseerx.ist.psu.edu/viewdoc/summary%3Fdoi=10.1.1.49.214 http://citeseer.ist.psu.edu/91922.html http://portal.acm.org/citation.cfm%3Fid=321600 https://doi.org/10.1007%2F3-540-60688-2_30 https://doi.org/10.1007%2FBF01931688 |
| dbo:wikiPageID |
22405006 (xsd:integer) |
| dbo:wikiPageLength |
21821 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1121170031 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Predication_(computer_architecture) dbr:Quicksort dbr:GPGPU dbr:Branch_misprediction dbr:Connection_Machine dbc:Sorting_algorithms dbr:Distributed_computing dbr:Flashsort dbr:Oversampling dbc:Distributed_algorithms dbr:Chernoff_bound dbr:Big_O_notation dbr:Divide_and_conquer_algorithm dbr:Bulk_synchronous_parallel dbr:Sorting_algorithm dbr:Loop_unrolling dbr:Sample_(statistics) dbr:Distributed_systems dbr:Multiprocessor dbr:Binary_search dbr:File:Animation.png dbr:File:Parallelersamplesort.svg |
| dbp:wikiPageUsesTemplate |
dbt:Citation_needed dbt:Math dbt:Mvar dbt:R dbt:Reflist dbt:Sorting |
| dct:subject |
dbc:Sorting_algorithms dbc:Distributed_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 |
Samplesort ist ein Sortieralgorithmus, der 1970 von W. D. Frazer und A. C. McKellar in der wissenschaftlichen Publikation Samplesort: A Sampling Approach to Minimal Storage Tree Sorting veröffentlicht wurde. Der Algorithmus arbeitet ähnlich wie Quicksort und verfolgt wie dieser das Teile-und-herrsche-Verfahren. Der Algorithmus teilt die Eingabesequenz in mehrere Teilsequenzen auf, die dann rekursiv sortiert werden. (de) Samplesort is a sorting algorithm that is a divide and conquer algorithm often used in parallel processing systems. Conventional divide and conquer sorting algorithms partitions the array into sub-intervals or buckets. The buckets are then sorted individually and then concatenated together. However, if the array is non-uniformly distributed, the performance of these sorting algorithms can be significantly throttled. Samplesort addresses this issue by selecting a sample of size s from the n-element sequence, and determining the range of the buckets by sorting the sample and choosing p−1 < s elements from the result. These elements (called splitters) then divide the array into p approximately equal-sized buckets. Samplesort is described in the 1970 paper, "Samplesort: A Sampling Approach to (en) |
| rdfs:label |
Samplesort (de) Samplesort (en) |
| owl:sameAs |
freebase:Samplesort yago-res:Samplesort wikidata:Samplesort dbpedia-de:Samplesort dbpedia-no:Samplesort https://global.dbpedia.org/id/kvn7 |
| prov:wasDerivedFrom |
wikipedia-en:Samplesort?oldid=1121170031&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/Animation.png wiki-commons:Special:FilePath/Parallelersamplesort.svg |
| foaf:isPrimaryTopicOf |
wikipedia-en:Samplesort |
| is dbo:wikiPageRedirects of |
dbr:Sample_sort |
| is dbo:wikiPageWikiLink of |
dbr:Proportion_extend_sort dbr:Quicksort dbr:List_of_algorithms dbr:Sorting_algorithm dbr:Sample_sort |
| is foaf:primaryTopic of |
wikipedia-en:Samplesort |
