補間ソート

インプレース補間タグソート
クラス	ソートアルゴリズム
データ構造	配列
最悪の場合のパフォーマンス	お（ n ） {\displaystyle O(n)}
最高のパフォーマンス	お（ n ） {\displaystyle O(n)}
平均的なパフォーマンス	お（ n ） {\displaystyle O(n)}
最悪の場合の空間複雑度	お（ n ） b 私 t s {\displaystyle O(n)ビット}
最適	お（ n ） {\displaystyle O(n)}

補間タグソート
クラス	ソートアルゴリズム
データ構造	配列
最悪の場合のパフォーマンス	お（ n 2 ） {\displaystyle O(n^{2})}
最高のパフォーマンス	お（ n ） {\displaystyle O(n)}
平均的なパフォーマンス	お（ n + け） {\displaystyle O(n+k)}
最悪の場合の空間複雑度	お（ 2 n + （ n ） b 私 t s ） {\displaystyle O(2n+(n)ビット)}
最適	お（ n ） {\displaystyle O(n)}

補間ソート
クラス	ソートアルゴリズム
データ構造	配列
最悪の場合のパフォーマンス	お（ n 2 ） {\displaystyle O(n^{2})}
最高のパフォーマンス	お（ n ） {\displaystyle O(n)}
平均的なパフォーマンス	お（ n + け） {\displaystyle O(n+k)}
最悪の場合の空間複雑度	お（ n ∗ 3 ） {\displaystyle O(n*3)}
最適	お（ n ） {\displaystyle O(n)}

コンピュータサイエンスにおけるソートアルゴリズム

補間ソート（またはヒストグラムソート）はバケットソートの一種です。補間式を用いてデータをバケットに割り当てます。一般的な補間式は以下のとおりです。

補間 = INT(((Array[i] - min) / (max - min)) * (ArraySize - 1))

アルゴリズム

補間ソートは、補間式を使用して分割統治するソートアルゴリズムです。^[1]この方法では、元の数値列に対応するレコードバケット長の配列を使用します。配列は、メモリスタッキングによる空間複雑度の増加を防ぎます。長さ配列のセグメンテーションレコードは、二次関数を使用して配列のメモリ空間を動的に宣言および削除できます。再帰プログラムの制御に必要な空間複雑度はです。には、動的に割り当てられたメモリの2次元配列とレコード長の配列が含まれます。ただし、の効率的なソート方法として、実行の複雑さは依然として維持されます。動的に割り当てられたメモリの配列は、リンクリスト、スタック、キュー、連想配列、ツリー構造などで実装できます。JavaScriptなどの配列オブジェクトが適用できます。データ構造の違いは、データアクセスの速度、つまりソートに必要な時間に関係します。順序付けされた配列の値が等差数列にほぼ均一に分布している場合、補間ソート順序付けの線形時間はです。 $O(n^{2})$ $O(3n)$ $O(n+k)$ $O(n)$

補間ソートアルゴリズム

未ソートのバケットの長さを記録するためのバケット長配列を設定します。元の配列長に初期化します。
[メインソート] バケット長配列がクリアされソートが完了している場合は実行します。クリアされていない場合は[除算関数]を実行します。
[除算関数] バケット長配列の末尾からバケット長分をポップすることで除算を実行します。バケット内の最大値と最小値を求めます。最大値と最小値が等しい場合、ソートが完了し除算を終了します。
2次元配列をすべて空のバケットとして設定します。補間数に応じてバケットに分割します。
バケットに分割した後、バケットの長さ分の要素をバケット長の配列にプッシュします。そして、空でないすべてのバケットから要素を1つずつ元の配列に戻します。
[メインソート]に戻ります。

ヒストグラムソートアルゴリズム

NISTの定義：バケットソートアルゴリズムの効率的な3パス改良。^[2]

最初のパスでは、補助配列内の各バケットのアイテム数をカウントし、各補助エントリが先行するアイテムの数になるように実行中の合計を計算します。
2 番目のパスでは、各アイテムをそのアイテムのキーの補助エントリに従って適切なバケットに配置します。
最後のパスでは各バケットをソートします。

練習する

補間ソートの実装

JavaScript コード:

Array.prototype.interpolationSort = function ( ) { var divideSize = new Array ( ); var end = this.length ; divideSize [ 0 ] = end ; while ( divideSize.length > 0 ) { divide ( this ); } // ArrayListに関数 divideを繰り返しますfunction divide ( A ) { var size = divideSize.pop ( ) ; var start = end - size ; var min = A [ start ]; var max = A [ start ] ; for ( var i = start + 1 ; i < end ; i ++ ) { if ( A [ i ] < min ) { min = A [ i ] ; } else { if ( A [ i ] > max ) { max = A [ i ]; } } } if ( min == max ) { end = end - size ; } else { var p = 0 ; var bucket = new Array ( size ) ; for ( var i = 0 ; i < size ; i ++ ) { bucket [ i ] = new Array (); } for ( var i = start ;  

      
     
    
         
  
    
       
         
       
       
               
              
                 
    
              
     
         
          
                    
           i < end ; i ++ ) { p = Math . floor ((( A [ i ] - min ) / ( max - min ) ) * ( size - 1 )); bucket [ p ]. push ( A [ i ]); } for ( var i = 0 ; i < size ; i ++ ) { if ( bucket [ i ]. length > 0 ) { for ( var j = 0 ; j < bucket [ i ]. length ; j ++ ) { A [ start ++ ] = bucket [ i ][ j ]; } divideSize . push ( bucket [ i ]. length ); } } } } };

補間ソート再帰法

最悪の場合の空間計算量: $O(n^{2})$

Array .prototype . interpolationSort = function () { // --編集日:2019/08/31 --// var start = 0 ; var size = this.length ; var min = this [ 0 ]; var max = this [ 0 ]; for ( var i = 1 ; i < size ; i ++ ) { if ( this [ i ] < min ) { min = this [ i ] ; } else { if ( this [ i ] > max ) { max = this [ i ]; } } } if ( min ! = max ) { var bucket = new Array ( size ) ; for ( var i = 0 ; i < size ; i ++ ) { bucket [ i ] = new Array (); } var interpolation = 0 ; for ( var i = 0 ; i < size ; i ++ ) { interpolation = Math . floor ((( this [ i ] - min ) / ( max - min )) * ( size - 1 )); bucket [補間] .push ( this [ i ]); } for ( var i = 0 ; i < size ; 

     
     
     
      
           
            
             
  
      
        
                  
       
             
                  
      
    
            i ++ ) { if ( bucket [ i ]. length > 1 ) { bucket [ i ]. interpolationSort (); } // 再帰for ( var j = 0 ; j < bucket [ i ]. length ; j ++ ) { this [ start ++ ] = bucket [ i ][ j ]; } } } };

ヒストグラムソートの実装

Array . prototype . histogramSort = function () { //-- 編集日:2019/11/14 --// var end = this . length ; var sortedArray = new Array ( end ); var interpolation = new Array ( end ); var hitCount = new Array ( end ); var divideSize = new Array (); divideSize [ 0 ] = end ; while ( divideSize . length > 0 ) { distribute ( this ); } // 繰り返し関数を Array に分配する function distribute ( A ) { var size = divideSize . pop ( ); var start = end - size ; var min = A [ start ]; var max = A [ start ]; for ( var i = start + 1 ; i < end ; i ++ ) { if ( A [ i ] < min ) { min = A [ i ]; } else { if ( A [ i ] > max ) { max = A [ i ]; } } } if ( min == max ) { end = end - size ; } else { for ( var i = start ; i < end ; i ++ ) {  

     
      
      
      
      
    
         
  
    
       
         
       
       
               
              
                 
    
              
     
                hitCount [ i ] = 0 ; } for ( var i = start ; i < end ; i ++ ) { interpolation [ i ] = start + Math . floor ((( A [ i ] - min ) / ( max - min ) ) * ( size - 1 )); hitCount [ interpolation [ i ]] ++ ; } for ( var i = start ; i < end ; i ++ ) { if ( hitCount [ i ] > 0 ) { divideSize . push ( hitCount [ i ] ); } } hitCount [ end - 1 ] = end - hitCount [ end - 1 ]; for ( var i = end - 1 ; i > start ; i -- ) { hitCount [ i - 1 ] = hitCount [ i ] - hitCount [ i - 1 ]; } for ( var i = start ; i < end ; i ++ ) { sortedArray [ hitCount [ interpolation [ i ]]] = A [ i ]; hitCount [ interpolation [ i ]] ++ ; } for ( var i = start ; i < end   
               
                          
        
      
               
              
      
          
               
            
      
               
          
        
      
             ; i ++ ) { A [ i ] = sortedArray [ i ]; } } } };

変異体

補間タグソート

補間タグソートは補間ソートの派生です。バケットソートと分割法を適用し、配列データを数学的な補間式によって限られた数のバケットに分割し、バケット内のデータを元の処理プログラムで再帰的に処理してソートを完了します。

