| dbo:abstract |
Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised by Ken Batcher. The resulting sorting networks consist of comparators and have a delay of , where is the number of items to be sorted. A sorted sequence is a monotonically non-decreasing (or non-increasing) sequence. A bitonic sequence is a sequence with for some , or a circular shift of such a sequence. (en) El ordenamiento bitónico es un algoritmo paralelo de ordenamiento. También se usa como método de construcción de una red de ordenamiento. El algoritmo fue diseñado por . Las redes de ordenamiento resultantes consisten en comparadores y tienen un costo temporal de , donde es el número de elementos a ser ordenados. Una es una sucesión monótonamente no-decreciente (o no-creciente). Una sucesión bitónica es una sucesión con para algún , o un cambio circular de la misma. (es) Le tri bitonique ou tri par fusion bitonique est un algorithme parallèle de tri. Il est utilisé également comme méthode de construction de réseaux de tri. L'algorithme a été conçu par Ken Batcher en 1968. Les réseaux de tri obtenus consistent en comparateurs et ont un temps d'exécution en parallèle de , où est le nombre de données à trier. Ces réseaux sont parmi les réseaux de tri les plus efficaces. Une suite est triée quand elle est monotone (croissante ou décroissante). Une suite est bitonique quand elle est croissante puis décroissante, ou décroissante puis croissante, les deux au sens large. (fr) バイトニックマージソート（英語: Bitonic mergesort）または単にバイトニックソート（英語: Bitonic sort）とは、ソートの並列アルゴリズムの１つ。ソーティングネットワークの構築法としても知られている。 このアルゴリズムは（英語: Ken Batcher）によって考案されたもので、このソーティングネットワークの計算量は個の要素に対して、サイズ（コンパレータ数＝比較演算の回数）は、段数（並列実行不可能な数）はとなる。各段での比較演算（n/2回）は独立して実行できるため、並列化による高速化が容易である。 バイトニックソートでは、バイトニック列（英語: bitoniq sequence）を生成しながら並べ替えを実行する。このバイトニック列は、単調非増加の後に単調非減少となるかその逆である列のことである。つまり、k個目までは昇順でそれ以降は降順（つまり、に対して）もしくはその循環シフトされたものである。 (ja) Битонная сортировка (англ. Bitonic sorter) — параллельный алгоритм сортировки данных, метод для создания сортировочной сети. Разработан американским информатиком Кеннетом Бэтчером в 1968 году. В основе алгоритма лежит понятие «битонной последовательности». Название было выбрано по аналогии с монотонной последовательностью. Битонная сортировка — один из старейших параллельных алгоритмов сортировки. Наряду с , является одним из первых методов построения сортировочной сети для любого количества входов. (ru) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/Batcher_Bitonic_Mergesort_for_eight_inputs.svg?width=300 |
| dbo:wikiPageExternalLink |
https://www.inf.hs-flensburg.de/lang/algorithmen/sortieren/bitonic/oddn.htm https://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm https://xlinux.nist.gov/dads/HTML/bitonicSort.html |
| dbo:wikiPageID |
2713090 (xsd:integer) |
| dbo:wikiPageLength |
8067 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1123626548 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:NIST dbr:Batcher_odd–even_mergesort dbr:Parallel_algorithm dbr:Butterfly_network dbc:Sorting_algorithms dbr:Ken_Batcher dbr:Array_data_structure dbr:Sorting_algorithm dbr:Sorting_network dbr:Pairwise_sorting_network dbr:File:Batcher_Bitonic_Mergesort_for_eight_inputs.svg dbr:File:BitonicSort.svg dbr:File:BitonicSort1.svg |
| dbp:averageTime |
parallel time (en) |
| dbp:bestTime |
parallel time (en) |
| dbp:caption |
Bitonic sort network with eight inputs. (en) |
| dbp:class |
dbr:Sorting_algorithm |
| dbp:data |
dbr:Array_data_structure |
| dbp:optimal |
No (en) |
| dbp:space |
non-parallel time (en) |
| dbp:time |
parallel time (en) |
| dbp:wikiPageUsesTemplate |
dbt:Refimprove dbt:Short_description dbt:Infobox_Algorithm dbt:Sorting |
| dct:subject |
dbc:Sorting_algorithms |
| rdf:type |
yago:WikicatSortingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:SortingAlgorithm105847658 |
| rdfs:comment |
Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised by Ken Batcher. The resulting sorting networks consist of comparators and have a delay of , where is the number of items to be sorted. A sorted sequence is a monotonically non-decreasing (or non-increasing) sequence. A bitonic sequence is a sequence with for some , or a circular shift of such a sequence. (en) El ordenamiento bitónico es un algoritmo paralelo de ordenamiento. También se usa como método de construcción de una red de ordenamiento. El algoritmo fue diseñado por . Las redes de ordenamiento resultantes consisten en comparadores y tienen un costo temporal de , donde es el número de elementos a ser ordenados. Una es una sucesión monótonamente no-decreciente (o no-creciente). Una sucesión bitónica es una sucesión con para algún , o un cambio circular de la misma. (es) バイトニックマージソート（英語: Bitonic mergesort）または単にバイトニックソート（英語: Bitonic sort）とは、ソートの並列アルゴリズムの１つ。ソーティングネットワークの構築法としても知られている。 このアルゴリズムは（英語: Ken Batcher）によって考案されたもので、このソーティングネットワークの計算量は個の要素に対して、サイズ（コンパレータ数＝比較演算の回数）は、段数（並列実行不可能な数）はとなる。各段での比較演算（n/2回）は独立して実行できるため、並列化による高速化が容易である。 バイトニックソートでは、バイトニック列（英語: bitoniq sequence）を生成しながら並べ替えを実行する。このバイトニック列は、単調非増加の後に単調非減少となるかその逆である列のことである。つまり、k個目までは昇順でそれ以降は降順（つまり、に対して）もしくはその循環シフトされたものである。 (ja) Битонная сортировка (англ. Bitonic sorter) — параллельный алгоритм сортировки данных, метод для создания сортировочной сети. Разработан американским информатиком Кеннетом Бэтчером в 1968 году. В основе алгоритма лежит понятие «битонной последовательности». Название было выбрано по аналогии с монотонной последовательностью. Битонная сортировка — один из старейших параллельных алгоритмов сортировки. Наряду с , является одним из первых методов построения сортировочной сети для любого количества входов. (ru) Le tri bitonique ou tri par fusion bitonique est un algorithme parallèle de tri. Il est utilisé également comme méthode de construction de réseaux de tri. L'algorithme a été conçu par Ken Batcher en 1968. Les réseaux de tri obtenus consistent en comparateurs et ont un temps d'exécution en parallèle de , où est le nombre de données à trier. Ces réseaux sont parmi les réseaux de tri les plus efficaces. (fr) |
| rdfs:label |
Bitonic sorter (en) Ordenamiento bitónico (es) Tri bitonique (fr) バイトニックソート (ja) Битонная сортировка (ru) |
| owl:sameAs |
freebase:Bitonic sorter yago-res:Bitonic sorter wikidata:Bitonic sorter dbpedia-es:Bitonic sorter dbpedia-fa:Bitonic sorter dbpedia-fr:Bitonic sorter http://hi.dbpedia.org/resource/बिटोनिक_सॉर्टर http://hy.dbpedia.org/resource/Բիտոնիկ_տեսակավորող dbpedia-ja:Bitonic sorter dbpedia-ru:Bitonic sorter dbpedia-sr:Bitonic sorter dbpedia-th:Bitonic sorter https://global.dbpedia.org/id/4ZGfU |
| prov:wasDerivedFrom |
wikipedia-en:Bitonic_sorter?oldid=1123626548&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/Batcher_Bitonic_Mergesort_for_eight_inputs.svg wiki-commons:Special:FilePath/BitonicSort.svg wiki-commons:Special:FilePath/BitonicSort1.svg |
| foaf:isPrimaryTopicOf |
wikipedia-en:Bitonic_sorter |
| is dbo:wikiPageRedirects of |
dbr:Batcher's_sort dbr:Batcher_sort dbr:Bitonic_merge_sort dbr:Bitonic_mergesort dbr:Bitonic_sort dbr:Bitonic_sorting |
| is dbo:wikiPageWikiLink of |
dbr:List_of_algorithms dbr:Batcher_odd–even_mergesort dbr:Ken_Batcher dbr:Sorting_algorithm dbr:Sorting_network dbr:Integer_sorting dbr:Merge_algorithm dbr:Merge_sort dbr:Radix_sort dbr:Shellsort dbr:Batcher's_sort dbr:Batcher_sort dbr:Bitonic_merge_sort dbr:Bitonic_mergesort dbr:Bitonic_sort dbr:Bitonic_sorting |
| is foaf:primaryTopic of |
wikipedia-en:Bitonic_sorter |
