JavaScriptでソートしましょう🔢

そこには、迅速な並べ替え、マージソート、挿入ソート、バブルソートなどのさまざまな並べ替えのアルゴリズムは、その日の生活に私たちの日に役立つことができるように、生産に出荷されるコードを書くなど.それらのすべてを知る必要はありませんが、それぞれの基本的な理解を持っている場合は、あなたのシナリオのための最も効率的な1つを決定することができます.

導入

suboptimal sortアルゴリズムを選ぶことは、より長い完了時間、コード複雑さ、または悪いことにつながるかもしれません.
我々は、ソートアルゴリズムを毎日使用する、Array.sortは昇順で配列をソートするために使用されるソートアルゴリズムの一つです.しかし、それはすべてのシナリオの解決策ではありません.
ソーティングアルゴリズムを選択するとき、複雑さを考慮する必要があります、あるいは、実行される操作(通常、Xの大きいOを読んでいるO(x)として言及される)と方法に沿ったスワップの数.それで、最も多くの使用されたもののいくつかを見直して、実行して、彼らの複雑さについて学びましょう.

バブルソート

バブルソートの作品は非常に簡単です.コレクションの最初の項目を2番目と比較します.最初のものが大きいならば、2を交換してください.ない場合は、2番目の項目に移動し、同じことを繰り返す.我々はリストの最後に到達するまで、これを繰り返す.
これまで、我々はリストの最大のアイテムをその位置で最も右側に泡立てました.リストがソートされるまで、我々は再びアイテムの残りのためにこれを繰り返します.
アクションでこれを見ましょう.

function bubbleSort(list) {
  let len = list.length;

  for(let i = len - 1; i >= 0; i--) {
    for(let j = 1; j <= i; j++) {
      if(list[j - 1] > list[j]) {
        let temp = list[j - 1];
        list[j - 1] = list[j];
        list[j] = temp;
      }    
    }  
  }

  return list;
}

bubbleSort([7, 5, 2, 3, 9, 6]); // [2, 3, 5, 6, 7, 9]

あなたが見ることができるように、このアルゴリズムは最適ではありません、実際、それは最悪のシナリオでの操作の数に関して最も重いもののうちの1つです.しかし、スワップに関しては、それが適所に分類される時から、それは最高のうちの1つです.
最悪の場合のバブルソートの複雑さは、O(N 2)であり、big O of n squareとして読みます.そこでは、nがコレクション内の項目の数です.
しかし、最高のケースシナリオ(すでにソートされたコレクション)では、O(1)はO(1)スワップである.
ケース
複雑さ
最悪ケース性能
O(N 2)比較
O(N 2)スワップ
ベストケースパフォーマンス
o ( n )比較
o ( 1 )スワップ
平均格性能
O(N 2)比較
O(N 2)スワップ

選択ソート

選択ソートは本当にバブルソートのように簡単です.リストを通過し、一番低い要素のインデックスを見つけ、一番低い要素を最初の要素と入れ替えます.最初の項目がソートされたので、すべての残りの要素についてこれを繰り返します.
アクションでこれを見ましょう.

function selectionSort(list) {
  let minIndex, temp,
      len = list.length;

  for(let i = 0; i < len; i++) {
    minIndex = i;
    for(let j = i+1; j < len; j++) {
      if(list[j] < list[minIndex]) {
        minIndex = j;
      }
    }

    temp = list[i];
    list[i] = list[minIndex];
    list[minIndex] = temp;
  }

  return list;
}

selectionSort([11, 25, 12, 22, 64]); //[11, 12, 22, 25, 64]

