JSでソートを知る

はじめに

ｉｉｍｏｎ新卒エンジニアのかとうです 🥕

大学時代苦手だった配列のソートにもう一度向き合うため、ソートについてまとめた記事です。まず、ソートについて理解して、JavaScriptでの実装を試みます。

ここでは、基本的なソートアルゴリズムについての内容を扱い、計算量などについては触れていません。

ソートとは

---

ソートとは、一連の手順を繰り返すことで配列内の要素を順序づけて並べ替えることです。ソートアルゴリズムを使用して配列の要素を並び替えることで、配列を扱いやすくすることができます。

例えば、数字の配列を昇順にソートすると、値の小さい要素が大きい要素よりも左側に配置されます。

// ソート前
[ 10, 7, 8, 1, 5 ]
// ソート後
[ 1, 5, 7, 8, 10 ]

基本のソートアルゴリズム

---

選択ソート

ソートされていない範囲から最小または最大の要素を繰り返し選択し、ソートされていない範囲の最初の要素と交換することで要素を並び替えます。

// 最小値1と未ソート範囲先頭の10を交換
[ 10, 7, 8, 1, 5 ]
// 未ソート範囲最小値5と未ソート範囲先頭7を交換
[ 1, 7, 8, 10, 5 ]
// 7と8
[ 1, 5, 8, 10, 7 ]
// 8と10
[ 1, 5, 7, 10, 8 ]
// ソート完了
[　　1, 5, 7, 8, 10　　]

バブルソート

隣り合う要素の順序が期待通りでない場合、それらの要素を繰り返し入れ替える単純なソート方法です。

クイックソート

配列から基準値となる要素を決定し、基準値以上と基準値未満の二つのグループに分割する処理を繰り返し行います。

基準値の選び方の例

• 最初の要素
• 最後の要素
• ランダムな要素
• 中央の要素

JavaScriptでソートする

JSには、配列の要素をソートするメソッドが用意されています。

sort()

---

sort()メソッドは配列の要素をソートし、その結果で元の配列を上書きします。元の配列は保持されません。undefinedの要素は全て配列の末尾に配置されます。

引数としてソート順を定義する関数compareFnを与えることで、ソート方法を設定することができます。引数がない場合、デフォルトで要素を文字列に変換し、UTF-16によって比較して昇順に並べ替えます。

仕組み

sort()メソッドは、バブルソート、クイックソートなどさまざまなソートアルゴリズムを適用して配列をソートします。アルゴリズムの選択は、ブラウザ、配列のサイズ、ソートされるデータ型によって異なります。主にクイックソートが使用されるようです。

他にもさまざまな意見がありました （ Javascript Array.sort implementation? ）

デフォルトでの使用

文字列要素のソート

const fruits = [ 'りんご', 'いちご', 'もも', 'ばなな' ];
const sortedArray = fruits.sort();
console.log(fruits); // [ 'いちご', 'ばなな', 'もも', 'りんご' ]
console.log(sortedArray); //  ["いちご", "ばなな", "もも", "りんご"]

数値要素のソート

const numbers = [ 2, 4, 200, 25, 1 ];
const sortedArray = numbers.sort();
console.log(numbers); // [ 1, 2, 200, 25, 4 ]
console.log(sortedArray); // [ 1, 2, 200, 25, 4 ]

toSorted()

---

元の配列を保持するtoSort()メソッドもあります。このメソッドは、配列の要素をソートした結果の新しい配列を返します。

デフォルトでの使用

数値要素のソート

const numList = [2, 4, 200, 25, 1];
const sortedNumList = numList.toSorted();
console.log(numList); // [ 2, 4, 200, 25, 1 ]
console.log(sortedNumList);　// [ 1, 2, 200, 25, 4 ]

これらのソートメソッドの使用方法では、数値要素が期待通り昇順で並んでいません😔😵‍💫

sort()による数値比較の仕組み

---

