[アルゴリズム]ソートアルゴリズム

14705 ワード

私がJavaScriptを勉強するとき、まず実現しなければならないのはソート関数です.ほとんどの言語のようにJavascriptでもソートに使う方法がありますが、ソートの仕方を自分で理解して実現できれば、言語開発の勉強に役立つと思います.実際,数日の思考と試みを経て,自分で作成したソート関数は二重for文の理解度を高めることができる.私が作成したソート関数がどんなアルゴリズムなのか分からなかったが、ブールソートアルゴリズムでソートが実現されたことに気づいた.
ソートアルゴリズムは学習アルゴリズムの最も基本的なアルゴリズムの一つである.だからアルゴリズムを勉強するときは、勉強しなければなりません.上述したように,組み込み手法を用いて簡単に並べ替えが可能であるが,最も基本的なアルゴリズムであるため,方法がなくても自分で実現できるはずであると考える.そこで,今回は3つの最も基本的なソートアルゴリズムを位置決めする.

ソートアルゴリズムとは?


まず、ソートアルゴリズムはウィキペディアによって定義されます.
ソートアルゴリズム(sortingalgorithm)は、番号順や辞書順などの要素を一定の順に並べたアルゴリズムです.有効なソートは、ナビゲーションやマージアルゴリズムなどの他のアルゴリズムを最適化するために重要です.また、ソートアルゴリズムは、通常、データの正規化または有意義な結果の生成に用いられる.アルゴリズムの結果は、次の2つの条件を満たす必要があります.
1.出力は降順ではありません(各要素は前の要素と比較して前の要素の順序より小さくありません).
2.出力は入力を並べ替えたものです.
ソートはプログラミングでよく使われるアルゴリズムです.そこで,多様なアルゴリズムを設計した.Bubble、ソートアルゴリズムの選択、挿入について説明します.

バブルソートアルゴリズム


Bubbleソートアルゴリズムは、隣接するデータを比較ソートするアルゴリズムです.前のデータが後のデータより大きい場合は、シフトで行います.常に2つの隣接するデータを比較することによって大きなデータが後方に送信されるため,ループごとに最大のデータが最後のデータとなる.

Bubbleソートアルゴリズムは,時間的複雑さがO(n^2)であるため,性能はよくないが実現しやすく,一般的なソートアルゴリズムである.
Javascriptを使用してバブルソートアルゴリズムを実装します.
const bubbleSort = array => {
  let temp = 0;
  for (let i = 0; i < array.length - 1; i++) {
    for (let j = 0; j < array.length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
};

console.log(bubbleSort([5,4,3,2,1]));

ソートアルゴリズムの選択


選択ソートは、その場ソートアルゴリズムです.ソートアルゴリズムを選択する方法は次のとおりです.
  • 配列を参照して、最小のデータを検索します.
  • は、そのデータを先頭のデータに置き換えます.
  • の最初の位置を除いた他のデータは、同じ方法で置き換えられる.

  • 泡配列と同様に時間複雑度はO(n^2)であった.性能はよくありませんが、小数点以下の配列には有効です.また、選択ソートは常にBubbleソートよりも優れています.
    以下に示すように、JavaScriptコードとして選択ソートアルゴリズムを実装します.
    const selectionSort = array => {
      let minIdx = 0;
      let temp = 0;
      for (let i = 0; i < array.length - 1; i++) {
        minIdx = i;
        for (let j = i + 1; j < array.length; j++) {
          if (array[j] < array[minIdx]) {
            minIdx = j;
          }
        }
        temp = array[minIdx];
        array[minIdx] = array[i];
        array[i] = temp;
      }
      return array;
    };
    
    console.log(selectionSort([5,4,3,2,1]));

    ソートアルゴリズムの挿入


    挿入ソートアルゴリズムは、資料配列のすべての要素を前から順にソートされた配列部分と比較し、自分の位置を見つけて挿入することで、ソートを完了するアルゴリズムです.
    各シーケンスには、相手のカードをソートする方法と同様に、要素を挿入できる位置が見つかり、その位置に配置されます.新しいカードを既存のソート済みカードの間の正しい位置に挿入します.この操作を繰り返す回数が、挿入する新しいカードの数と同じであれば、カード全体がソートされます.
    挿入ソートは2番目のデータから始まり、前(左)のデータと比較して挿入位置を指定し、データを1つ後ろに移動して挿入します.

    挿入ソートは、k回目の繰り返し後、最初のk要素がソート順に表示されるソートの選択と同様です.ただし、選択ソートの違いは、残りのすべての要素を検索してk+1要素を検索し、挿入ソートはk+1要素を配置するのに必要な任意の数の要素のみを検索するため、実行効率が高いことです.
    挿入ソートアルゴリズムをjavascriptで次のように実現します.
    const insertionSort = array => {
        let temp = 0;
        let j = 0;
        for (let i = 1; i < array.length; i++) {
            temp = array[i];
            for (j = i - 1; j >= 0 && temp < array[j]; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = temp;
        }
        return array;
    };
    console.log(insertionSort([5,4,3,2,1]));
    

    の最後の部分


    今回の報告では,3つの最も基本的な並べ替えアルゴリズムについて議論した.実際のソートアルゴリズムにはいろいろありますが、私が理解できる範囲はまだ多くなく、最も基本的なものに位置づけるしかありません.
    これらの基本アルゴリズムは性能が悪く、ビッグデータのソートには使用されません.しかし,資料が少なければ,他の高度なソートアルゴリズム(Quick,マージ)よりも効率的である.
    まず,必要に応じて使用できるソートアルゴリズムを把握したので,より多くのデータを処理できるソートアルゴリズムを引き続き学習する.ある日自己理解と実現ができれば,残りのソートアルゴリズムを公表すべきである.

    リファレンス


    ウィキペディア-ソートアルゴリズム
    ウィキペディア-バブルソートアルゴリズム
    ウィキペディア-ソートアルゴリズムの選択
    Wikipedia-ソートの挿入
    https://www.zerocho.com/category/Algorithm