ソフトウェアプログラマー試験: 最もシンプルなコード実装による最速のソートおよび検索アルゴリズム

アルゴリズムの中心的な問題はソートと検索です。これら 2 つの分野は最も広く使用され、最も徹底的に研究されています。この記事では、ソートと検索の分野で最も効率的な 2 つのアルゴリズム、クイックソートアルゴリズムとバイナリ検索アルゴリズムについて説明します。

教科書や多くの実装ライブラリに記載されているこれら 2 つのアルゴリズムのコードは非常に複雑で理解しにくいものです。この記事で紹介するコードは最も単純な実装コードであり、理解しやすく非常に効率的です。

バイナリ検索アルゴリズムは、Flex でワークフローエディターを開発していたときに実装されました。当時の要件は、2 つのグラフィック間を接続する線を引くことでした。マウス操作に応じて描画する必要があり、線分の始点と終点はいずれもグラフィックの外枠上にある必要がありました。

上記の説明は少し抽象的かもしれません。このように言いましょう。私が最初に実装した GUI 効果は、マウスで接続された 2 つのボックスでした。私が描いた線は、マウスをクリックして放したときに 2 つの端点を結んだ線分でした。しかし、このような線分は見た目が悪く、顧客は線分の両端が 2 つのボックスの境界上にあることを要求しています。

この問題を解決するにはどうすればよいでしょうか。線分をソートされた点の集合と見なし、バイナリ検索アルゴリズムを使用して線分と境界線の交点を検索し、それらを描画します。

バイナリ検索アルゴリズムは当時はActionScript3で書かれていましたが、現在はJavaに変更されています。

クイックソートアルゴリズムとバイナリサーチアルゴリズム

アルゴリズムは主にソートアルゴリズム、検索アルゴリズム、グラフアルゴリズムに分けられます。私はグラフアルゴリズムをあまり使用しないので、それについては何も言う権利がなく、この記事では取り上げません。

最も高速なソートアルゴリズムはクイックソートアルゴリズムであり、最も高速な検索アルゴリズムはバイナリサーチアルゴリズムです。私もこの 2 つのアルゴリズムが一番好きです。

再帰を使用して実装されているため、コードは簡潔かつ明確であり、効率が非常に高くなります。

私の理解によれば、アルゴリズムの本質は数学です。入力と設定された目標に基づいて、有限数のステップで出力が達成されます。通常、コンピュータを使用して実装されたアルゴリズムは、コンピュータの高速計算能力を活用するためにループを使用します。

ループと再帰は同等であり、これは科学者によって証明されています。数学にはループはなく、再帰だけが存在するため、ループの代わりに再帰を使用してアルゴリズムを表現すると、次のような多くの利点があります。

1. 再帰コードはループコードよりもはるかにシンプルでエレガントです。

2. 再帰コードは数学的にモデル化でき、その正しさは数学的観点から検証できます。

多くの関数型言語にはループの概念やキーワードすら存在しないため、ループを実装するには再帰を使用する必要があります。たとえば、ErLang。

ただし、再帰アルゴリズムは簡単にループになる可能性があります。私は再帰のシンプルさを好み、実際にスタックオーバーフローの問題が発生しない限り、ループは使用しません。

二分探索アルゴリズム

理論：

バイナリ検索アルゴリズムは、ソートされたコレクションを検索するために使用されます。

その原則は次のとおりです。

1. ソートされた配列の中央の要素を見つけ、それがターゲット値と一致する場合は、配列内のそのインデックスを返します。

2. 見つからない場合は、中間値が目標値より大きいか小さいかを判断します。

中間の値が目標値より大きい場合は、最初の要素から中間の 1 要素までこのプロセスを再帰的に実行します。

中間の値が目標値より小さい場合は、最後の要素に中間値 + 1 を追加します。

3. 終了インデックスが開始インデックスより小さい場合は、見つからなかったことを示す -1 が返されます。

4. サブセットに 2 つの要素がある場合は、それらを個別に比較します。 Java の整数除算では小数点が切り捨てられるため、配列に要素が 2 つしかない場合は、中央の値は常に最初の要素になります。

上記の再帰プロセスの後、一致する要素のインデックスが返されます。または、見つからないことを示す -1 が返されます。

バイナリ検索アルゴリズムは、配列を毎回 2 つに分割でき、各再帰呼び出しですべてのデータを一致させることなくデータの半分を削除できるため、高速です。

コード：

以下はコードです。ロジックは明確で、コードはシンプルです。

