この線形時間と線形スペースの並べ替えの名前はありますか？

Question

は、我々は、データ構造は、ハッシュはまだ一定時間操作ですが、ストレージが1からに渡されたどんな値に整数のために特別に注文される「注文したマップを」と呼ばれる持っていると仮定しましょう。

linear_sort(arr): 
    largest_element_in_arr = max(arr) 

    ordered_map = new map() 

    // populate values in the map of integers, ranging from 1 to largest integer in array, with 0s. 
    from 1 to largest_element: 
     ordered_map[index] = 0 

    for element in arr: 
     ordered_map[element] += 1 

    // collapse empty elements 
    for element in ordered_map: 
     delete if element's value is 0 

    output elements of ordered_map 

Answer 1

それは本質的counting sortです、ただし、ドメインの値を範囲[0..n]に正規化し、配列で数えるという通常の方法の代わりに、ハッシュ関数を使用してカウントにマップします。

入力値が制限された範囲（カウントソートの弱点）でない疎なデータには便利ですが、もちろんその魔法の「順序付きハッシュ関数」に依存しています。

編集：実際には、最初にマップにデータを入力すると、O(n)のスペースが使用されているように見えます。nは入力の最小値の範囲です。つまり、実際には任意のハッシュ関数を使用します（ハッシュ関数はアイデンティティ関数であり、特別な順序は自然数の順序です）。