補間タグソートは、補間ソートにおける再帰ソート手法です。再帰によるスタックオーバーフローを回避するため、メモリクラッシュが発生します。代わりに、ブールデータ型のタグ配列を使用して再帰関数を操作し、メモリを解放します。必要な追加メモリ空間はほぼです。動的に割り当てられたメモリの2次元配列とブールデータ型のタグ配列が含まれます。スタック、キュー、連想配列、ツリー構造をバケットとして実装できます。 $2n+(n)ビット$

JavaScript配列オブジェクトはこのソート方法に適しているため、データ構造の違いはデータアクセス速度、ひいてはソート処理にかかる時間に影響します。ソート対象となる配列内の値が均等に分布している場合、線形時間Θ(n)が使用されます。バケットソートアルゴリズムは、ソート処理をの下限に制限しません。補間タグソートの平均パフォーマンス複雑度はです。 $O(nlogn)$ $O(n+k)$

補間タグソートアルゴリズム

タグ配列を元の配列サイズと同じに設定し、false 値に初期化します。
[メインソート] 元の配列のすべてのバケットがソートされているかどうかを判断します。ソートが完了していない場合は、[除算関数] を実行します。
[分割関数] バケット内の最大値と最小値を求めます。最大値と最小値が等しい場合、ソートが完了し、分割が停止します。
空のバケットをすべて2次元配列として用意し、補間数に応じてバケットに分割します。
バケットに分割した後、タグ配列でバケットの開始位置を真の値としてマークします。そして、空でないすべてのバケットから、要素を1つずつ元の配列に戻します。
[メインソート]に戻ります。

練習する

JavaScript コード:

