ソートアルゴリズムについてまとめてみた

こんにちは。

マネーフォワードでフロントエンドエンジニアやっております高山です。

マネーフォワードにジョインしたのは12月1日で、

気がつけば2ヶ月が経過し、日々揉まれながら過ごしております。

今回、エンジニアブログを投稿することになり、

「何書こう、、、何書こう、、、」と模索した結果、

アルゴリズムについて書いてみようと思いました。

非エンジニアの方で「アルゴリズムとは遠い」と思われている方でも、

『調べたい事があり、Googleで検索する』

といった行為も、Googleの検索アルゴリズムを使っていたりして、

Webサービスや、スマホAppを使用する側も、開発する側も、

アルゴリズムは必要不可欠な時代となっております。 　 前置きはこのくらいにしまして、数あるアルゴリズムの中でも、

一般的にメジャーで入門的存在の「ソートアルゴリズム」の代表的な一部を

まとめさせていただきましたので、何か参考になればと思います。

「え、今更ソートアルゴリズム!?」と言ったツッコミを受けそうですが、

以前から一度まとめたいなと思った内容だったりもして、

知らなかった方は、これキッカケでその他のアルゴリズムに興味持っていただければ、これ幸いです。

（と、書いている本人が色々と勉強中の状態だったりします。） 　

ソートアルゴリズム

まずは、こちらの映像を見ていただければと思います。

この映像は、ちょっと前に話題になった「ソートアルゴリズム」を可視化した映像です。

再生回数も190万回とすごい。

アニメーションを動かす処理とはまた違って、

アルゴリズムの可視化されると何とも言えない感動がありますね。

とう事で、ただソートする。

といった裏で、様々なアルゴリズムが存在します。

それでは、その一部を。 　

バブルソート

特徴

• 隣り合う要素の大小を比較しながら整列
• アルゴリズムは最も単純
• 非効率なソートアルゴリズム

バブルと言えば、何かと華やかな印象がありますが、

バブルソートはその逆で、実装も簡易で最も効率の悪いソートとなっております。

アルゴリズムは、下から順番に、上の要素と比較し、上の要素が大きい場合は違いに交換する。

といったものになっており、

小さい数字は交換されて上へと順々に上がり、1順すると一番小さい数字が一番上に上がってきます。

2順目は一番上の要素を除き、一番小さい数字を2番目に上げ、3順目は3番目に上げ..

と、一番下の要素まで繰り返す事によってソートを行います。

TypeScript

public bubble(a: number[]): number[] {
  var i: number = 0, j: number = 0;
  for (; i < a.length; i++) {
    for (j = a.length - 1; j > i; j--) {
      //上の要素と比較し、上のほうが大きければ互いに交換する
      if (a[j] < a[j - 1]) {
        this.swap(a, j - 1, j);
      }
    }
  }
  return a;
}

scriptも数行で完結できるソートアルゴリズムとなっております。 swapの処理は、様々ありますが、配列も渡す形式で行っております。

public swap(arr: number[], a: number, b: number): number[] {
  var tmp: number = arr[a];
  arr[a] = arr[b];
  arr[b] = tmp;
  return arr;
}

（ソース一式は、ページ下のGitHubのリンクから参照できます。） 　

バケットソート

特徴

• オーダーは高速
• データの値の範囲が有限個の整数で表現できなければならない
• データの値の種類の分、バケツが必要な為、メモリ浪費してしまう可能性あり

バケットソートはあらかじめ順番通りに並んだバケツをソートを行う要素分用意し、

順番に格納された要素をバケツから取り出しソートを行うといったアルゴリズムになっております。

バケットソートの特徴として、

データの存在する範囲が有限個に限定と、より強い制限を前提としているソートですが、

使用可能な場合は高速に並べ替えを実行できるソートの一つとなっております。

TypeScript

private _bucket_length: number = 100;

バケット数は、デフォルトでは、100個用意しています。

max: number = this._bucket_length,

バケツの準備を行い。

// バケツを準備
for (var i: number = 0; i < max; i++) {
    bucket[i] = 0;
}

バケツを作成。

// 全てのデータに対応するバケツを作成
for (var i: number = 0; i < a.length; i++) {
    var n = a[i];
    bucket[n]++;
}

// バケツの順番に中のデータを取り出し配列に格納
for (var i: number = 0; i < max; i++) {
  ...省略
}