/**

* @param 配列

* @param 開始

* @param end これは最後の要素のインデックスです。最初の呼び出しはarray.length-1にする必要があります。

* @パラメータ値

* @戻る

パブリック静的intバイナリサーチ(int[]配列、int開始、int終了、int値){

int 中間 = (開始 + 終了) / 2;

if(終了

-1 を返します。

}

終了 == (開始 + 1) の場合

if(配列[開始]==値){

開始を返します。

}それ以外の場合(配列[終了]==値){

終了を返します。

}

}そうでない場合(配列[中央]==値){

真ん中を返す;

}else if(値>配列[中央]){

binarySearch(配列、中間+1、終了、値) を返します。

}else if(値

binarySearch(配列、開始、中間-1、値) を返します。

}

-1 を返します。

}

上記のコードを少し変更するだけで、任意のタイプをソートできます。たとえば、ジェネリックを使用してから、Comparable インターフェースの実装を追加できます。

クイックソートアルゴリズム

バイナリ検索アルゴリズムは非常に高速ですが、ソートされた配列でのみ機能します。配列がソートされていない場合はどうなるでしょうか? 簡単です。まずクイックソートアルゴリズムを使用してソートし、次にバイナリ検索を使用して検索します。

最初に並べ替えてから検索する方が、各要素を一致させるよりもはるかに高速です。検索エンジンやデータベースのインデックスでも、データセットのソート技術が使用されているため、データをすばやく検索できます。

理論：

考えられる最も遅くて簡単なソートアルゴリズムは、挿入ソートアルゴリズムです。

1. 配列を走査し、最小の要素を見つけて、それを最初の要素として配置します。

2. 配列全体がソートされるまで、ソートされていない配列をループします。

これには 2 つのネストされたループが必要であり、効率は O(n^2) です。

挿入ソートが非常に効率的である理由は、配列全体の中で最小のデータを見つけるには、配列全体の要素を走査する必要があるためです。

挿入ソートの巧妙なところは、配列全体から最小の要素、2 番目に小さい要素などを探すのではなく、特定の要素よりも小さい値をその都度横に移動するだけであり、最終的には反復処理によって自動的にソートを実現するという点にあります。これにより、ソートに必要な計算手順が大幅に節約されます。

クイックソートアルゴリズムの理論:

1. S 内の要素数が 0 または 1 の場合、戻ります。

2. S 内の任意の要素 v を選択します。これを中心点と呼びます。

3. 集合 S 内の要素を 2 つの部分に分割します。L = {ピボット未満の要素 + ピボット}、R = {ピボット以上の要素}。

4. LとRを戻します。

Java を使用してインプレースソートメソッドを使用するため、戻り値は必要ありません。

Java は変数を変更できる言語なので、関数型言語の用語で言えば「副作用」があります。この副作用を使用して、値を返さずにパラメーターとして渡された配列を直接変更します。

コード：

* 副作用が小さいものから大きいものまで、クイックソート

* @param 配列

* @param 開始

* @param end これは最後の要素のインデックスです。最初の呼び出しはarray.length-1にする必要があります。

パブリック静的voidクイックソート(int[]配列、int開始、int終了){

// 再帰呼び出しで j+1 が使用されるため、start>end となる可能性があり、j が end より 1 大きくなる可能性があります。さらに、配列が空の場合や入力が間違っている場合にもこの状況が発生します。

if(終了<=開始){

戻る;

}それ以外 {

//中央の要素を中心点として右端に移動します

int 符号 = (開始 + 終了) / 2;

int tmp=配列[終了];

配列[終了]=配列[符号];

配列[符号]=tmp;

int j=開始;

for(int i=start;i<=end-1;i++){

//小さい要素とマークは交換されますが、等しい要素は交換できません。そうしないと、無限ループが形成されます。

if(配列[i]

tmp=配列[i];

配列[i] = 配列[j];

配列[j] = tmp;

j=j+1;

}

// マークされた要素とそれより大きい最初の要素を交換して、配列を 2 つの部分に分割します。1 つの部分は中央の値より小さく、もう 1 つの部分は中央の値より大きくなります。 tmp=配列[j];

配列[j]=配列[end];

配列[終了]=tmp;

クイックソート(配列、開始、j);

クイックソート(配列、j+1、終了);

}

Java の Arrays クラスも、ソートにクイックソートアルゴリズムを使用します。しかし、そのコードは象形文字の本のように書かれています。

クイックソートアルゴリズムの実行効率を向上させる主な方法は、選択された中心点が配列全体の中央値である可能性が高くなることを期待して、中心点を検出することです。

私の実装では、配列の中央の値を中心点として選択するだけです。一般的に言えば、この選択は非常に効率的です。

上記の実装手法では、中央のデータ要素を配列の末尾に移動することで、配列のインプレース比較を実装していることに注意してください。これはよく使用される手法で、データの比較を容易にするためにデータを配列の先頭または末尾に移動します。

さらに、私の Java クイックソートコードは「副作用」を使用していますが、Haskell や ErLang などの純粋な関数型言語には「副作用」がなく、つまり変数を再割り当てできません。この時点で、値を返して、毎回新しいサブ配列を作成する必要があります。しかし、関数型言語は強力な配列処理機能を備えており、多くのパフォーマンス最適化を実行できます。そのため、関数型言語で実装されたクイックソートコードはより単純で、「副作用」がなく、より数学的です。

【編集者のおすすめ】