JavaScript 配列ソート アルゴリズム: コーディング面接のチュートリアル

データのリストの並べ替えは、アプリケーションの処理において非常に重要な部分です。

データの表示や検索の実行に便利です。したがって、優れたソフトウェア エンジニアが配列の並べ替え方法を知っているのは当然のことです。この記事では、JavaScript で配列をソートするための最も一般的なアルゴリズムのいくつかについて説明します。

並べ替えとは何ですか?なぜそれが役立つのでしょうか?

並べ替えは、値を何らかの順序に従って体系的に整理することです。この順序は降順または昇順になります。 JavaScript で配列を並べ替えると、データをよりわかりやすく表示できるため便利です。

たとえば、最新のファイルを最初に並べ替えたファイルや、価格順に製品を並べ替えて表示したい場合があります。また、並べ替えられたデータでのみ機能するデータの二分検索を実行する場合にも役立ちます。

データを簡単に並べ替える関数やライブラリはありますが、インタビューのコーディングや低レベルのコードを記述する必要がある場合には、内部で並べ替えがどのように機能するかを知る必要があります。

JavaScript 配列ソートアルゴリズム

バブルソート

バブル ソートはおそらく、理解して実装するのが最も簡単なアルゴリズムです。これは、パス内で配列をループすることによって機能します。各パスで配列内を最初から最後まで移動し、隣接する 2 つの要素を比較します。要素の順序が間違っている場合は、要素を入れ替えます。

n パスを実行します。n は配列内の要素の数です。各パスで、配列は右からソートされます。数値を昇順に並べ替えるアルゴリズムの擬似コードは次のとおりです。

 1. Let n be the number of elements in the array
2. Loop n times, keeping count of the loops using i (doing the following in each loop)
   a. loop the array from the second element to the (n - i)th element
   b. if the previous element is greater than the current element, swap them.

