配列をソートした 27 ときのそのデータの位置とlstの中の位置のズレの総和を計算する

Question

数を要素とする配列 lst が与えられたとき，その配列をソートしたときのそのデータの位置とlstの中の位置のズレの総和を計算する関数 f(lst)を作りたいです.現状のプログラムでは，ただクイックソートを行うだけなので，ズレの総和を計算するにはどうすれば良いでしょうか？

function f(lst){
    function quicksort(a, l, r){
        var v, i, j
        if (r > l){
    	v = a[r];
    	[i, j] = [l - 1, r]
    	while (true){
    	    i += 1; while (a[i] < v) i += 1
    	    j -= 1; while (a[j] > v) j -= 1
    	    if (j <= i) break;
    	    [a[i], a[j]] = [a[j], a[i]]
    	}
    	[a[i], a[r]] = [a[r], a[i]]
    	quicksort(a, l, i - 1)
    	quicksort(a, i + 1, r)
        }
    }
    var count = 0
    var a = lst
    quicksort(a, 0, a.length -1)
    puts(count)
    return a
}
var lst = [ 1,2, 3, 6, 8]
puts(f(lst))

実際に求めたい出力結果の例が以下のとおりです．
f([4,3,2,1]) = 8
f([2,3,2,1]) = 6
f([1,2,3,6,8]) = 0
f([9,1,2,3,6]) = 8
f([1,1,1,1,1]) = 0

Comments

[yambejp]

f([2,3,2,1]) = 6
f([9,1,2,3,6]) = 8
の根拠がよくわかりません。
ズレの総和とはどういうロジックなのでしょうか？

[Q3fdxrGzWzu0u5n]

例えば，lst = [4,3,2,1]でしたら，4を右に3，3を右に1，2を左に1，1を右に3動かすため，それぞれ足して，8となります．

Answer 1

こんにちは

一案としまして、以下のような感じになるかと思います。

const f = (lst) => {

  const lstSorted = [...lst].sort((v1, v2) => v1 - v2);
  
  const sum = lst.reduce((s, v, i) => {
    const j = lstSorted.indexOf(v);
    lstSorted[j] = NaN;
    return s + Math.abs(i - j);
  }, 0);
  
  return sum;
};

• 動作確認用サンプル: https://codepen.io/jun68ykt/pen/pogxBGy

追記1

上記の回答コードでは、引数で与えられた lst(のコピー)をソートした lstSorted を得るために javascript標準の sort メソッドを使って

const lstSorted = [...lst].sort((v1, v2) => v1 - v2);

としていますが、Q3fdxrGzWzu0u5nさんが自作されたquicksortを使えば、以下の二行

const lstSorted = [...lst];
quicksort(lstSorted, 0, lstSorted.length -1)

によっても得られます。

追記2

別案を挙げます。

与えられた配列 lst が例えば [40, 30, 20, 10] だった場合に、この配列のコピーをソートするのではなく、lst の要素とインデクスを並べた、長さ2の配列を要素とする配列

[ [40, 0], [30, 1], [20, 2], [10, 3] ]

を作り、この配列を各要素の先頭の値で昇順ソートすると以下が得られます。

[ [10, 3], [20, 2], [30, 1], [40, 0] ]

上記の配列を使うと、各要素の移動量の計算は、各要素の配列の二番目に入っているソート前のインデクスと、ソート後の配列の各要素それ自体のインデクスの差から求めることができます。以下はこの考え方による f(lst) です。

const f = lst => 
  lst.map((v, i) => [v, i])
     .sort(([v1],[v2]) => v1 - v2)
     .reduce((s, [v, i], j) => s + Math.abs(i-j), 0);

• 動作確認用サンプル: https://codepen.io/jun68ykt/pen/oNbQjgv

Answer 2

ソート前の配列からソート後の配列を引いて絶対値を足して行けば良いのでは？
ただし、単に配列を新しい変数に代入しただけだと、2つの変数の中身が同じものになってしまうのでコピーする必要があります。

var s=0;
var a=lst.concat();  //値をコピー

quicksort(a, 0, a.length -1)
for(var i =0;i<lst.length;i++)
  s+=Math.abs(lst[i]-a[i]);

console.log(s);