| dbpedia-owl:abstract
|
- Pigeonhole sorting, also known as count sort (not to be confused with counting sort), is a sorting algorithm that is suitable for sorting lists of elements where the number of elements (n) and the number of possible key values (N) are approximately the same. It requires O(n + N) time. The pigeonhole algorithm works as follows: Given an array of values to be sorted, set up an auxiliary array of initially empty "pigeonholes," one pigeonhole for each key through the range of the original array. 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. Iterate over the pigeonhole array in order, and put elements from non-empty pigeonholes back into the original array. For example, suppose we were sorting these value pairs by their first element: (5, "hello") (3, "pie") (8, "apple") (5, "king") For each value between 3 and 8 we set up a pigeonhole, then move each element to its pigeonhole: 3: (3, "pie") 4: 5: (5, "hello"), (5, "king") 6: 7: 8: (8, "apple") We then iterate over the pigeonhole array in order and move them back to the original list. The difference between pigeonhole sort and counting sort is that in counting sort, the auxiliary array does not contain lists of input elements, only counts: 3: 1 4: 0 5: 2 6: 0 7: 0 8: 1 Using this information we can perform a series of exchanges on the input array that puts it in order, moving items only once. Pigeonhole sort, in contrast, moves items twice: once onto the pigeonhole/bucket array and again onto the destination array. For arrays where N is much larger than n, bucket sort is a generalization that is more efficient in space and time.
- 鳩の巣ソート（英: pigeonhole sort）はソートアルゴリズムの一種であり、要素数 (n) とソートキーの値の個数 (N) がほぼ同じ場合に適した手法である。必要な時間計算量は Θ(n + N) である。 鳩の巣ソートは次のように動作する。 初期状態で空の「鳩の巣」の配列を用意する。個々の鳩の巣にはソートキーの1つの値が対応している。それぞれの鳩の巣には、そのソートキーを持つ要素のリストを格納する。 入力配列を順に見ていき、それぞれの要素を対応する鳩の巣のリストに入れていく。 鳩の巣の配列を順に走査し、空でない鳩の巣にある要素を順次並べていく。 例えば、以下のような値の対を、それぞれの先頭の値をキーとしてソートする。 (5, "hello") (3, "pie") (8, "apple") (5, "king") キーの値は3から8なので、それぞれについて鳩の巣を設定し、各要素を鳩の巣に移動する。 3: (3, "pie") 4: 5: (5, "hello"), (5, "king") 6: 7: 8: (8, "apple") 次に鳩の巣の配列を順次走査し、出現順に元の配列に戻していけばよい。 分布数えソートに似ているが、分布数えソートでは補助配列にはキーごとの要素数のみを格納し、要素そのものは格納しない。上の例では、次のようになる。 3: 1 4: 0 5: 2 6: 0 7: 0 8: 1 この情報を使うと、ソートキーの値を見ただけでソート後の位置を示すことができる。 N が n よりずっと大きい場合、より一般的なバケットソートの方が効率的である。
- 鸽巢排序(Pigeonhole sort), 也被称作基数分类, 是一种时间复杂度为O(n)且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法. 但它只有在差值(或者可被映射在差值)很小的范围内的数值排序的情况下实用. 当涉及到多个不相等的元素, 且将这些元素放在同一个"鸽巢"的时候, 算法的效率会有所降低. 为了简便和保持鸽巢排序在适应不同的情况, 比如两个在同一个存储桶中结束的元素必然相等 我们一般很少使用鸽巢排序, 因为它很少可以在灵活性, 简便性, 尤是速度上超过其他排序算法. 事实上, 桶排序较鸽巢排序更加的实用. 鸽巢排序的一个比较有名的变形是tally sort, 它仅仅适用非常有限的题目, 这个算法因在Programming Pearls一书中作为解决一个非常规有限集问题方法的例子而著名. 显然, 快速排序可以当作只有两个(有些情况下是三个)"鸽巢"的鸽巢排序
|
| rdfs:comment
|
- 鳩の巣ソート（英: pigeonhole sort）はソートアルゴリズムの一種であり、要素数 (n) とソートキーの値の個数 (N) がほぼ同じ場合に適した手法である。必要な時間計算量は Θ(n + N) である。 鳩の巣ソートは次のように動作する。 初期状態で空の「鳩の巣」の配列を用意する。個々の鳩の巣にはソートキーの1つの値が対応している。それぞれの鳩の巣には、そのソートキーを持つ要素のリストを格納する。 入力配列を順に見ていき、それぞれの要素を対応する鳩の巣のリストに入れていく。 鳩の巣の配列を順に走査し、空でない鳩の巣にある要素を順次並べていく。 例えば、以下のような値の対を、それぞれの先頭の値をキーとしてソートする。 (5, "hello") (3, "pie") (8, "apple") (5, "king") キーの値は3から8なので、それぞれについて鳩の巣を設定し、各要素を鳩の巣に移動する。 3: (3, "pie") 4: 5: (5, "hello"), (5, "king") 6: 7: 8: (8, "apple") 次に鳩の巣の配列を順次走査し、出現順に元の配列に戻していけばよい。 分布数えソートに似ているが、分布数えソートでは補助配列にはキーごとの要素数のみを格納し、要素そのものは格納しない。上の例では、次のようになる。 3: 1 4: 0 5: 2 6: 0 7: 0 8: 1 この情報を使うと、ソートキーの値を見ただけでソート後の位置を示すことができる。 N が n よりずっと大きい場合、より一般的なバケットソートの方が効率的である。
- 鸽巢排序(Pigeonhole sort), 也被称作基数分类, 是一种时间复杂度为O(n)且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法. 但它只有在差值(或者可被映射在差值)很小的范围内的数值排序的情况下实用. 当涉及到多个不相等的元素, 且将这些元素放在同一个"鸽巢"的时候, 算法的效率会有所降低. 为了简便和保持鸽巢排序在适应不同的情况, 比如两个在同一个存储桶中结束的元素必然相等 我们一般很少使用鸽巢排序, 因为它很少可以在灵活性, 简便性, 尤是速度上超过其他排序算法. 事实上, 桶排序较鸽巢排序更加的实用. 鸽巢排序的一个比较有名的变形是tally sort, 它仅仅适用非常有限的题目, 这个算法因在Programming Pearls一书中作为解决一个非常规有限集问题方法的例子而著名. 显然, 快速排序可以当作只有两个(有些情况下是三个)"鸽巢"的鸽巢排序
- Pigeonhole sorting, also known as count sort (not to be confused with counting sort), is a sorting algorithm that is suitable for sorting lists of elements where the number of elements (n) and the number of possible key values (N) are approximately the same. It requires O(n + N) time. The pigeonhole algorithm works as follows: Given an array of values to be sorted, set up an auxiliary array of initially empty "pigeonholes," one pigeonhole for each key through the range of the original array.
|