これを JavaScript に変換すると、コードは次のようになります。

 function sort(arr) {
    const n = arr.length;

    for (let i = 0; i < n; i++) {
        for (let j = 1; j < n - i; j++) {
            if (arr[j - 1] > arr[j]) {
                const temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    
    return arr;
}

何が起こっているのかをよりよく理解するには、2 つのループ内に console.logs を追加して、各パスで配列がどのように変化するかを確認することをお勧めします。

以下のコードでは、sort 関数を変更して、2 つのループ内に console.logs を追加しました。また、sort 関数を使用して並べ替えた、並べ替えられていない小さな配列も作成しました。

 function sort(arr) {
    const n = arr.length;

    for (let i = 0; i < n; i++) {
	console.log(`Pass: ${i}`);

        for (let j = 1; j < n - i; j++) {
            if (arr[j - 1] > arr[j]) {
                const temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
	
	    console.log(arr);
        }
    }
    
    return arr;
}

const array = [9, 2, 7, 4, 1];
sort(array);

console.log(array);

上記のコードを実行した結果は次のようになります。

バブル ソートの Big O 時間計算量は O(n ^ 2) です。これは、パスごとに配列をループする n パスを実行するためです。したがって、うまく拡張できません。ただし、配列要素をその場で変更するため、空間計算量は O(1) になります。

挿入ソート

挿入ソートは、人気のある JavaScript 配列ソート アルゴリズムです。挿入ソートを使用して値を昇順に並べ替えているとします。このアルゴリズムは、番号 (num と呼びます) を選択することによって機能します。次に、num の左側にある 1 つおきの数値が num より小さくなるまで、num を左に移動します。これを 2 番目の要素から最後まで行うと、すべての数値がソートされます。以下は擬似コードでの説明です。

 1. Let n be the number of elements in the array
2. Loop i from 1 to n - 1 (start from the second element)
    a. Set currentElement to array[i]
    b. Set j to i - 1
    c. While j >= 0 and array[j] > current_element
       i. Move array[j] to array[j+1]
       ii. Decrement j by 1
    d. Set array[j+1] to current_element

そして、JavaScript で実装された疑似コードは次のとおりです。

 function insertionSort(array) {
  const n = array.length;

  for (let i = 1; i < n; i++) {
    const currentElement = array[i];
    let j = i - 1;

    while (j >= 0 && array[j] > currentElement) {
      array[j + 1] = array[j];
      j -= 1;
    }

    array[j + 1] = currentElement;
  }

  return array;
}

バブルソートと同様に、 console.logs 追加すると、何が起こっているかを視覚化するのに役立ちます。以下のコード スニペットは、挿入ソートが機能していることを示しています。

 function sort(array) {
    const n = array.length;

    for (let i = 1; i < n; i++) {
        const currentElement = array[i];
        let j = i - 1;
        console.log("Placing element:", currentElement);

        while (j >= 0 && array[j] > currentElement) {
            array[j + 1] = array[j];
            j -= 1;
        }

        array[j + 1] = currentElement;
        console.log("Placed it at position:", j + 1);
        console.log(array);
    }

    return array;
}

const array = [4, 1, 2, 5, 3];
sort(array);

上記のスニペットを実行すると、次の結果が得られます。

マージソート

挿入ソートとバブル ソートは二次時間でスケールしますが、マージ ソートは準線形時間でスケールします。時間計算量は O(n * log(n)) です。

マージソートは分割統治戦略を利用します。配列は、それぞれ 1 要素の小さな配列に繰り返し分割されます。分割後、それらは再びマージされます。

分割は再帰的であるため、後で配列を再構築できます。

配列をマージして戻す場合、サブ配列は順番にマージされます。マージは、ソートされた配列をマージする場合と同じ方法で行われます。これを行うための疑似コードを以下に示します。

 1. If the length of the array is 1 or less, return the array (base case)
2. Find the middle index:
   a. Set mid to the floor of (length of the array / 2)
3. Divide the array into two subarrays:
   a. Create leftArray and copy the first half of the array into it (from index 0 to mid)
   b. Create rightArray and copy the second half of the array into it (from index mid+1 to the end)
4. Recursively call MergeSort on leftArray
5. Recursively call MergeSort on rightArray
6. Merge the two sorted subarrays:
   a. Create an empty resultArray
   b. While both leftArray and rightArray are not empty:
      i. If the first element in leftArray is less than or equal to the first element in rightArray, append it to resultArray
      ii. Otherwise, append the first element in rightArray to resultArray
   c. Append any remaining elements in leftArray to resultArray (if any)
   d. Append any remaining elements in rightArray to resultArray (if any)
7. Return resultArray

これを JavaScript で実装すると、次のようになります。

 function sort(array) {

	// Base case in which we stop subdividing the array
	if (array.length == 1) {
		return array;
	}

	// Finding the middle point of the array
	const m = Math.round(array.length / 2);

	// Divide the array into two halves
	const leftUnsorted = array.slice(0, m);
	const rightUnsorted = array.slice(m);

	// Recursively call merge sort
	const leftSorted = sort(leftUnsorted);
	const rightSorted = sort(rightUnsorted);

	// Return a merged sorted array
	return merge(leftSorted, rightSorted);
}

function merge(left, right) {
	// Merge two sorted lists
	let result = [];
	let leftIndex = 0;
	let rightIndex = 0;

	while (leftIndex < left.length && rightIndex < right.length) {
		if (left[leftIndex] < right[rightIndex]) {
			result.push(left[leftIndex]);
			leftIndex += 1;
		} else {
			result.push(right[rightIndex]);
			rightIndex += 1;
		}
	}

	return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}

サンプル配列を使用してコードを実行すると、機能するはずです。

クイックソート

マージ ソートと同様に、クイック ソートは分割統治戦略に依存しています。アルゴリズムはピボット要素を選択します。次に、ピボットより大きいすべての要素を右側に移動し、ピボットより小さい要素を左側に移動します。これが完了すると、ピボットは正しい位置に配置されます。

ピボットを中心に要素を移動するには、アルゴリズムはまずピボットを配列の末尾に移動します。

移動した後、ポインターを使用して配列の左からループし、ピボットより大きい最初の数値を探します。同時に、配列の右側から別のポインター ループを使用して、ピボットより小さい最初の数値を探します。両方の番号が特定されたら、それらを交換します。この手順は、左からのポインタが右へのポインタよりも大きくなるまで繰り返されます。

停止すると、ピボットと最後に交換された 2 つの数値のうち大きい方を交換します。この時点で、ピボットは正しい位置にあります。ピボットより小さい数値は左側にあり、大きい数値は右側にあります。

この手順は、サブ配列の要素が 1 つだけ残るまで、ピボットの左右のサブ配列に対して再帰的に繰り返されます。

クイックソートの疑似コードは次のとおりです。

 1. If lessThanPointer is less than greaterThanPointer:
    a. Choose a pivot element from the array
    b. Move elements such that elements less are to the left and elements greater are to the right:
    c. Recursively call Quicksort on leftSubarray
    d. Recursively call Quicksort on rightSubarray

そしてそれを JavaScript に変換します。

 function sort(array, low, high) {
    if (low < high) {
        // Choose the pivot index and partition the array
        const pivotIndex = move(array, low, high);

        // Recursively sort the subarrays to the left and right of the pivot
        sort(array, low, pivotIndex - 1);
        sort(array, pivotIndex + 1, high);
    }
}

function move(array, low, high) {
    // Select the pivot element (in this case, the last element)
    const pivotElement = array[high];

    // Initialize the index for the smaller element
    let i = low - 1;

    for (let j = low; j < high; j++) {
        // If the current element is less than or equal to the pivot, swap it with the element at index i+1
        if (array[j] <= pivotElement) {
            i += 1;
            const temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

    // Swap the pivot element into its correct position
    const temp = array[i];
    array[i] = array[j];
    array[j] = temp;

    // Return the index of the pivot element
    return i + 1;
}

Node.js のクイック ソートを使用してサンプル配列を並べ替えると、次の結果が得られます。

最良の場合、クイックソートは準線形時間計算量で実行されます。クイック ソートでのスペース使用量も対数的に増加します。したがって、他の JavaScript 配列ソート アルゴリズムと比較して比較的効率的です。

コーディング面接のヒント

❇️練習が大切です。さまざまなアルゴリズムを学ぶのに役立ちますが、さらに重要なのは、問題解決と計算的思考のスキルを開発するのに役立ちます。 Leetcode や AlgoExpert などのプラットフォームで練習することもできます。

❇️ まずは問題を解決してみてください。すぐに解決策に飛びつくのではなく、問題を解決するスキルを身につけるのに役立つので、解決してみてください。

❇️ 問題に時間がかかりすぎる場合は、すぐに解決策に進みます。解決策から問題の解決方法を学ぶことはできます。ほとんどの学習プラットフォームはソリューションを提供しています。 ChatGPT や Google Bard も概念を説明するのに役立ちます。

❇️ また、すぐにコードを書かないでください。コードを書く前に、解決策をホワイトボードに書いてよく考えてください。疑似コードは、アイデアを素早く書き留めるのにも便利な方法です。

結論

この記事では、最も一般的な並べ替えアルゴリズムについて説明しました。ただし、これをすべて学ぶのは最初は大変に思えるかもしれません。したがって、私は通常、1 つのソースだけに依存するのではなく、さまざまなソースを混合することをお勧めします。コーディングを楽しんでください!

次に、Python のsorted関数を理解することを確認してください。