Bucket sort (original) (raw)
Přihrádkové řazení (anglicky bucket sort) je stabilní řadicí algoritmus. Algoritmus rozděluje vstupní data na několik částí (přihrádek, anglicky bucketů). Tyto části jsou následně seřazeny.
| Property | Value |
|---|---|
| dbo:abstract | Přihrádkové řazení (anglicky bucket sort) je stabilní řadicí algoritmus. Algoritmus rozděluje vstupní data na několik částí (přihrádek, anglicky bucketů). Tyto části jsou následně seřazeny. (cs) Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, a generalization of pigeonhole sort that allows multiple keys per bucket, and is a cousin of radix sort in the most-to-least significant digit flavor. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm. The computational complexity depends on the algorithm used to sort each bucket, the number of buckets to use, and whether the input is uniformly distributed. Bucket sort works as follows: 1. * Set up an array of initially empty "buckets". 2. * Scatter: Go over the original array, putting each object in its bucket. 3. * Sort each non-empty bucket. 4. * Gather: Visit the buckets in order and put all elements back into the original array. (en) Bucketsort (von englisch bucket „Eimer“) ist ein Sortierverfahren, das für bestimmte Werte-Verteilungen eine Eingabe-Liste in linearer Zeit sortiert. Der Algorithmus ist in drei Phasen eingeteilt: 1. * Verteilung der Elemente auf die Buckets (Partitionierung) 2. * Jeder Bucket wird mit einem weiteren Sortierverfahren wie beispielsweise Mergesort sortiert. 3. * Der Inhalt der sortierten Buckets wird konkateniert. Das Verfahren arbeitet also out-of-place. (de) El ordenamiento por casilleros (bucket sort o bin sort, en inglés) es un algoritmo de ordenamiento que distribuye todos los elementos a ordenar entre un número finito de casilleros. Cada casillero solo puede contener los elementos que cumplan unas determinadas condiciones. En el ejemplo esas condiciones son intervalos de números. Las condiciones deben ser excluyentes entre sí, para evitar que un elemento pueda ser clasificado en dos casilleros distintos.Después cada uno de esos casilleros se ordena individualmente con otro algoritmo de ordenación (que podría ser distinto según el casillero), o se aplica recursivamente este algoritmo para obtener casilleros con menos elementos. Se trata de una generalización del algoritmo . Cuando los elementos a ordenar están uniformemente distribuidos la complejidad computacional de este algoritmo es de O(n). El algoritmo contiene los siguientes pasos: 1. * Crear una colección de casilleros vacíos 2. * Colocar cada elemento a ordenar en un único casillero 3. * Ordenar individualmente cada casillero 4. * devolver los elementos de cada casillero concatenados por orden (es) Le tri par paquets est un algorithme de tri qui fonctionne sur des nombres réels appartenant à un intervalle borné fixé à l'avance. Le principe de ce tri consiste à partitionner régulièrement l'intervalle d'entrée en autant de sous-intervalles que l'entrée comporte d'éléments à trier, et à distribuer les données selon leur valeurs en autant de paquets correspondant à ces sous-intervalles. Les paquets sont alors triés séparément à l'aide d'un autre algorithme de tri. Si les nombres en entrée sont uniformément distribués dans l'intervalle initial, alors la complexité temporelle moyenne du tri par paquets est linéaire, et ce quel que soit l'algorithme de tri auxiliaire utilisé. (fr) 버킷 정렬(bucket 整列), 버킷 소트(bucket sort)는 배열의 원소를 여러 으로 분산하여 작동하는 정렬 알고리즘이다. 버킷은 빈(bin)이라고도 불리고, 버킷 정렬도 빈 정렬로도 불린다. 각 버킷은 다른 정렬 알고리즘을 사용하거나 버킷 정렬을 반복 적용해 각각 정렬한다. 분포 정렬이고 일반화된 비둘기집 정렬과 같다. 최하위 유효숫자부터 정렬하는 기수 정렬과도 비슷하다. 비교를 이용해 구현할 수도 있어서 비교 정렬 알고리즘으로 보기도 한다. 계산 복잡도는 각 버킷을 정렬하는 데 사용되는 알고리즘, 사용할 버킷 수, 버킷마다 균일한 입력이 들어가는지 여부에 따라 다르다. 정렬은 다음과 같이 이루어진다. 1. * 빈 버킷의 배열을 준비한다. 2. * 분산: 정렬할 배열의 원소를 각각 버킷에 넣는다. 3. * 내용물이 있는 버킷을 각각 정렬한다. 4. * 수집: 버킷을 순서대로 방문하며 모든 원소를 원래 배열에 다시 넣는다. (ko) バケットソート（英: bucket sort）は、ソートのアルゴリズムの一つ。バケツソート、ビンソート（英: bin sort）などともいう。バケツ数 k 個使った場合、オーダーはO(n + k)となり、ソートする要素数nとk を無関係にできる場合線形時間ソートとなるが、要素間の全順序関係を用いるソートとは異なり、キーの取りうる値がk種類である、という入力により強い制限を要求するソートである。 (ja) Il bucket sort è un algoritmo di ordinamento per valori numerici che si assume siano distribuiti uniformemente in un intervallo . La complessità del bucket sort è lineare O(n). (it) Bucket sort, ou bin sort, é um algoritmo de ordenação que funciona dividindo um vetor em um número finito de recipientes. Cada recipiente é então ordenado individualmente, seja usando um algoritmo de ordenação diferente, ou usando o algoritmo bucket sort recursivamente. O Bucket Sort tem complexidade linear quando o vetor a ser ordenado contém valores que são uniformemente distribuídos. (pt) Sortowanie kubełkowe (ang. bucket sort) – jeden z algorytmów sortowania, najczęściej stosowany, gdy liczby w zadanym przedziale są rozłożone jednostajnie, ma on wówczas złożoność Θ(n). W przypadku ogólnym pesymistyczna złożoność obliczeniowa tego algorytmu wynosi O(n²). Pomysł takiego sortowania podali po raz pierwszy w roku 1956 E. J. Issac i R. C. Singleton. (pl) Сортування комірками або коміркове сортування (англ. Bucket sort) — це стабільний алгоритм впорядкування, що доцільно використовувати, якщо вхідні дані розподілені рівномірно. В основі алгоритму лежить розподілення всіх елементів по скінченній кількості комірок. Кожна комірка впорядковується окремо іншим алгоритмом впорядкування або ж рекурсивно алгоритмом впорядкування комірками. Сортування комірками є узагальненням сортування підрахунком. Алгоритм працює за час , оскільки використовує додаткову інформацію про елементи. (uk) Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения. Данный алгоритм требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой. Преимущества: относится к классу быстрых алгоритмов с линейным временем исполнения O(N) (на удачных входных данных). Недостатки: сильно деградирует при большом количестве мало отличных элементов, или же на неудачной функции получения номера корзины по содержимому элемента. В некоторых таких случаях для строк, возникающих в реализациях основанного на сортировке строк алгоритма сжатия BWT, оказывается, что быстрая сортировка строк в версии Седжвика значительно превосходит блочную сортировку скоростью. (ru) 桶排序（Bucket sort）或所謂的箱排序，是一個排序演算法，工作的原理是將陣列分到有限數量的桶裡。每個桶再個別排序（有可能再使用別的排序演算法或是以遞迴方式繼續使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的陣列內的數值是均勻分配的時候，桶排序使用線性時間（）。但桶排序並不是比较排序，他不受到下限的影響。 桶排序以下列程序進行： 1. * 設置一個定量的陣列當作空桶子。 2. * 尋訪序列，並且把項目一個一個放到對應的桶子去。 3. * 對每個不是空的桶子進行排序。 4. * 從不是空的桶子裡把項目再放回原來的序列中。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Bucket_sort_1.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.rrsd.com/software_development/postmans_sort/cuj/cuj.htm http://www1bpt.bridgeport.edu/~dichter/lilly/bucketsort.htm http://www.dcc.uchile.cl/~rbaeza/handbook/algs/4/423.sort.c.html https://xlinux.nist.gov/dads/HTML/bucketsort.html https://xlinux.nist.gov/dads/HTML/postmansort.html |
| dbo:wikiPageID | 97592 (xsd:integer) |
| dbo:wikiPageLength | 13746 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121660233 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quicksort dbr:Insertion_sort dbr:Analysis_of_algorithms dbr:Linear_time dbr:Comparison_sort dbr:Pigeonhole_sort dbr:Post_office dbc:Articles_with_example_pseudocode dbc:Sorting_algorithms dbr:Floor_function dbr:Counting_sort dbr:Array_data_structure dbc:Stable_sorts dbr:Dictionary_of_Algorithms_and_Data_Structures dbr:Sorting_algorithm dbr:Merge_sort dbr:Mergesort dbr:Bucket_(computing) dbr:National_Institute_of_Standards_and_Technology dbr:Radix_sort dbr:Selection_sort dbr:Distribution_sort dbr:File:Bucket_sort_1.svg dbr:File:Bucket_sort_2.svg |
| dbp:averageTime | , where k is the number of buckets. . (en) |
| dbp:class | dbr:Sorting_algorithm |
| dbp:data | dbr:Array_data_structure |
| dbp:wikiPageUsesTemplate | dbt:Short_description dbt:Not_in_source dbt:Infobox_algorithm dbt:Sorting |
| dct:subject | dbc:Articles_with_example_pseudocode dbc:Sorting_algorithms dbc:Stable_sorts |
| rdf:type | yago:WikicatSortingAlgorithms yago:WikicatStableSorts yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Category105838765 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Event100029378 yago:Idea105833840 yago:Kind105839024 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:SortingAlgorithm105847658 |
| rdfs:comment | Přihrádkové řazení (anglicky bucket sort) je stabilní řadicí algoritmus. Algoritmus rozděluje vstupní data na několik částí (přihrádek, anglicky bucketů). Tyto části jsou následně seřazeny. (cs) Bucketsort (von englisch bucket „Eimer“) ist ein Sortierverfahren, das für bestimmte Werte-Verteilungen eine Eingabe-Liste in linearer Zeit sortiert. Der Algorithmus ist in drei Phasen eingeteilt: 1. * Verteilung der Elemente auf die Buckets (Partitionierung) 2. * Jeder Bucket wird mit einem weiteren Sortierverfahren wie beispielsweise Mergesort sortiert. 3. * Der Inhalt der sortierten Buckets wird konkateniert. Das Verfahren arbeitet also out-of-place. (de) 버킷 정렬(bucket 整列), 버킷 소트(bucket sort)는 배열의 원소를 여러 으로 분산하여 작동하는 정렬 알고리즘이다. 버킷은 빈(bin)이라고도 불리고, 버킷 정렬도 빈 정렬로도 불린다. 각 버킷은 다른 정렬 알고리즘을 사용하거나 버킷 정렬을 반복 적용해 각각 정렬한다. 분포 정렬이고 일반화된 비둘기집 정렬과 같다. 최하위 유효숫자부터 정렬하는 기수 정렬과도 비슷하다. 비교를 이용해 구현할 수도 있어서 비교 정렬 알고리즘으로 보기도 한다. 계산 복잡도는 각 버킷을 정렬하는 데 사용되는 알고리즘, 사용할 버킷 수, 버킷마다 균일한 입력이 들어가는지 여부에 따라 다르다. 정렬은 다음과 같이 이루어진다. 1. * 빈 버킷의 배열을 준비한다. 2. * 분산: 정렬할 배열의 원소를 각각 버킷에 넣는다. 3. * 내용물이 있는 버킷을 각각 정렬한다. 4. * 수집: 버킷을 순서대로 방문하며 모든 원소를 원래 배열에 다시 넣는다. (ko) バケットソート（英: bucket sort）は、ソートのアルゴリズムの一つ。バケツソート、ビンソート（英: bin sort）などともいう。バケツ数 k 個使った場合、オーダーはO(n + k)となり、ソートする要素数nとk を無関係にできる場合線形時間ソートとなるが、要素間の全順序関係を用いるソートとは異なり、キーの取りうる値がk種類である、という入力により強い制限を要求するソートである。 (ja) Il bucket sort è un algoritmo di ordinamento per valori numerici che si assume siano distribuiti uniformemente in un intervallo . La complessità del bucket sort è lineare O(n). (it) Bucket sort, ou bin sort, é um algoritmo de ordenação que funciona dividindo um vetor em um número finito de recipientes. Cada recipiente é então ordenado individualmente, seja usando um algoritmo de ordenação diferente, ou usando o algoritmo bucket sort recursivamente. O Bucket Sort tem complexidade linear quando o vetor a ser ordenado contém valores que são uniformemente distribuídos. (pt) Sortowanie kubełkowe (ang. bucket sort) – jeden z algorytmów sortowania, najczęściej stosowany, gdy liczby w zadanym przedziale są rozłożone jednostajnie, ma on wówczas złożoność Θ(n). W przypadku ogólnym pesymistyczna złożoność obliczeniowa tego algorytmu wynosi O(n²). Pomysł takiego sortowania podali po raz pierwszy w roku 1956 E. J. Issac i R. C. Singleton. (pl) Сортування комірками або коміркове сортування (англ. Bucket sort) — це стабільний алгоритм впорядкування, що доцільно використовувати, якщо вхідні дані розподілені рівномірно. В основі алгоритму лежить розподілення всіх елементів по скінченній кількості комірок. Кожна комірка впорядковується окремо іншим алгоритмом впорядкування або ж рекурсивно алгоритмом впорядкування комірками. Сортування комірками є узагальненням сортування підрахунком. Алгоритм працює за час , оскільки використовує додаткову інформацію про елементи. (uk) 桶排序（Bucket sort）或所謂的箱排序，是一個排序演算法，工作的原理是將陣列分到有限數量的桶裡。每個桶再個別排序（有可能再使用別的排序演算法或是以遞迴方式繼續使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的陣列內的數值是均勻分配的時候，桶排序使用線性時間（）。但桶排序並不是比较排序，他不受到下限的影響。 桶排序以下列程序進行： 1. * 設置一個定量的陣列當作空桶子。 2. * 尋訪序列，並且把項目一個一個放到對應的桶子去。 3. * 對每個不是空的桶子進行排序。 4. * 從不是空的桶子裡把項目再放回原來的序列中。 (zh) Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, a generalization of pigeonhole sort that allows multiple keys per bucket, and is a cousin of radix sort in the most-to-least significant digit flavor. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm. The computational complexity depends on the algorithm used to sort each bucket, the number of buckets to use, and whether the input is uniformly distributed. (en) El ordenamiento por casilleros (bucket sort o bin sort, en inglés) es un algoritmo de ordenamiento que distribuye todos los elementos a ordenar entre un número finito de casilleros. Cada casillero solo puede contener los elementos que cumplan unas determinadas condiciones. En el ejemplo esas condiciones son intervalos de números. Las condiciones deben ser excluyentes entre sí, para evitar que un elemento pueda ser clasificado en dos casilleros distintos.Después cada uno de esos casilleros se ordena individualmente con otro algoritmo de ordenación (que podría ser distinto según el casillero), o se aplica recursivamente este algoritmo para obtener casilleros con menos elementos. Se trata de una generalización del algoritmo . Cuando los elementos a ordenar están uniformemente distribuidos la (es) Le tri par paquets est un algorithme de tri qui fonctionne sur des nombres réels appartenant à un intervalle borné fixé à l'avance. Le principe de ce tri consiste à partitionner régulièrement l'intervalle d'entrée en autant de sous-intervalles que l'entrée comporte d'éléments à trier, et à distribuer les données selon leur valeurs en autant de paquets correspondant à ces sous-intervalles. Les paquets sont alors triés séparément à l'aide d'un autre algorithme de tri. (fr) Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения. (ru) |
| rdfs:label | Přihrádkové řazení (cs) Bucketsort (de) Bucket sort (en) Ordenamiento por casilleros (es) Tri par paquets (fr) Bucket sort (it) バケットソート (ja) 버킷 정렬 (ko) Sortowanie kubełkowe (pl) Bucket sort (pt) Блочная сортировка (ru) Сортування комірками (uk) 桶排序 (zh) |
| owl:sameAs | freebase:Bucket sort wikidata:Bucket sort dbpedia-bg:Bucket sort dbpedia-cs:Bucket sort dbpedia-de:Bucket sort dbpedia-es:Bucket sort dbpedia-fa:Bucket sort dbpedia-fr:Bucket sort dbpedia-he:Bucket sort http://hy.dbpedia.org/resource/Բլոկային_դասակարգում dbpedia-it:Bucket sort dbpedia-ja:Bucket sort dbpedia-ko:Bucket sort dbpedia-pl:Bucket sort dbpedia-pt:Bucket sort dbpedia-ru:Bucket sort dbpedia-sr:Bucket sort dbpedia-tr:Bucket sort dbpedia-uk:Bucket sort dbpedia-zh:Bucket sort https://global.dbpedia.org/id/4rWJz yago-res:Bucket sort |
| prov:wasDerivedFrom | wikipedia-en:Bucket_sort?oldid=1121660233&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Bucket_sort_1.svg wiki-commons:Special:FilePath/Bucket_sort_2.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Bucket_sort |
| is dbo:wikiPageRedirects of | dbr:Bin_sort dbr:Bucket_array dbr:Bucket_sorting dbr:Bucketsort dbr:Range_sort dbr:Postal_sort dbr:Postman's_sort dbr:Postman_sort dbr:Histogram_sort |
| is dbo:wikiPageWikiLink of | dbr:American_flag_sort dbr:Proxmap_sort dbr:Quicksort dbr:List_of_algorithms dbr:Bloom_filter dbr:Interpolation_sort dbr:Punched_card_sorter dbr:NAS_Parallel_Benchmarks dbr:Median_cut dbr:Edge-notched_card dbr:Flashsort dbr:Bin_sort dbr:Asymptotically_optimal_algorithm dbr:Counting_sort dbr:Hybrid_algorithm dbr:Distributed_hash_table dbr:Sorting_algorithm dbr:Spreadsort dbr:Bucket_(computing) dbr:Radix_sort dbr:SPQR_tree dbr:Image_foresting_transform dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Unit_record_equipment dbr:Bucket_array dbr:Bucket_sorting dbr:Bucketsort dbr:Range_sort dbr:Postal_sort dbr:Postman's_sort dbr:Postman_sort dbr:Histogram_sort |
| is foaf:primaryTopic of | wikipedia-en:Bucket_sort |