これも、そんなに複雑ではないソートアルゴリズムかと思います。 　

基数ソート

特徴

• バケットソートの発展形
• 下位1桁目から対応するバケットに格納
• 計算時間は高速
• データの種類が有限で、最大値・最小値がはっきりしている

基数ソートは、バケットソートの発展形で、

10進数の0以上の整数値の場合、0〜10のバケツを用意し

ソートを行う要素の下1桁目に対応するバケツに格納します。

一通り格納すると、次は下2桁目に対応するバケツに格納します。

全桁数この処理を行い、取り出すとソートされているといったアルゴリズムになっております。

個人的に好きなソートの一つです。

TypeScript

10進数の整数を扱う前提で、

// 0 ~ 10 の10個のバケツを準備
for (var i: number = 0; i < 10; i++) {
    bucket[i] = [];
}

最大桁数取得します。

// 最大桁数取得
for (var i: number = 0; i < a.length; i++) {
    if (maxDigit < a[i].toString(10).length) {
      maxDigit = a[i].toString(10).length;
    }
}

最大桁数分 処理を実行します。

// 桁数分実行
for (var d: number = 0; d < maxDigit; ++d) {
    ... 省略
}

桁単位で該当するバケツに代入していきます。

//桁単位で該当するバケツに代入
for (n = 0; n < bucket[j].length; n++) {
   a[i++] = bucket[j][n];
}

一通り処理を行うと、次の桁へと移動させます。

r *= 10;

全ての処理完了後はソートが完了しております。 　

ヒープソート

特徴

• 親のデータが2つの子のデータよりも小さくなるように作られたデータ構造
• もっとも小さいデータが常に根にある
• 平均的にはクイックソートより遅い

ヒープソートは、2分ヒープ木を用いてソートを行うアルゴリズムです。

ヒープソートに用いられる2分ヒープ木は、親のデータが2つの子データよりも小さくなるように作られています。

アルゴリズムとしては、

未整列のリストから要素を取り出し、順にヒープに追加を行い、

全て追加し終わった後に、2分ヒープ木の根から取り出しソートを行うといったアルゴリズムになっております。

特徴としては、もっとも小さいデータが常に根にあることです。

TypeScript

まずは、ヒープに要素を追加していく処理を行い、

// ヒープに要素を追加

for (var i: number = 0; i < a.length; i++) {
  insert(a[i]);
}

親と比較して子のほうが小さければ入れ替えする事によって、 根を小さい値へと行っていきます。

// 親と比較して子のほうが小さければ入れ替え
while (i > 1 && heap[i - 1] < heap[j - 1]) {
    ... 省略
}

ヒープから取り出しながら配列に追加していきます。

// ヒープから取り出しながら配列に追加
for (i = 0, len = heap.length; i < len; i++) {
    a[i] = shift();
}

子の小さい方のデータと比較して親の方が大きければ、入れ替えを行います。

if (heap[i - 1] > heap[j - 1]) {
    that.swap(heap, i - 1, j - 1);
}

全て根から取り出し後、ソートは完了しております。 　

マージソート

特徴

• データを分割し各々をソート行った後にマージ
• 平均・最悪ともに計算が高速

マージソートのアルゴリズムとしては、

バラバラになっている配列データを再帰的に最小限まで分解を行い、

分解し終わった後、結合を行います。

結合を行う際、データ列の先頭同士を比べ小さい方をデータ列から取り出し、

残りのデータ列に対して再帰的に適応する事によって、ソートを行います。

特徴としては、最悪計算量がクイックソートより少ないのが特徴ですが

ランダムデータでは通常、クイックソートのほうが速いようです。

TypeScript 配列が2つ以上の場合、分割を開始します。

a = split(aArr.slice(0, mid));
b = split(aArr.slice(mid, aArr.length));

分割後のマージの処理で、aとbを比較し、c配列に格納していきます。

if (i < j) {
    c.push(a.shift());
} else {
    c.push(b.shift());
}

削除いない要素を結合します。

if (a.length === 0) {
    c = c.concat(b);
} else if (b.length === 0) {
    c = c.concat(a);
}

全ての要素処理完了後、ソートは完了しております。 　

クイックソート

特徴

• 一般的に最も高速だといわれている
• データの比較と交換回数が非常に少ない
• 対象のデータの並びやデータの数によっては必ずしも速いわけではない