上の例の各繰り返しでリストをソートする方法を見てみましょう.
ソートリスト
未分類のサブリスト
最低元素
[]
[ 11 , 25 , 12 , 22 , 64 ]
11
［11］
[ 25 , 12 , 22 , 64 ]
12
[ 11 , 12 ]
[ 25 , 22 , 64 ]
22
[ 11 , 12 , 22 ]
[ 25 , 64 ]
25
[ 11 , 12 , 22 , 25 ]
［64］
64
[ 11 , 12 , 22 , 25 , 64 ]
[]
複雑さに関して、このアルゴリズムは我々が直面しているシナリオにかかわらず同じままです.比較用のo(n 2)であり、o(n)はスワップする.しかし、あなたがコードを見るならば、それは自己説明的で単純です、そして、時々、我々はちょうどそれをちょうど望みます.用語やスワップでは、バブルソートよりも小さいです.
ケース
複雑さ
最悪ケース性能
O(N 2)比較
o ( n )スワップ
ベストケースパフォーマンス
O(N 2)比較
o ( n )スワップ
平均格性能
O(N 2)比較
o ( n )スワップ

挿入ソート

これは、私がトランプをして、誰かが1つずつ彼らを手渡しているようです.私は通常、私はそれらを受け取るように私の手にそれらを置く.挿入ソートは、一度に最後のリストを1つのアイテムを構築します.これは、クイックソートやマージソートなどの競合他社に対して大きなリストに対して効率が悪いということです.
しかし、いくつかの利点があります.

簡単な実装(我々はまもなくそこに着くでしょう).

小さなデータ・セットのために

効率.

バブルまたは選択ソートより効率的な

.

は、すでにソートされたコレクションに適応的、すなわち効率的です.

場所で

.

それが受けるので、

オンライン、リストをソートすることができます.

どのように動作しているかを見ましょう.

function insertionSort(list){
  let i, len = list.length, item, j;

  for(i = 1; i < len; i++){
    item = list[i];
    j = i;

    while(j > 0 && list[j-1] > item) {
      list[j] = list[j-1];
      j--;
   }

   list[j] = item;
  }

  return list;
}

複雑さの面では、バブルのソートと最悪の場合とO(N 2)の平均ケースの両方の比較とスワップに似ています.しかし、最良の場合では、O(n)比較とO(1)スワップで本当に効率的です.
ケース
複雑さ
最悪ケース性能
O(N 2)比較
O(N 2)スワップ
ベストケースパフォーマンス
o ( n )比較
o ( 1 )スワップ
平均格性能
O(N 2)比較
O(N 2)スワップ

マージソート

マージソートは、分割と征服アルゴリズムであり、再帰的なパターンで実装されます.私たちは小さな部分にリストを破壊するまで、各部分に1つのアイテムがあります.その後、我々は一緒にそれらをマージするが、それらを比較し、順番にアイテムを置く.
本当に分かりやすいですが、アクションで見てみましょう.

