Sorting network (original) (raw)

About DBpedia

ソーティングネットワーク（英: sorting network）とは、ワイヤとコンパレータからなる、数列をソートするネットワーク（抽象的な数理モデル）である。一つのコンパレータが二つのワイヤを繋ぎ、小さい方の値を一方に、大きい方の値を他方に出力する。これによって値のソートが行われる。比較ソートアルゴリズムとソーティングネットワークの主な違いは、比較の順序が、それまでの比較の結果によらずあらかじめ決まっていることである。このため、アルゴリズムを並列に実行することが容易である。モデルは単純だが、ソーティングネットワークの理論は非常に深く、複雑である。

thumbnail

Property Value
dbo:abstract En ciencias de la computación, una red de ordenamiento (en inglés, sorting network) es un algoritmo que ordena un número fijo de valores mediante el uso de una secuencia fija de comparaciones. Esta puede ser imaginada como una red de hilos y módulos comparadores. Los valores (de cualquier tipo ordenable) fluyen a través de los hilos (no se debe confundir con hilo de ejecución). Cada comparador conecta dos hilos, compara los valores introducidos por los hilos, y los ordena obteniendo el menor como salida a un hilo, y el mayor a otro. Las redes de ordenamiento se diferencian del más general en el hecho de que no son capaces de manejar cantidades arbitrariamente grandes de entrada, y que su secuencia de comparaciones se conoce de antemano, independientemente del resultado de las comparaciones previas. Esta independencia de la secuencia de comparaciones es útil para la ejecución paralela y para su implementación en hardware. A pesar de la simplicidad de las redes de ordenamiento, su teoría es sorprendentemente profunda y compleja. Las redes de ordenamiento fueron primero estudiadas circa 1954 por Armstrong, Nelson y O'Connor,​ quienes subsecuentemente patentaron la idea.​ Las redes de ordenamiento pueden ser implementadas tanto en hardware como en software. Donald Knuth describe como los comparadores para los enteros binarios pueden ser implementados como sencillos dispositivos electrónicos de tres estados.​ , en 1968, sugirió usarlos para construir redes de interruptores para hardware de computadora, reemplazando a ambos: los buses de computadora y el más rápido pero más caro conmutador de barras cruzadas.​ Desde la década del 2000, las redes de ordenamiento (especialmente del ordenamiento bitónico) son usadas por la comunidad GPGPU para construir algoritmos de ordenamiento para correr en unidades de procesamiento gráfico.​ (es) En Informatique, un réseau de tri est un algorithme de tri qui trie un nombre fixe de valeurs en utilisant une suite fixe de comparateurs. On peut voir un réseau de tri comme un réseau composé de fils et de comparateurs. Les valeurs, prises dans un ensemble ordonné, circulent le long des fils. Chaque comparateur connecte deux fils, compare les données qui entrent par les fils et les trie, sortant la plus petite donnée sur l'un des fils, la plus grande sur l’autre. Les réseaux de tri diffèrent des algorithmes de tri par comparaison dans le sens où ils ne sont pas capables de traiter un nombre arbitraire d'entrées ; de plus, leur séquence de comparaisons est définie à l'avance, et indépendante du résultat des comparaisons précédentes. L'indépendance des séquences de comparaison est utile pour l'exécution en parallèle et pour la réalisation en hardware. Elle peut aussi être vue comme une protection contre un logiciel malveillant qui chercherait à examiner la nature des séquences triées. (fr) 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. In order to sort larger amounts of inputs, new sorting networks must be constructed. 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. (en) ソーティングネットワーク（英: sorting network）とは、ワイヤとコンパレータからなる、数列をソートするネットワーク（抽象的な数理モデル）である。一つのコンパレータが二つのワイヤを繋ぎ、小さい方の値を一方に、大きい方の値を他方に出力する。これによって値のソートが行われる。比較ソートアルゴリズムとソーティングネットワークの主な違いは、比較の順序が、それまでの比較の結果によらずあらかじめ決まっていることである。このため、アルゴリズムを並列に実行することが容易である。モデルは単純だが、ソーティングネットワークの理論は非常に深く、複雑である。 (ja) Sieć sortująca to abstrakcyjny, matematyczny model sieci, składającej się z przewodów i modułów porównujących (komparatorów), używanej do sortowania sekwencji liczb. Każdy moduł porównujący łączy dwa przewody i sortuje dwie wartości, wyprowadzając mniejszą na jeden przewód i większą na drugi. Pomimo prostoty modelu, teoria sieci sortujących jest zaskakująco głęboka i złożona. (pl) Сеть сортиро́вки (англ. sorting network) — класс алгоритмических методов сортировки, в которых последовательность сравнений не зависит от результатов предыдущих сравнений. Часто изображаются в виде сети, горизонтальные линии в которой соответствуют передаче сортируемого элемента слева направо, а вертикальными соединениями пар линий обозначены так называемые «модули компараторов», имеющие два входа и два выхода. Модуль компаратора производит сравнение элементов на входе и обменивает их местами таким образом, чтобы на нижнем выходе было, например, большее число. Сети сортировки допускают эффективную аппаратную реализацию. (ru)
dbo:thumbnail wiki-commons:Special:FilePath/SimpleSortingNetwork2.svg?width=300
dbo:wikiPageExternalLink http://optimizacion.cic.ipn.mx/sortingnetworks/ https://bertdobbelaere.github.io/sorting_networks.html https://web.archive.org/web/20080116050552/http:/www.cs.uky.edu/~lewis/essays/algorithms/sortnets/sort-net.html http://www.cs.brandeis.edu/~hugues/sorting_networks.html http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/sortieren.htm http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap28.htm https://metacpan.org/pod/Algorithm::Networksort http://rjlipton.wordpress.com/2014/04/24/galactic-sortning-networks/
dbo:wikiPageID 562061 (xsd:integer)
dbo:wikiPageLength 21208 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1117587967 (xsd:integer)
dbo:wikiPageWikiLink dbr:Robert_W._Floyd dbr:Monotonic_function dbr:Shell_sort dbr:Big-O_notation dbr:Insertion_sort dbr:Mathematical_induction dbr:General-purpose_computing_on_graphics_processing_units dbr:Co-NP dbr:Endre_Szemerédi dbr:Genetic_algorithm dbr:Contraposition dbr:Crossbar_switch dbr:Batcher_odd–even_mergesort dbr:Comparison_sort dbr:Computer_hardware dbr:Computer_science dbr:Parallel_computing dbr:Switch dbr:Michael_T._Goodrich dbr:Bubble_sort dbc:Sorting_algorithms dbr:János_Komlós_(mathematician) dbr:Expander_graph dbr:Graphics_processing_unit dbr:Ken_Batcher dbr:Lemma_(mathematics) dbc:Computer_engineering dbr:Advances_in_Mathematics dbr:Bitonic_sorter dbr:Divide_and_conquer_algorithm dbr:Donald_Knuth dbr:Bus_(computing) dbr:Sorting_algorithm dbr:If_and_only_if dbr:Miklós_Ajtai dbr:Random-access_machine dbr:Software dbr:The_Art_of_Computer_Programming dbr:Pairwise_sorting_network dbr:P_vs_NP dbr:Bitonic_sort dbr:Michael_S._Paterson dbr:File:Recursive-bubble-sorting-network.svg dbr:File:Recursive-insertion-sorting-network.svg dbr:File:SimpleSortingNetwork2.svg dbr:File:SimpleSortingNetworkFullOperation.svg dbr:File:Six-wire-bubble-sorting-network.svg dbr:File:Six-wire-insertion-sorting-network.svg dbr:File:Six-wire-pyramid-sorting-network.svg dbr:File:Sorting-network-comparator-demonstration.svg
dbp:wikiPageUsesTemplate dbt:= dbt:Cite_journal dbt:Cite_web dbt:Math dbt:Mvar dbt:Reflist dbt:Rp dbt:Sorting
dcterms:subject dbc:Sorting_algorithms dbc:Computer_engineering
gold:hypernym dbr:Devices
rdf:type yago:WikicatSortingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity dbo:Device yago:Rule105846932 yago:SortingAlgorithm105847658
rdfs:comment ソーティングネットワーク（英: sorting network）とは、ワイヤとコンパレータからなる、数列をソートするネットワーク（抽象的な数理モデル）である。一つのコンパレータが二つのワイヤを繋ぎ、小さい方の値を一方に、大きい方の値を他方に出力する。これによって値のソートが行われる。比較ソートアルゴリズムとソーティングネットワークの主な違いは、比較の順序が、それまでの比較の結果によらずあらかじめ決まっていることである。このため、アルゴリズムを並列に実行することが容易である。モデルは単純だが、ソーティングネットワークの理論は非常に深く、複雑である。 (ja) Sieć sortująca to abstrakcyjny, matematyczny model sieci, składającej się z przewodów i modułów porównujących (komparatorów), używanej do sortowania sekwencji liczb. Każdy moduł porównujący łączy dwa przewody i sortuje dwie wartości, wyprowadzając mniejszą na jeden przewód i większą na drugi. Pomimo prostoty modelu, teoria sieci sortujących jest zaskakująco głęboka i złożona. (pl) Сеть сортиро́вки (англ. sorting network) — класс алгоритмических методов сортировки, в которых последовательность сравнений не зависит от результатов предыдущих сравнений. Часто изображаются в виде сети, горизонтальные линии в которой соответствуют передаче сортируемого элемента слева направо, а вертикальными соединениями пар линий обозначены так называемые «модули компараторов», имеющие два входа и два выхода. Модуль компаратора производит сравнение элементов на входе и обменивает их местами таким образом, чтобы на нижнем выходе было, например, большее число. Сети сортировки допускают эффективную аппаратную реализацию. (ru) En ciencias de la computación, una red de ordenamiento (en inglés, sorting network) es un algoritmo que ordena un número fijo de valores mediante el uso de una secuencia fija de comparaciones. Esta puede ser imaginada como una red de hilos y módulos comparadores. Los valores (de cualquier tipo ordenable) fluyen a través de los hilos (no se debe confundir con hilo de ejecución). Cada comparador conecta dos hilos, compara los valores introducidos por los hilos, y los ordena obteniendo el menor como salida a un hilo, y el mayor a otro. (es) 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. (en) En Informatique, un réseau de tri est un algorithme de tri qui trie un nombre fixe de valeurs en utilisant une suite fixe de comparateurs. On peut voir un réseau de tri comme un réseau composé de fils et de comparateurs. Les valeurs, prises dans un ensemble ordonné, circulent le long des fils. Chaque comparateur connecte deux fils, compare les données qui entrent par les fils et les trie, sortant la plus petite donnée sur l'un des fils, la plus grande sur l’autre. (fr)
rdfs:label Red de ordenamiento (es) Réseau de tri (fr) ソーティングネットワーク (ja) Sieć sortująca (pl) Sorting network (en) Сеть сортировки (ru)
owl:sameAs freebase:Sorting network yago-res:Sorting network wikidata:Sorting network dbpedia-da:Sorting network dbpedia-es:Sorting network dbpedia-fa:Sorting network dbpedia-fr:Sorting network dbpedia-he:Sorting network dbpedia-ja:Sorting network dbpedia-pl:Sorting network dbpedia-ru:Sorting network dbpedia-sr:Sorting network https://global.dbpedia.org/id/4pwRK
prov:wasDerivedFrom wikipedia-en:Sorting_network?oldid=1117587967&ns=0
foaf:depiction wiki-commons:Special:FilePath/Recursive-bubble-sorting-network.svg wiki-commons:Special:FilePath/Recursive-insertion-sorting-network.svg wiki-commons:Special:FilePath/SimpleSortingNetwork2.svg wiki-commons:Special:FilePath/SimpleSortingNetworkFullOperation.svg wiki-commons:Special:FilePath/Six-wire-bubble-sorting-network.svg wiki-commons:Special:FilePath/Six-wire-insertion-sorting-network.svg wiki-commons:Special:FilePath/Six-wire-pyramid-sorting-network.svg wiki-commons:Special:FilePath/Sorting-network-comparator-demonstration.svg
foaf:isPrimaryTopicOf wikipedia-en:Sorting_network
is dbo:wikiPageRedirects of dbr:Sort_network dbr:Sorting_net dbr:Sorting_networks dbr:AKS_network dbr:AKS_sorting_network dbr:Ajtai-Komlós-Szemerédi_sorting_network dbr:Comparison_network
is dbo:wikiPageWikiLink of dbr:Elementary_Number_Theory,_Group_Theory_and_Ramanujan_Graphs dbr:List_of_genetic_algorithm_applications dbr:Permutation dbr:Vaughan_Pratt dbr:List_of_network_theory_topics dbr:List_of_permutation_topics dbr:Optimal_sorting dbr:Endre_Szemerédi dbr:Batcher_odd–even_mergesort dbr:Comparator dbr:Majority_function dbr:Prefix_sum dbr:Distributed_computing dbr:János_Komlós_(mathematician) dbr:Expander_graph dbr:Parametric_search dbr:Digital_comparator dbr:Bitonic_sorter dbr:CC_(complexity) dbr:CC_system dbr:Sorting_algorithm dbr:Aks dbr:Merge_sort dbr:Michael_Fellows dbr:Miklós_Ajtai dbr:Radix_sort dbr:Shellsort dbr:Pairwise_sorting_network dbr:Sort_network dbr:Sorting_net dbr:Sorting_networks dbr:AKS_network dbr:AKS_sorting_network dbr:Ajtai-Komlós-Szemerédi_sorting_network dbr:Comparison_network
is foaf:primaryTopic of wikipedia-en:Sorting_network