JavaScriptで並べ替えに "クイックソート" アルゴリズムを使用してみました。：ULCAMTCVSMPS：So-netブログ

	ブログをはじめるログイン

Firefox 54がとてつもなく速い!..｜自作の音楽再生ウェブアプリケーション専.. ブログトップ

JavaScriptで並べ替えに "クイックソート" アルゴリズムを使用してみました。　[プログラミング] [編集]

データの並べ替えを高速に行う必要がある時、一般的に、最適なアルゴリズムと言えば " Quicksort " (クイックソート) アルゴリズムだそうです。

私はHTML5のCanvas要素とWeb Audio APIで簡易なミュージックプレイヤーを作ってみたのですが、音楽ファイルを含む多数のフォルダーがあるディレクトリーを読み込んだ後に、楽曲リストを名前順に並べ替える必要がございました。
そこで威力を発揮したのがクイックソートです。
数千曲のリストも素早く並べ替えられます。

専用ブログの記事: ウェブ音楽プレイヤー
URL: https://applicationprogram.blog.so-net.ne.jp/2019-07-03-1

以下に私の使用したコードを掲載致しますが、このコードは書き方として冗長なものとなっております。
また、始めに基準値を設定する為の複数個のサンプルデータの中央の値を取る為にバブルソートを行っておりますが、これについても実はもっと簡単に、サンプル数を3つに固定して単純な条件分岐だけで中央の値を取得する事も出来ます。

var data = [2,6,1,4,9,23,11,41,35,26,14,19,55,38,17,25,18,40,31,45,34,5,10,7,3,8,12,22];
var data2 = ['abc','aaaaaa','xy','ABC','123','12','5678','98','11F'];


// クイックソートを行う関数の宣言。
function quicksort( arrayOfData, boundaryOfLeft, boundaryOfRight )
{
 if( boundaryOfLeft < boundaryOfRight )
 // 区間内に複数個のデータがあるならば処理を行う。
 {
  // 奇数個のデータの中央の値を基準値として設定する。
  var sampleData = [];
  var pivot = 0;
  var randomNumber = 0;
  var numberOfSample = 3;
  var i = 0;
  var j = 0;

  // ランダムにサンプル データを抽出する。
  for( i = 0; i < numberOfSample; i++ )
  {
   randomNumber = Math.floor( Math.random() * (boundaryOfRight + 1 - boundaryOfLeft) + boundaryOfLeft );
   sampleData[i] = arrayOfData[randomNumber];
  }

  // バブル ソートを行う。
  for( i = 0; i < sampleData.length - 1; i++ )
  {
   for( j = sampleData.length - 1; j > i; j-- )
   {
    if( sampleData[j] < sampleData[j - 1] )
    {
     temporaryData = sampleData[j - 1];
     sampleData[j - 1] = sampleData[j];
     sampleData[j] = temporaryData;
    }
   }
  }

  // 中央の値を取る。
  pivot = sampleData[(numberOfSample - 1) / 2];

  i = boundaryOfLeft;
  j = boundaryOfRight;
  var temporaryData = null;
  while( true )
  {
   while( arrayOfData[i] < pivot )
   // 基準以上の値に出会うまで移動する。
   {
    i++;
   }

   while( arrayOfData[j] > pivot )
   // 基準以下の値に出会うまで移動する。
   {
    j--;
   }

   if( i >= j )
   // もし左右の注目位置が一致または交差したならば処理を抜ける。
   {
    break;
   }else
   // 左右の注目位置が未だ離れているならばその位置の値を交換する。
   {
    temporaryData = arrayOfData[i];
    arrayOfData[i] = arrayOfData[j];
    arrayOfData[j] = temporaryData;
    i++;
    j--;
   }
  }

  if( boundaryOfLeft < i - 1 )
  // 未だ左側の区間内に複数のデータがあるならば処理を繰り返す。
  {
   arrayOfData = quicksort( arrayOfData, boundaryOfLeft, i - 1 );
  }

  if( j + 1 < boundaryOfRight )
  // 未だ右側の区間内に複数のデータがあるならば処理を繰り返す。
  {
   arrayOfData = quicksort( arrayOfData, j + 1, boundaryOfRight );
  }
 }
 return( arrayOfData );
}


// クイックソートを実行する。
data = quicksort( data, 0, data.length - 1 );
data2 = quicksort( data2, 0, data2.length - 1 );

console.log( data ); // 1,2,3,4,5,6,7,8,9,10,11,12,14,17,18,19,22,23,25,26,31,34,35,38,40,41,45,55
console.log( data2 ); // 11F,12,123,5678,98,ABC,aaaaaa,abc,xy