sort()メソッドは、デフォルトで対象の要素をUTF-16のエンコード形式で表現して数値を比較します。

たとえば、配列 [ 2, 4, 200, 25, 1 ] の場合、要素は以下のように変換されます。

文字列	UTF-16
2	0032
4	0034
200	0032 0030 0030
25	0032 0035
1	0031

比較の流れ

1. 先頭のコードユニットから比較します（コードユニットとは、25: 0032 0035の場合、0032、0035ごとの単位）
2. 先頭のコードユニットが同じ場合、次のコードユニットを比較します
3. 比較したコードユニットに順序をつけることができた場合、コードユニットの比較を終了します

数値の配列をソートする場合、200の最後のコードユニットが考慮されず、2つ目のコードユニットで比較が終了します。すべてのコードユニットを比較しないので、200と25を比べた時に [ 200, 25 ] と並べられてしまいます🙃🙃

数値を昇順で並べる方法

---

sort()メソッドの引数に比較関数compareFn(a, b)を与えることで、配列 [ a, b ] のソート順を定義することができます。

compareFn(a, b)を以下のように設置します。

比較結果	返り値	ソート結果
a < b	負	[ a, b ]
a > b	正	[ b, a ]
a === b	0	[ a, b ]（順序維持）

使用例

const numberArray = [ 2, 4, 200, 25, 1 ];
function ascendFn(a, b) {
  return a - b;
}

function descendFn(a, b) {
    return b - a;
}

numberList.sort(ascendFn); // 昇順
console.log(numberArray); // [ 1, 2, 4, 25, 200 ]

numberList.sort(descendFn); // 降順
console.log(numberArray); // [ 200, 25, 4, 2, 1 ]

ソートメソッドなしでソートする

JSのメソッドsort()、toSorted()を使用せずに配列を並べ替えてみます！

目的：数値の配列を昇順に並べる

方法：バブルソート、クイックソート

使用する構文

---

分割代入

分割代入とは、配列から値を取り出して、別の変数に代入することを可能にするJSの構文です。分割代入を使用することで、一時変数を使用せずに2つの値を入れ替えることができます。

一時変数の使用

const arr = [ 1, 30, 100 ];
const temp = arr[2]; // 一時変数
arr[2] = arr[1];
arr[1] = temp;
console.log(arr); // [ 1, 100, 30 ]

分割代入の使用

const arr = [ 1, 30, 100 ];
[arr[2], arr[1]] = [arr[1], arr[2]];
console.log(arr); // [ 1, 100, 30 ]

バブルソート

---

左から隣り合う要素を比較し、左側の要素が大きい場合、2つの要素の入れ替えを行います。要素の交換が行われなかった場合、ソートを終了することで最適化しています。

