9.6K 279 180

Published Jan 15th, 10:08 a.m. 0 min read

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

この記事の主な目的は、日本語レベルを上げるのを手伝うことです。ソフトウェア開発に関連する概念や知識なとを紹介するために簡単な日本語を使います。ITの知識に関しては、インターネット上でもっとよく説明されているかもしれませんが、この記事の主な目標はまだ日本語を学ぶことです。

こんにちは、私はトゥアンと申します。東京からフルスタックWeb開発者です。将来の有用で面白い記事を見逃さないように、私のブログをフォローしてください。

データソートはコンピュータサイエンスの基本的な概念であり、配列をソートする方法を学ぶことは、自分のコーディングスキルを向上させるための重要なステップです。最も人気のあるソートアルゴリズムの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プロジェクトでマージソートを実装し、自分のコーディングスキルを向上させるための知識を持っていることになります。

最後

いつもお世話になっています。この記事を楽しんで、新しいことを学べたら嬉しいです。

次の記事でお会いしましょう！この記事が気に入ったら、私を応援するために「いいね！」を押して登録してください。ありがとうございました。