Blog#102: マージソートをマスターする：JavaScriptで配列をソートするガイド

こんにちは、私は東京からのフルスタックWebデベロッパーであるTUANです。

今後の便利で面白い記事を見逃さないように、私のブログをフォローしてください。

データソートはコンピュータサイエンスの基本的な概念であり、配列をソートする方法を学ぶことは、自分のコーディングスキルを向上させるための重要なステップです。最も人気のあるソートアルゴリズムの1つは「マージソート」と呼ばれており、この記事では、その動作方法と、自分のJavaScriptプロジェクトでそれを使用する方法についてもう少し深く見ていきます。

マージソートとは

マージソートは、要素の配列を小さな部分配列に分割するアルゴリズムです。それらの部分配列は個別にソートされ、最終的に、部分配列はソートされた配列に戻されます。

このアルゴリズムが「マージソート」と呼ばれる理由は、小さな部分配列を単一のソートされた配列に結合するために「マージ」と呼ばれるプロセスを使用するからです。このプロセスは再帰的に繰り返され、配列をより小さい部分に分解し、各部分配列には1つの要素しか含まれていないようになります。

マージソートを使用する上での主な利点は、O(n * log n)のタイムでn個の要素をソートすることが保証されるということで、バブルソートや挿入ソートのような他のソートアルゴリズムより効率的であるということです。

JavaScriptでマージソートを使う方法

マージソートの基本的な考え方を理解したので、JavaScriptでどのように実装するか見ていきましょう。基本的な実装の例を示します。

function mergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }

  let middle = Math.floor(arr.length / 2);
  let left = arr.slice(0, middle);
  let right = arr.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

この例では、2つの関数があります：mergeSortとmerge。mergeSort関数は配列を入力として受け取り、再帰を使ってそれを小さな部分配列に分解します。merge関数は2つのソート済みの部分配列を取り、単一のソート済み配列に戻します。

使用例

JavaScriptでマージソートを実装する方法を学んだので、それを使用する実際の例を見ていきましょう。

1. 名前のリストをソートする

アルファベット順にソートする必要がある名前のリストを扱う場合、マージソートを使用することで迅速かつ効率的に行うことができます。例を示します。

let names = ["Alice", "Bob", "Charlie", "David", "Eve"];
console.log(mergeSort(names)); 
// Output: ["Alice", "Bob", "Charlie", "David", "Eve"]

2. 数字のリストをソートする

昇順または降順にソートする必要がある数字のリストを扱う場合、マージソートを使用することで実現できます。これは、数字のリストを昇順にソートする方法の例です。

let numbers = [4, 2, 5, 1, 3];
console.log(mergeSort(numbers)); 
// Output: [1, 2, 3, 4, 5]

3. オブジェクトのリストをソートする

マージソートは、特定のプロパティに基づいてオブジェクトのリストをソートするためにも使用できます。人々に関する情報を持つオブジェクトのリストを姓によってソートする方法の例を示します。

let people = [
  {firstName: "John", lastName: "Doe"},
  {firstName: "Jane", lastName: "Smith"},
  {firstName: "Bob", lastName: "Johnson"}
];

function compare(a, b) {
  if (a.lastName < b.lastName) {
    return -1;
  }
  if (a.lastName > b.lastName) {
    return 1;
  }
  return 0;
}

console.log(mergeSort(people, compare));
/* Output: 
[ { firstName: 'Bob', lastName: 'Johnson' },
  { firstName: 'John', lastName: 'Doe' },
  { firstName: 'Jane', lastName: 'Smith' } ]
*/

4. カスタムデータ構造のリストをソートする

文字列や数字のような単純なデータ型だけでなく、マージソートはリンクリストやバイナリツリーのようなカスタムデータ構造をソートするためにも使用できます。リンクリストをソートする方法の例を示します。

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  //.. push, mergeSort(linkedlist) methods
}
let list = new LinkedList();
list.push(5);
list.push(2);
list.push(4);
list.push(1);
list.push(3);
list = mergeSort(list);
//.. traversing through linkedlist

5. 大量のデータをソートする

マージソートの保証された時間複雑度がO(n * log n)なので、大量のデータをソートするために適しています。そのためビッグデータやデータサイエンスアプリケーションに使用するのに適しています。

let largeData = Array.from({length: 1000000}, () => Math.floor(Math.random()*100000))
console.log("Before Sort: ", largeData.slice(0,5));
largeData = mergeSort(largeData);
console.log("After Sort: ", largeData.slice(0,5));

結論

マージソートは、強力で効率的なソートアルゴリズムであり、数字や文字列の配列から、リンクリストやバイナリツリーのような複雑なデータ構造に至るまで、幅広いデータ型をソートするために使用できます。マージソートの主要な利点はO(n * log n)の保証された時間複雑度であり、大量のデータをソートするために適しています。このガイドと例を使用して、自分のJavaScriptプロジェクトでマージソートを実装し、自分のコーディングスキルを向上させるための知識を持っていることになります。

いつものように、この記事を楽しんで新しいことを学んでいただけたと思います。

ありがとうございました。次の記事でお会いしましょう！

この記事が気に入ったら、いいねをして購読してサポートしてください。ありがとうございます。