翻訳と辞書
Words near each other
・ Sortie (album)
・ Sortie number
・ Sortie numbers
・ Sortilege
・ Sortilegio
・ Sortilin 1
・ Sortilège (band)
・ Sortilège (EP)
・ Sortimo
・ Sortindane Peaks
・ Sorting
・ Sorting (sediment)
・ Sorting algorithm
・ Sorting and assembly machinery
・ Sorting identity
Sorting network
・ Sorting nexin
・ Sorting office
・ Sortino
・ Sortino ratio
・ Sortir
・ Sortir du nucléaire
・ Sortir du nucléaire (Canada)
・ Sortir du nucléaire (France)
・ Sortition
・ Sortland
・ Sortland Bridge
・ Sortland Church
・ Sortlandssundet
・ Sortobe


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Sorting network : ウィキペディア英語版
Sorting network

In computer science, comparator networks are abstract devices built up of a fixed number of "wires", carrying values, and comparator modules that connect pairs of wires, swapping the values on the wires if they are not in a desired order. Such networks are typically designed to perform sorting on fixed numbers of values, in which case they are called sorting networks.
Sorting networks differ from general comparison sorts in that they are not capable of handling arbitrarily large inputs, and in that their sequence of comparisons is set in advance, regardless of the outcome of previous comparisons. This independence of comparison sequences is useful for parallel execution and for implementation in hardware. Despite the simplicity of sorting nets, their theory is surprisingly deep and complex. Sorting networks were first studied circa 1954 by Armstrong, Nelson and O'Connor,〔 who subsequently patented the idea.
Sorting networks can be implemented either in hardware or in software. Donald Knuth describes how the comparators for binary integers can be implemented as simple, three-state electronic devices.〔 Batcher, in 1968, suggested using them to construct switching networks for computer hardware, replacing both buses and the faster, but more expensive, crossbar switches. Since the 2000s, sorting nets (especially bitonic mergesort) are used by the GPGPU community for constructing sorting algorithms to run on graphics processing units.
==Introduction==

A sorting network consists of two types of items: comparators and wires. The wires are thought of as running from left to right, carrying values (one per wire) that traverse the network all at the same time. Each comparator connects two wires. When a pair of values, traveling through a pair of wires, encounter a comparator, the comparator swaps the values if and only if the top wire's value is greater than the bottom wire's value.
In a formula, if the top wire carries and the bottom wire carries , then after hitting a comparator the wires carry x' = \min(x, y) and y' = \max(x, y), respectively, so the pair of values is sorted. A network of wires and comparators that will correctly sort all possible inputs into ascending order is called a sorting network.
The full operation of a simple sorting network is shown below. It is easy to see why this sorting network will correctly sort the inputs; note that the first four comparators will "sink" the largest value to the bottom and "float" the smallest value to the top. The final comparator simply sorts out the middle two wires.
650px

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Sorting network」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.