function bubbleSort(arr) {
    let swapped;
    for (let i = 0; i < arr.length - 1; i++) {
        swapped = false;
        for (let j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        if (!swapped) break; // 要素の交換がないとき、配列のソート完了
    }
    return arr;
}

const array = [ 10, 7, 8, 1, 5 ];
console.log(array); // [ 10, 7, 8, 1, 5 ]
bubbleSort(array); // バブルソート
console.log(array); // [ 1, 5, 7, 8, 10 ]

配列要素の動き

[ 10, 7, 8, 1, 5 ]

i = 0
[ 10, 7, 8, 1, 5 ]
[ 7, 10, 8, 1, 5 ]
[ 7, 8, 10, 1, 5 ]
[ 7, 8, 1, 10, 5 ]

i = 1
[ 7, 8, 1, 5, 10 ]
[ 7, 8, 1, 5, 10 ]
[ 7, 1, 8, 5, 10 ]

i = 2
[ 7, 1, 5, 8, 10 ]
[ 1, 7, 5, 8, 10 ]

i = 3
[ 1, 5, 7, 8, 10 ]

// ソート完了
[ 1, 5, 7, 8, 10 ]

クイックソート

---

配列の中から基準値を選択し、残りの要素を基準により大きい配列グループと、小さい配列グループに分けます。これを配列グループの要素が1つになるまで繰り返します。

/**
 * 配列を基準値を用いて分割し、基準値の正しい位置を決定します
 * @param {number[]} arr - ソート対象の配列
 * @param {number} low - 分割の開始インデックス
 * @param {number} high - 分割の終了インデックス
 * @returns {number} 基準値の正しい位置のインデックス
 */
function partition(arr, low, high) {
    const pivot = arr[high]; // 基準値の決定
    let i = low - 1; // 基準値より小さい要素の最後のインデックスを追跡
    
    for (let j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
}

/**
 * クイックソートアルゴリズムを用いて配列をソートします
 * @param {number[]} arr - ソート対象の配列
 * @param {number} low - ソートの開始インデックス
 * @param {number} high - ソートの終了インデックス
 */
function quickSort(arr, low, high) {
    if (low < high) {
        const pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

const array = [ 10, 7, 8, 1, 5 ];
console.log(array); // [ 10, 7, 8, 1, 5 ] 
quickSort(array, 0, array.length - 1);
console.log(array); // [ 1, 5, 7, 8, 10 ]

コードの説明

1回目のquickSort

対象の配列：array = [ 10, 7, 8, 1, 5 ]

1. quickSort(array, 0, array.length - 1)
2. 基準値pivot は 5 （arr[4]）
3. i = -1 に初期化
4. for ループ j = 0 から j = 3 まで実行
   • j = 0 ：arr[0] は 10 で、10 < 5 は false
   • j = 1 ：arr[1] は 7 で、7 < 5 は false
   • j = 2 ：arr[2] は 8 で、8 < 5 は false
   • j = 3 ：arr[3] は 1 で、1 < 5 は true
   • このとき i = 0 になり、arr[0] と arr[3] を交換して基準値を正しい位置に移動
5. 配列： [ 1, 7, 8, 10, 5 ]
6. 交換した要素の隣 arr[i + 1] と arr[high] を交換
7. 配列 ：[ 1, 5, 8, 10, 7 ]

2回目のquickSort（基準値の左側 [ 1 ]）

対象の配列：[ 1, 5, 8, 10, 7 ]

1. quickSort(array, 0, 0)
2. low >= high なので何もしない

3回目のquickSort基準値の右側 [ 8, 10, 7 ]）

対象の配列：[ 1, 5, 8, 10, 7 ]

1. quickSort(array, 2, 4)
2. 基準値pivot は 7 （arr[4]）
3. i = 1 に初期化
4. for ループ j = 2 から j = 3 まで実行
   • j = 2 ：arr[2] は 8 で、8 < 7 は false
   • j = 3 ：arr[3] は 10 で、10 < 7 は false
   • arr[i + 1] （arr[2]）と arr[high]（arr[4]） を交換して基準値を正しい位置に移動
5. 配列： [ 1, 7, 8, 10, 5 ]
6. 交換した要素の隣 arr[i + 1] と arr[high] を交換
7. 配列 ：[ 1, 5, 7, 8, 10 ]

…

ソート完了：[ 1, 5, 7, 8, 10 ]

最後に

ここまで読んでくださり、ありがとうございます！✨

苦手だったソートに少し寄り添うことができました。今回触れなかった挿入ソート、マージソートなどの他のソートアルゴリズムや、計算時間についても調べてみたいと思いました。

この記事を読んで興味を持って下さった方がいらっしゃれば、カジュアルにお話させていただきたいです。是非ご応募をお願いいたします！

Wantedly / Green

参考

• Array.prototype.sort() - JavaScript | MDN
• Array.prototype.toSorted() - JavaScript | MDN
• 分割代入 - JavaScript | MDN
• JavaScript Sort() – How to Use the Sort Function in JS
• Sorting algorithm | Definition, Time Complexity, & Facts
• Sorting Algorithms - GeeksforGeeks
• Javascript Array.sort implementation?