配列の知識と技術(2)

　配列は、要素を配列にすることも可能です。要素が配列である配列を二次元配列と呼び、さらに要素の子要素が配列であれば三次元配列と呼びます。これらは、一般に、多次元配列と総称されます。この時、各要素には、［］ を次元分だけ追記してアクセスすることが可能です。

// JavaScript Source
var a = new Array(3);
a[0] = new Array("D1", "D2", "D3", "D4");
a[1] = new Array("B1", "B2", "B3");
a[2] = new Array("C1", "C2", "C3", "C4", "C5");
a[0][0] = "D8";
a[1][1] = "B9";
a[2][4] = "C7";
var n;
n = a.length;                 // = 3
n = a[0].length;             // = 4
n = a[1].length;             // = 3
n = a[2].length;             // = 5
var s;
s = a.toString();            // = "D8,D2,D3,D4,B1,B9,B3,C1,C2,C3,C4,C7"
s = a[0].toString();        // = "D8,D2,D3,D4"
s = a[1].toString();        // = "B1,B9,B3"
s = a[2].toString();        // = "C1,C2,C3,C4,C7"

a.sort();                       // ソート → 各配列の先頭要素が比較される
s = a.toString();            // = "B1,B9,B3,C1,C2,C3,C4,C7,D8,D2,D3,D4"
s = a[0].toString();        // = "B1,B9,B3"
s = a[1].toString();        // = "C1,C2,C3,C4,C7"
s = a[2].toString();        // = "D8,D2,D3,D4"

　添え字には、数字の代わりに文字列を指定することもできます。添え字に文字列を持つ配列を連想配列と呼びます。これには、Array オブジェクト、Object オブジェクトを利用します。また、｛｝ で囲むつくり方もあります。
　いずれも、添え字に文字列を設定した時は、代わりに数字を指定することはできません。undefined を返すか、エラーとなりプログラムがストップします。ただし、両者を混在させることは可能です。

// JavaScript Source
var a = new Array();
a["春"] = "Spring";
a["夏"] = "Summer";
a["秋"] = "Autumn";
a["冬"] = "Winter";
var n = a.length;        // = 0 : 長さは0となる
var s;
s = a[0];                   // エラー
s = a["春"];              // = "Spring"

var a = new Object();
a["春"] = "Spring";
a["夏"] = "Summer";
a["秋"] = "Autumn";
a["冬"] = "Winter";

var a = {春 : "Spring", 夏 : "Summer", 秋 : "Autumn", 冬 : "Winter"};
var n = a.length;        // = 0
var s = a["夏"];         // = "Summer"

　クイックソートは高速で並べ替えを行う技術の一つです。ただし、要素数が少ない時は効果は希薄です。大量のデータを処理する際（JavaScriptではあまりありませんが）に使われます。
　クイックソートでは、まず基準値を算出します。これには中間値が望ましいのですが、簡易的には、任意の二つないし三つの値の平均を取ることが多いようです。そして、基準値より大きい値を先頭から、小さい値を末尾から探して、見つかったら二つの値を交換します。これを交換すべき要素がなくなる（ = 両者が交錯する）まで繰り返していくと、基準値より小さいグループが前方に、大きいグループが後方に集まります。（右図参照）
　さらにグループごとに同様の処理を繰り返していく（再帰処理）ことで、すべての要素の並べ替えが実現します。

// JavaScript Source
// クイックソート関数（昇順）
// ... array : 対象配列, start : 開始インデックス, end : 終了インデックス
function QSort(array, start, end) {
    var i = start;
    var j = end;
    var nBase = Math.floor((array[start] + array[end]) / 2);    // 基準値（平均を適用）
    while (1) {
        while (array[i] < nBase) i++;    // 基準値より大きい値を先頭から探す
        while (array[j] > nBase) j--;    // 基準値より小さい値を末尾から探す
        if (i >= j) break;                     // 両者が交錯していたら抜ける
        var e = array[i];                     // 交錯していなければ値を交換
        array[i] = array[j];
        array[j] = e;
        i++;            // 交換した一つ後に添え字を進める
        j--;            // 交換した一つ前に添え字を進める
    }
    if (start < i - 1) QSort(array, start, i - 1);    // 基準値より小さいグループの再帰処理
    if (end > j + 1)  QSort(array, j + 1, end);      // 基準値より大きいグループの再帰処理
}

// --------------------------
// 要素数50個の配列を作成
var a = new Array(50);
for (i=0; i<a.length; i++) a[i] = Math.floor(Math.random() * 100);

// ソート前の要素を表示
var s = "";
for (i=0; i<a.length; i++) s += a[i].toString() + ", ";
document.Form3.Text3a.value = s;

// クイックソート
QSort(a, 0, a.length-1);

// ソート後の要素を表示
s = "";
for (i=0; i<a.length; i++) s += a[i].toString() + ", ";
document.Form3.Text3b.value = s;

<!-- HTML Source -->
<form name="Form3" style="margin:1ex">[ ソート前 ]<br>
    <textarea name="Text3a" rows="3" cols="70" style="font-size:12px"></textarea>
    <br>[ ソート後 ]<br>
    <textarea name="Text3b" rows="3" cols="70" style="font-size:12px"></textarea>
</form>