最後はやっぱりクイックソートです。

大ボス感もあり、一般的に最も高速なソートアルゴリズムとしても知られております。

クイックソートのアルゴリズムとしては、まず最初に「軸要素」を決定し、

データ構造を2分した際のしきい値として使用されます。

軸要素の取得の方法は様々ですが、今回は

左から見て最初に得られた2つの異なる値の大きい方を軸要素と決定しております。

データの先頭から軸要素以上のデータを検索、データの末尾から軸要素未満のデータを検索、

見つかった場合は、それぞれを交換します。

この処理を検索ラインが交差するまで続け、交差した場所でデータを2つに分割します。

この処理を繰り返す事によって最終的にソートされる。と

「何を食べればこういう事が思いつくのか」と言った気持ちにさせるアルゴリズムとなっております。

まず最初に、軸要素の選択を行います。

var p = pivot(a, i, j);

順に参照、最初に見つかった異なる2つの要素のうち、大きい方の番号を返却 全部同じ要素の場合は -1を返却して、即時終了します。

var k: number = i + 1;
while (k <= j && a[i] === a[k]) {
    k++;
}
if (k > j) {
    return -1;
}
if (a[i] >= a[k]) {
  return i;
}
return k;

続いて、パーティション分割

k = partition(a, i, j, a[p]);

a[l] ~ a[r]間で、p を軸として分割。pより小さい要素は前に、大きい要素は後ろへと移動。

partition: Function = (a: number[], i: number, j: number, p: number) => {

検索が交差するまで繰り返します。

while (l <= r) {

軸要素以上のデータを検索

while (l <= j && a[l] < p) {
    l++;
}

軸要素未満のデータを検索

while (r >= i && a[r] >= p) {
    r--;
}

この処理を再帰的に実行する事によって

recurse(a, i, k - 1);
recurse(a, k, j);

処理終了後、ソートも完了しております。

といった感じで、一部ではありますが、ソートアルゴリズムにまとめさせていただきました。

もちろんソートアルゴリズムはこれ以外にもたくさん存在し、

Google検索すると色々情報はヒットしますので、興味のある方は検索してみていただければと思います。

はっきり言って、「ヒープソートをクイックソートに実装しなおして。」とか、

フロントエンドとして仕事して中で、1回もなくこれからも多分ほとんどなく、

実務ではあまり役たたない内容だったかもしれませんが、

検索や、レコメンド、探索、乱数テーブル等のその他のアルゴリズムはどこかで作成する機会があるかと思いますので、 知らなかった方はこれキッカケで興味持っていただければと思う次第であります。 （書いている本人も全然勉強中の最中です！）

参考文献

wikipedia www.ics.kagoshima-u.ac.jp 110chang.com

今回まとめさせていただいたソートアルゴリズムをTypeScriptにしております。

TypeScript Sort Algorithm Github

TypeScript Sort Algorithm

使用方法は以下の様になっております。

var sort = new Sort();
var result = sort.marge(number[]);

シングルトンオブジェクトで作成しておりますので、以下の方法でも使用可能です。

var result = new Sort(number[]);

第二引数で、バケット数を指定できます。

var sort = new Sort([], bucketLength);
var result = sort.bucket(number[]);

or

var sort = new Sort();
var result = sort.bucket(number[], bucketLength);

マネーフォワードについて

【採用サイト】 ■マネーフォワード採用サイト ■Wantedly | マネーフォワード

【公開カレンダー】 ■マネーフォワード公開カレンダー

【プロダクト一覧】 ■家計簿アプリ・クラウド家計簿ソフト『マネーフォワード』 ■家計簿アプリ・クラウド家計簿ソフト『マネーフォワード』　iPhone,iPad ■家計簿アプリ・クラウド家計簿ソフト『マネーフォワード』　Android ■クラウド型会計ソフト『MFクラウド会計』 ■クラウド型請求書管理ソフト『MFクラウド請求書』 ■クラウド型給与計算ソフト『MFクラウド給与』 ■経費精算システム『MFクラウド経費』 ■消込ソフト・システム『MFクラウド消込』 ■マイナンバー対応『MFクラウドマイナンバー』 ■創業支援トータルサービス『MFクラウド創業支援サービス』 ■お金に関する正しい知識やお得な情報を発信するウェブメディア『マネトク！』