JavaScriptアルゴリズム-挿入順序

挿入
簡単な問題:配列Aにx要素を挿入する

慣性思考JavaScript元の実装

let A = [2,4,6,9,10]  //   
const x = 8  //    
const b = A.find(a => a > x)  //          b

if(b == undefined){  //                 

    A.push(x)  //        

} else {

    const idx = A.indexOf(b) //  b     
    A.splice(idx,0,x) //           

}

による最適化 

簡単に実現するのはすべてこんなに面倒です.look look again
うんpushの代わりにspliceを使ってもいいです.xより大きい値がないとindexOfは-1に戻ります.ゲートがあります.コードをつけてみてください.

let A = [2,4,6,9,10]  //   
const x = 8  //    
const b = A.find(a => a > x)  //          b

//       
const idx = A.indexOf(b)
A.splice(idx==-1?A.length:idx,0,x)

プログラムアルゴリズムはどうやって

を実現しますか?
プログラム実現挿入プロセス
0
1
2
3
4
5
p比較ポインタ
2
4
6
9
10
空席
p=4  (10>8)
2
4
6
9
空席
10
p=3(9>8)
2
4
6
空席
9
10
p=2(6<8)
2
4
6
8
9
10
 
最後に、p指向要素とxサイズ、p値>xを最後から比較し、p値を後に1ビット移動し、ポインタを前に移動して比較を続けます.p値がx以下であれば、xが現在のポインタを挿入した後の空席.  言葉がとても抽象的です.やっぱりlook codeですね.

function inster(A, x){
    p = A.length -1 ; //          
    
    while(p>=0 && A[p]>x){   //        x 
        
        A[p+1] = A[p]   //         
        p--    //    

    }
    
    A[p+1] = x   //        x ,              

}

並べ替えの挿入

考え方

(1)配列の最初の要素は、一桁の長さしかない順序配列として、暫定的にA集合とする.
(2)ポインタiは、2番目のビットから検索し、要素を指して、順番にAセットを挿入する.
(3)サイクル不変式は、ポインタiの次の順序付けが必要な要素を指します.
(4)ポインタiを最後のビットに移動し、並べ替えを挿入します.
並べ替え図解を挿入する0
1
2
3
4
ポインタi
7
5
8
3
9
i=1
5
7
8
3
9
i=2
5
7
8
3
9
i=3
3
5
7
8
9
i=4
3
5
7
8
9
i=5  
 
解析:緑の領域は常に規則的な配列であり、ポインタの要素は秩序的な配列を挿入します.すなわち、挿入順序は2ステップに分けて1.移動ポインタ2.を挿入します.

アルゴリズムは

を実現する.
把握した挿入アルゴリズムを統合すると、移動ポインタだけを実現する必要があります.両者の組み合わせは並べ替えを挿入します.

function insert(A, i, x){
    p = i-1;  //             
    while(p>=0 && A[p]>x){
       A[p+1] = A[p]
       p--
    }
    A[p+1] = x
}

function insertion_sort(A){
    
    for(let i = 1; i