[アルゴリズム] マージソートのプログラミング（JavaScript編）
「マージソートは分割統治に基づいたアルゴリズム」という説明を見かけたが、よくわかりにくかった。
でも、いくつかの説明サイトをみて、分割するフェイズと結像（統治）するフェイズを分けて考える事で理解することができた。
肝心なことは、こうしたアルゴリズムというお題をプログラミングするという事なのだが、複数言語で書くということを念頭に置いているため、
なるべく言語依存しないように書こうと努力している。
そして、一番はじめはブラウザで簡単に実行結果が得られるJavaScriptを採用しているわけだが、確実にC言語やShellでつまずく事は
間違いないだろう。
オブジェクト思考が反映されている言語とそうでない言語という分割だが、言語依存というのはそんなに間違った考え方ではない事も合わせて最近わかってきた。
そもそも、単体の言語で出来ないことと言うのはあまりなく、他の言語では簡単に書けるのにこの言語は書きにくいというレベルが多いという事。
そもそもそれを実現するのがプログラマーという職業なのかもしれないね。
ソースコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
// 分割位置の取得 function midPoint(nums){ return parseInt((nums.length / 2) + 0.5 ,10); } // condition : arr1.length >= arr2.length && array was sort function setMarge(arr1 , arr2){ var arr = []; while(arr1.length || arr2.length){ if(arr1.length == 0){ arr.push(arr2.shift()); } else if(arr2.length == 0){ arr.push(arr1.shift()); } else if(arr1[0] > arr2[0]){ arr.push(arr2.shift()); } else{ arr.push(arr1.shift()); } } return arr; } // 配列を2つに分割して２つの値の場合それをソートする function mergeSort(numbers){ if(!numbers.length){ return []; } else if(numbers.length == 1){ } else if(numbers.length == 2){ if(numbers[0] > numbers[1]){ var tmp = numbers[0]; numbers[0] = numbers[1]; numbers[1] = tmp; } } else{ var midNum = midPoint(numbers); var arr1 = numbers.slice(0 , midNum); var arr2 = numbers.slice(midNum); arr1 = mergeSort(arr1); arr2 = mergeSort(arr2); numbers = setMarge(arr1 , arr2); } return numbers; } |
実行
事前にソースコードをスクリプトコンソールで実行しておき、下記コマンドを実行することで、結果が得られます。
|
1 2 3 |
var numbers = mergeSort([20,10,2,12,7,16,8,13,1]); console.log(numbers); >> [1, 2, 7, 8, 10, 12, 13, 16, 20] |
解説
全体構成
マージソートは、解説ページせ説明している通り、1/2ずつの処理と、再帰的な分割をグルーピングしていく方法が、非常に複雑に感じる方式なのだが、
今回は３つの関数で実施している。
半分に分割関数
1つ目の関数は、半分を切り分けるだけの関数で、中間の場所を数値で返している。
ちなみに、端数は前方にくっつけるように端数繰り上げにしてある。
ソート処理
2つ目の関数は、必ずソートされている状態であることが条件の２つの分割された配列を、左側から同時に処理して、小さい方をshiftしていく方式で
理論的にソートを実現している。
全体フロー関数
3つ目の関数は、マージソートの基本フロー関数で、１つの配列グループを再帰的に処理する関数にしている。
これにより、分割された配列をそれぞれソートしてその場で返す処理を実現している。
分割 -> ソート -> マージ
|
1 2 3 4 5 6 7 |
var midNum = midPoint(numbers); var arr1 = numbers.slice(0 , midNum); var arr2 = numbers.slice(midNum); arr1 = mergeSort(arr1); arr2 = mergeSort(arr2); |
分割関数で対象配列の中間値を取得し、
sliceで実際の配列データを、分割、
mergeSort関数でそれぞれ分割された配列をソートする
という流れ。