|
Samplesort is a sorting algorithm that is a divide and conquer algorithm often used in parallel processing systems.〔(【引用サイトリンク】title=Samplesort using the Standard Template Adaptive Parallel Library )〕 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 m -1 elements from the result. These elements (called splitters) then divide the sample into m 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. == Algorithm == Samplesort can be thought of as a refined quicksort. Where quicksort partitions its input into two parts at each step, based on a single value called the pivot, samplesort instead takes a larger sample from its input and divides its data into buckets accordingly. Like quicksort, it then recursively sorts the buckets. To devise a samplesort implementation, one needs to decide on the number of buckets . When this is done, the actual algorithm operates in three phases: # Sample elements from the input (the ''splitters''). Sort these; each pair of adjacent splitters then defines a ''bucket''. # Loop over the data, placing each element in the appropriate bucket. (This may mean: send it to a processor, in a multiprocessor system.) # Sort each of the buckets. The full sorted output is the concatenation of the buckets. A common strategy is to set equal to the number of processors available. The data is then distributed among the processors, which perform the sorting of buckets using some other, sequential, sorting algorithm. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Samplesort」の詳細全文を読む スポンサード リンク
|