Array . prototype . InterpolaionTagSort = function () { // Whale Chen は「Wikipedia CC BY-SA 3.0 License」に同意します。署名日: 2019-06-21 // var end = this . length ; if ( end > 1 ) { var start = 0 ; var Tag = new Array ( end ); // アルゴリズムステップ 1 for ( var i = 0 ; i < end ; i ++ ) { Tag [ i ] = false ; } Divide ( this ); } while ( end > 1 ) { // アルゴリズムステップ 2   while ( Tag [ -- start ] == false ) { } // 次のバケットの開始位置を検索Divide ( this ); }  

      
       
         
                  
                  
     
   
                           
          
     
  

  function Divide ( A ) { var min = A [ start ]; var max = A [ start ]; for ( var i = start + 1 ; i < end ; i ++ ) { if ( A [ i ] < min ) { min = A [ i ]; } else { if ( A [ i ] > max ) { max = A [ i ]; } } } if ( min == max ) { end = start ; } // アルゴリズム ステップ 3 Start を次のバケットの終了にしますelse { var interpolation = 0 ; var size = end - start ; var Bucket = new Array ( size ); // アルゴリズム ステップ 4          for ( var i = 0 ; i < size ; i ++ ) { Bucket [ i ] = new Array (); } for ( var i = start ; i < end ; i ++ ) { interpolation = Math . floor ((( A [ i ] - min ) / ( max - min )) * ( size - 1 )); Bucket [補間]. push ( A [ i ]); } for ( var i = 0 ; i     
        
       
                
               
                  
                 
                                               
          
            
                
                      
                 
                      
          
       
            < size ; i ++ ) { if ( Bucket [ i ]. length > 0 ) { // アルゴリズムステップ 5       Tag [ start ] = true ; for ( var j = 0 ; j < Bucket [ i ]. length ; j ++ ) { A [ start ++ ] = Bucket [ i ][ j ]; } } } } } //アルゴリズムステップ 6 };

インプレース補間タグソート

インプレース補間タグソートは、補間ソートのインプレースアルゴリズムです。インプレース補間タグソートは、Nビットのタグを維持することで、N回のスワップのみでソートを実現できます。ただし、ソート対象となる配列は連続した整数列で重複がないか、等差数列の数に近似するように完全に均等に分布している必要があります。

因子列データは重複してはいけません。例えば、0～100のソートは1ステップで完了します。交換回数は、計算時間の複雑さは、最悪の空間複雑さはです。系列の特性がこのソート法の条件要件「配列は連続した整数または重複しない等差数列である」を満たす場合、インプレース補間タグソートは非常に高速でメモリ空間を節約できる優れたソート法となります。 $O(n)$ $O(n)$ $O(n)ビット$

インプレース補間タグソートアルゴリズム

インプレース補間タグソートは、繰り返しのない連続する整数系列をソートします。元の配列と同じ長さのブールデータ型タグ配列を1つだけ使用し、配列の先頭からデータの補間を計算します。補間は配列の新しい位置を指します。位置は、入れ替えられた位置がタグ配列の対応する位置でtrueとしてマークされ、配列の末尾まで増加します。

アルゴリズムプロセス:

等しい数のタグ配列を設定して、false 値に初期化します。
tag[i]がfalseのときに配列にアクセスし、補間=pに対応する位置を計算します。
a[i]とa[p]を交換し、tag[p] = trueとします。
ツアー配列が完成し、ソートが完了しました。

練習する

JavaScript コード:

Array.prototype.InPlaceTagSort = function ( ) { //編集日: 2019-07-02 var n = this.length ; var Tag = new Array ( n ) ; for ( i = 0 ; i < n ; i ++ ) { Tag [ i ] = false ; } var min = this [ 0 ] ; var max = this [ 0 ] ; for ( i = 1 ; i < n ; i ++ ) { if ( this [ i ] < min ) { min = this [ i ]; } else { if ( this [ i ] > max ) { max = this [ i ]; } } } var p = 0 ; var temp = 0 ; for ( i = 0 ; i < n ; i ++ ) { while ( Tag [ i ] == false ) { p = Math . floor ((( this [ i ] - min ) / ( max - min )) * ( n - 1 )); temp = this [ i ]; this [ i ] = this [ p ]; this [ p ] = temp ; Tag [ p ] = true  
 
     
      
              
     
     
                   
               
     
     
          
         
                  
        
         
        
        ; } } }; needSortArray 。InPlaceTagSort ();

O(n)時間で実行されるインプレースソートの起源

ドナルド・クヌースは「アルゴリズムの数学的分析」の中で、「計算複雑性の研究は、私たちが日々直面するより日常的な問題に対するツールを磨く興味深い方法である」と述べています。^[3]

クヌースはさらに、ソート問題に関して、時間効率の高いインサイチュー順列化は本質的にサイクルリーダーを見つける問題と関連しており、任意の時点でどれだけの順列化が実行されたかを指定する追加の「タグ」ビットを操作できれば、インサイチュー順列化は容易に時間内に実行できると指摘した。そのようなタグビットがなければ、「あらゆるアルゴリズムはインサイチュー順列化に平均して少なくともステップを必要とすると推測するのが妥当であるように思われる」と彼は結論付けている。 ^[3] $O(n)$ $n$ $n\log n$

インプレース補間タグソートは、ドナルド・クヌース教授が「追加の「タグ」ビットを操作し、サイクルリーダーを見つけ、インサイチュー順列化を時間内に簡単に実行できる」と述べたソートアルゴリズムの 1 つです。 $n$ $O(n)$

類似ソート方法

他のソート方法と再帰アルゴリズムを組み合わせたバケットソート

バケットソートは、他のソート方法と組み合わせてソートを完了することができます。バケットソートと挿入ソートを組み合わせると、かなり効率的なソート方法になります。ただし、系列に値からの大きな偏差が現れた場合、たとえば、系列の最大値が次に大きい値のN倍よりも大きい場合などです。列の系列を処理した後、最大値以外のすべての要素が同じバケットに収まるように分布します。2番目のソート方法は挿入ソートを使用します。実行の複雑さが悪化する可能性があります。これにより、バケットソートを使用する意味と高速性が失われます。 $O(n^{2})$

補間ソートは、バケットソートを再帰的に用いる方法です。再帰処理を行った後も、バケットソートを用いて系列を分散させます。これにより、上記の状況を回避できます。再帰補間ソートの実行複雑度をに抑えたい場合は、系列全体に階乗増幅を適用する必要があります。実際には、特殊な分布の系列が発生する可能性は非常に低いです。 $O(n^{2})$

参考文献

^ NISTアルゴリズム。「補間ソート」。定義：ヒストグラムソートを参照。
^ NISTアルゴリズム。「histogramSort sort」。定義：バケットソートアルゴリズムの効率的な3パス改良。
^ ab カール・ディートリッヒ・ノイベルト (1998)。「フラッシュソートアルゴリズム」。2007 年 11 月 6 日に取得。

外部リンク

補間ソート.html
ヒストグラムソート.html
フラッシュソートアルゴリズム
アルゴリズムの数学的分析
http://www.drdobbs.com/database/the-flashsort1-algorithm/184410496
バケット排列遞迴方式演算法バケットソート再帰方式。ホエールチェン 2012/09/16
插值標簽排序演算法補間タグソートアルゴリズム。ホエールチェン 2013/03/24
補間ソート（Pascal版あり）
w3schools JavaScript 配列ソートテストプラットフォーム

[1] NISTアルゴリズム。「補間ソート」。定義：ヒストグラムソートを参照。

[2] NISTアルゴリズム。「histogramSort sort」。定義：バケットソートアルゴリズムの効率的な3パス改良。

[neubert_code-3] カール・ディートリッヒ・ノイベルト (1998)。「フラッシュソートアルゴリズム」。2007 年 11 月 6 日に取得。