| dbo:abstract
|
- Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number n of elements and the length N of the range of possible key values are approximately the same. It requires O(n + N) time. It is similar to counting sort, but differs in that it "moves items twice: once to the bucket array and again to the final destination [whereas] counting sort builds an auxiliary array then uses the array to compute each item's final destination and move the item there." The pigeonhole algorithm works as follows: 1.
* Given an array of values to be sorted, set up an auxiliary array of initially empty "pigeonholes", one pigeonhole for each key in the range of the keys in the original array. 2.
* Going over the original array, put each value into the pigeonhole corresponding to its key, such that each pigeonhole eventually contains a list of all values with that key. 3.
* Iterate over the pigeonhole array in increasing order of keys, and for each pigeonhole, put its elements into the original array in increasing order. (en)
- Il Pigeonhole sort è un algoritmo di ordinamento particolarmente adatto quando il numero di elementi e la lunghezza dell'intervallo dei possibili valori chiave sono approssimativamente uguali. L'algoritmo ha una complessità temporale e spaziale di O(n + N). È simile al counting sort, ma differisce da quest'ultimo perché il pigeonhole muove gli elementi due volte: una volta nell'array di appoggio e poi di nuovo nella destinazione finale. Il nome pigeonhole (tradotto in "buco della piccionaia") deriva dal nome inglese del principio dei cassetti, che ricorda il processo di assegnamento ad una cella all'interno dell'algoritmo. L'algoritmo funziona come segue: 1.
* Dato un array di valori da ordinare, si alloca un array composto inizialmente di celle vuote (i "pigeonhole"), ciascuna per ogni valore compreso nel range dell'array iniziale. 2.
* Scorrendo l'array iniziale, si inserisce ogni valore nella cella corrispondente, in modo che ogni casella alla fine contenga una lista di tutti i valori che corrispondo alla stessa chiave. 3.
* Iterando in ordine sull'array di appoggio, si spostano gli elementi nelle celle non vuota nell'array originale. (it)
- 鳩の巣ソート（はとのすソート、英: pigeonhole sort）はソートアルゴリズムの一種であり、要素数 (n) とソートキーの値の個数 (N) がほぼ同じ場合に適した手法である。必要な時間計算量は Θ(n + N) である。 (ja)
- Сортування Діріхле — це алгоритм сортування, який підходить для сортування списків елементів, де кількість елементів (n) і довжина діапазону можливих значень ключів (N) приблизно однакові. Це вимагає O(n+N) часу. Він подібний до сортування підрахунком, але відрізняється тим, що він переміщує елементи двічі: один раз в масив відрахувань, а в другий раз до кінцевого масиву, оскільки сортування підрахунком створює допоміжний масив для обчислення кінцевого місця кожного елемента і його переміщення. Алгоритм працює наступним чином: 1.
* Враховуючи масив значень, що підлягають сортуванню, створюється допоміжний масив спочатку порожніх значень, один прохід для кожного ключа через діапазон вихідного масиву. 2.
* Переходячи до початкового масиву, кожне значення кладеться в комірку, що відповідає його ключу, таким чином, щоб кожна комірка згодом містила список всіх значень з цим ключем. 3.
* Послідовно переставляється матриця з наведених елементів, і елементи кладуться з непустого вузла назад у вихідний масив. (uk)
- 鸽巢排序（Pigeonhole sort），也被称作基数分类，是一种时间复杂度为（大O符號）且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法。但它只有在差值（或者可被映射在差值）很小的范围内的数值排序的情况下实用。 当涉及到多个不相等的元素，且将这些元素放在同一个「鸽巢」的时候，算法的效率会有所降低。为了简便和保持鸽巢排序在适应不同的情况，比如两个在同一个存储桶中结束的元素必然相等。 我们一般很少使用鸽巢排序，因为它很少可以在灵活性、简便性、尤是速度上超过其他排序算法。事实上，桶排序较鸽巢排序更加的实用。 鸽巢排序的一个比较有名的变形是吻合排序法（tally sort），它仅仅适用非常有限的题目，这个算法因在一书中作为解决一个非常规有限集问题方法的例子而著名。 显然，快速排序可以当作只有两个（有些情况下是三个）"鸽巢"的鸽巢排序。 (zh)
|
| dbo:wikiPageID
| |
| dbo:wikiPageInterLanguageLink
| |
| dbo:wikiPageLength
|
- 2149 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:class
| |
| dbp:data
| |
| dbp:optimal
| |
| dbp:time
|
- , where N is the range of key values and n is the input size (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- 鳩の巣ソート（はとのすソート、英: pigeonhole sort）はソートアルゴリズムの一種であり、要素数 (n) とソートキーの値の個数 (N) がほぼ同じ場合に適した手法である。必要な時間計算量は Θ(n + N) である。 (ja)
- 鸽巢排序（Pigeonhole sort），也被称作基数分类，是一种时间复杂度为（大O符號）且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法。但它只有在差值（或者可被映射在差值）很小的范围内的数值排序的情况下实用。 当涉及到多个不相等的元素，且将这些元素放在同一个「鸽巢」的时候，算法的效率会有所降低。为了简便和保持鸽巢排序在适应不同的情况，比如两个在同一个存储桶中结束的元素必然相等。 我们一般很少使用鸽巢排序，因为它很少可以在灵活性、简便性、尤是速度上超过其他排序算法。事实上，桶排序较鸽巢排序更加的实用。 鸽巢排序的一个比较有名的变形是吻合排序法（tally sort），它仅仅适用非常有限的题目，这个算法因在一书中作为解决一个非常规有限集问题方法的例子而著名。 显然，快速排序可以当作只有两个（有些情况下是三个）"鸽巢"的鸽巢排序。 (zh)
- Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number n of elements and the length N of the range of possible key values are approximately the same. It requires O(n + N) time. It is similar to counting sort, but differs in that it "moves items twice: once to the bucket array and again to the final destination [whereas] counting sort builds an auxiliary array then uses the array to compute each item's final destination and move the item there." The pigeonhole algorithm works as follows: (en)
- Il Pigeonhole sort è un algoritmo di ordinamento particolarmente adatto quando il numero di elementi e la lunghezza dell'intervallo dei possibili valori chiave sono approssimativamente uguali. L'algoritmo ha una complessità temporale e spaziale di O(n + N). È simile al counting sort, ma differisce da quest'ultimo perché il pigeonhole muove gli elementi due volte: una volta nell'array di appoggio e poi di nuovo nella destinazione finale. Il nome pigeonhole (tradotto in "buco della piccionaia") deriva dal nome inglese del principio dei cassetti, che ricorda il processo di assegnamento ad una cella all'interno dell'algoritmo. (it)
- Сортування Діріхле — це алгоритм сортування, який підходить для сортування списків елементів, де кількість елементів (n) і довжина діапазону можливих значень ключів (N) приблизно однакові. Це вимагає O(n+N) часу. Він подібний до сортування підрахунком, але відрізняється тим, що він переміщує елементи двічі: один раз в масив відрахувань, а в другий раз до кінцевого масиву, оскільки сортування підрахунком створює допоміжний масив для обчислення кінцевого місця кожного елемента і його переміщення. Алгоритм працює наступним чином: (uk)
|
| rdfs:label
|
- Pigeonhole sort (it)
- 비둘기집 정렬 (ko)
- 鳩の巣ソート (ja)
- Pigeonhole sort (en)
- 鸽巢排序 (zh)
- Сортування Діріхле (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