function mergeSort(list) {
   let len = list.length;
   if(len < 2)
      return list;
   let mid = Math.floor(len/2),
       left = list.slice(0,mid),
       right =list.slice(mid);

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

function merge(left, right) {
  let result = [],
      lLen = left.length,
      rLen = right.length,
      l = 0,
      r = 0;
  while(l < lLen && r < rLen) {
     if(left[l] < right[r]) {
       result.push(left[l++]);
     }
     else{
       result.push(right[r++]);
    }
  }  

  return result.concat(left.slice(l)).concat(right.slice(r));
}

マージソートは以前のアルゴリズムから複雑さの点ではるかに良いです.o ( n log n )演算を行い、配列をソートします.必要なメモリに関しては、リンクリストを使用している場合にはO ( n )の合計をO ( n )とする.
ケース
複雑さ
最悪ケース性能
o ( n log n )
ベストケースパフォーマンス
o ( n log n )
平均格性能
o ( n log n )
最悪ケース空間
o ( n ) total , o ( n )補助リスト、リスト( o )、リンクリスト付きo ( 1 )

クイックソート

クイックソートはマージソートに似ていますが、コレクションを半分に分割しません.我々はピボットポイントを選択し、そこから分割します.ピボットポイントを選択したら、すべての小さい項目を左側に、大きな項目を右側に配置します.
つまり、ピボットポイント自体がソートされます.我々は、完全なリストがソートされるまで、我々は左と右側のためにこれを再帰的に続けます.
ピボットを選択すると、リストのランダム、ミドルポイント、最初、または最後の項目になります.自分自身の長所と短所でこれを行うには多くの方法があります.
この違いをよりよく理解するために行動しましょう.

function quickSort(list, left, right) {
   let len = list.length, 
   pivot,
   partitionIndex;


  if(left < right) {
    pivot = right;
    partitionIndex = partition(list, pivot, left, right);

   //sort left and right
   quickSort(list, left, partitionIndex - 1);
   quickSort(list, partitionIndex + 1, right);
  }
  return list;
}

function partition(list, pivot, left, right) {
   let pivotValue = list[pivot],
       partitionIndex = left;

   for(let i = left; i < right; i++) {
    if(list[i] < pivotValue) {
      swap(list, i, partitionIndex);
      partitionIndex++;
    }
  }
  swap(list, right, partitionIndex);
  return partitionIndex;
}

function swap(list, i, j) {
   let temp = list[i];
   list[i] = list[j];
   list[j] = temp;
}

quickSort([11,8,14,3,6,2,7],0,6); 
//[2, 3, 6, 7, 8, 11, 14]

ご覧の通り、アルゴリズムがより効率的になるほど、実装が複雑になります.複雑さの面では、最悪の場合のマージソートより最悪であり、平均で最高である.
ケース
複雑さ
最悪ケース性能
O ( N 2 )
ベストケースパフォーマンス
単純なパーティションを持つo ( n log n )は、three-way partition
平均格性能
o ( n log n )
最悪ケース空間
o ( n )補助

ヒープソート

ヒープソートは比較ベースの並べ替えですが、選択ソートの改良版として考えることができます.これは、ソートされた領域と非ソート領域に入力を分割し、最大の項目を抽出し、ソートされた領域に挿入して、ソートされていない領域を反復的に縮小します.
Unsorted地域は、より迅速に各ステップで最大の項目を見つけるためにheap data structureに保持されます.

💡 Since there is no heap data structure in JavaScript, we can use an array to represent it.

それは一口だったので、行動してみましょう.

function heapSort(list) {
  let len = list.length;
  let i = Math.floor(len / 2 - 1);
  let j = len - 1;

  while(i >= 0) {
    heapify(list, len, i);

    i--;
  }

  while(k >= 0) {
    [list[0], list[k]] = [list[k], list[0]];

    heapify(list, k, 0);

    k--;
  }

  return list;
}

function heapify(list, len, i){   
  let largest = i;
  let left = i * 2 + 1;
  let right = left + 1;

  if(left < len && > list[left] > list[largest]) {
    largest = left;
  }

  if(right < len && list[right] > list[largest]) {
    largest = right;
  }

  if(largest != i) {
    [list[i], list[largest]] = [list[largest], list[i]];

    heapify(list, len, largest);
  }

  return list;
}

上記のコードスニペットでは、heapify関数は、3つの要素、親、および2つの子を比較します.それから、我々が最大のヒープのために正しい順序にあることを確認します.
ケース
複雑さ
最悪ケース性能
o ( n log n )
ベストケースパフォーマンス
o ( n log n )等しいキーを持つo ( n )
平均格性能
o ( n log n )
最悪ケース空間
o ( n ) total , o ( 1 )補助

概要

これで、これらのソートアルゴリズムをよく理解する必要があります.そうでなければ、私は再びそれらを通過し、ペンと紙でいくつかの例を書くことをお勧めします.場合は、ヒープの並べ替えのような複雑なものを理解するトラブルが心配しないでください.私が最初に同じトラブルを持っていたので、それは完全にokです.しかし、実際には、それらを実装しようとすると私は最後にそれらを学んだ.
そこに他の多くの並べ替えアルゴリズムがありますので、それらを探索し、彼らが今まで学んだこととどのように動作する方法を比較して自由に感じる.
読書のおかげで、あなたのコレクションの並べ替えをお楽しみください.

⚡ All the images in this post are pulled from the algorithm's Wikipedia pages.