アルゴリズムは、限られた数のステップで問題を解決するために使用される、明確に定義された一連のルールです。簡単に言えば、コンピュータが問題を解決するプロセスです。このプロセスでは、問題解決のアイデアを形成する場合でも、プログラムを作成する場合でも、特定のアルゴリズムを実装することになります。前者は推論によって実現されるアルゴリズムであり、後者は演算によって実現されるアルゴリズムです。
アルゴリズムには次の 5 つの重要な特性が必要です。
1. 有限性: アルゴリズムは、有限数のステップを実行した後に終了することを保証する必要があります。
2. 正確性: アルゴリズムの各ステップは明確に定義される必要があります。
3. 入力: アルゴリズムには、オペランドの初期状況を記述するための 0 個以上の入力があります。
4. 出力: アルゴリズムには、入力データの処理結果を反映する 1 つ以上の出力があります。出力のないアルゴリズムには意味がありません。
5. 実現可能性: 原理的には、このアルゴリズムは正確に実行でき、ペンと紙を使用して限られた数の操作を実行することによっても完了できます。
マージ ソート (MERGE SORT) は、別の種類のソート方法です。マージの意味は、2 つ以上の順序付けされたデータ シーケンスを新しい順序付けされたデータ シーケンスにマージすることであるため、マージ アルゴリズムとも呼ばれます。その基本的な考え方は、配列 A に N 個の要素があると仮定し、配列 A が N 個の順序付けられたサブシーケンスで構成されていると見なすことができ、各サブシーケンスの長さは 1 であり、2 つずつ 2 をマージして N/2 の順序付けされたサブシーケンスを取得します。次に、長さ 2 または長さ 1 を 2 つずつマージし、長さ N の順序付けされたデータ シーケンスが得られるまでこれを繰り返します。このソート方法は、2 方向マージ ソートと呼ばれます。
たとえば、配列 A には 49 38 65 97 76 13 27 という 7 つのデータがあります。マージ ソート アルゴリズムを使用する操作プロセスを図 7 に示します。
初期値[49][38][65][97][76][13][27]
長さ 1 の 7 つのサブシーケンスで構成されていると見なされます。最初のマージ後 [38 49] [65 97] [13 76] [27]
長さ 1 または 2 の 4 つのサブシーケンスで構成されると見なされます。2 回目の結合後 [38 49 65 97] [13 27 76]
長さ 4 または 3 の 2 つのサブシーケンスで構成されると見なされます。3 回目の結合後 [13 27 38 49 65 76 97]
図 6 マージ ソート アルゴリズムのプロセス図 マージ アルゴリズムの中心となる操作は、1 次元配列内の 2 つの隣接する順序付きシーケンスを 1 つの順序付きシーケンスにマージすることです。マージ アルゴリズムは再帰アルゴリズムを使用して実装することもできます。再帰アルゴリズムは形式が比較的単純ですが、実用性は低くなります。
マージ アルゴリズムにおけるマージの数は非常に重要な量です。計算によると、配列内の要素が 3 ～ 4 個の場合、マージの数は 2 回、要素が 5 ～ 8 個の場合、マージの数は 3 回になります。 、要素数が 9 ～ 16 の場合、マージ数は 4 です。この規則によると、部分列が N 個ある場合、マージ数は 4 であると推測できます。
X (2>=N、サブ条件を満たす最小の X)。
バブルアルゴリズムの説明:
バブルソートのアルゴリズムを説明する前に、まず、(配列 A 内の) 10 個の数値のうち最大の数値を最後の位置に置くアルゴリズムを紹介します。アルゴリズムは次のように説明されます。
(1) 配列 A[1] から A[10] までの、隣接する 2 つの数値をペアで比較します。つまり、A[1] と A[2] が比較され、比較後、A[2] と A[3] が比較され、最後に A[9] と A[10] が比較されます。
(2) 各比較中に、前の数値が後の数値より大きい場合、2 つの数値が交換されます。つまり、大きい数値が後ろに移動し、小さい数値が前に移動します。たとえば、最初の比較では、A[1]がA[2]より大きい場合、A[1]とA[2]の値が入れ替わります。以下の図は、上記のアルゴリズムを説明するために 6 つのデータを使用しています。
6 つのデータが A[]=5 7 4 3 8 6 であると仮定します。
A[1] A[2] A[3] A[4] A[5] A[6]
5 7 4 3 8 6 初めて、A[1]=5 と A[2]=7 が比較され、7>5 となり、スワップは実行されません。
5 7 4 3 8 6 2 回目は、A[2]=7 と A[3]=4 が比較され、4<7、交換されます。
2 回目の比較後のデータは 5 4 7 3 8 6 となります。
5 4 7 3 8 6 3 回目、A[3]=7 と A[4]=3 が比較され、3<7、交換されます。
3 回目の比較後のデータは 5 4 3 7 8 6 となります。
5 4 3 7 8 6 4 回目、A[4]=7 と A[5]=8 が比較され、8>7 となり、スワップは実行されません。
5 4 3 7 8 6 5 回目、A[6]=6 と A[5]=8 が比較され、6<8、交換されます。
5 番目の最終結果は次のとおりです。
5 4 3 7 6 8
************************************************* * *****
選択ソートアルゴリズムの説明:
選択によるソート方法を紹介する前に、最小の数値を最初の位置に配置するアルゴリズムを紹介します。もちろん、上記のバブル ソート方法を使用することもできます。その指針となるイデオロギーを急ぐ必要はありません。まず、A[1] から順に各番号を確認し、スキャンが完了した後、その番号の位置 P を書き留めます。とすると、A[1]～A[10]の中で最も小さいデータが先頭に移動されます。アルゴリズムの手順は次のとおりです。
1) まず、A[1] の数値が最小であると仮定し、このときの位置 P=1 に注目します。
2) A[P] と A[I] を順番に比較します (I は 2 から 10 に変化します)。A[I] の数値が A[P] の数値より小さい場合、I の値が変化します。が P に割り当てられるため、P は常に現在スキャンされている最小の数値の位置を指します。つまり、A[P] は常にすべてのスキャンされた数値の最小の数値と等しくなります。 1 つずつ比較した後、P は 10 個の数値の中で最も小さい数値の位置を指します。つまり、A[P] は 10 個の数値の中で最も小さい数値です。
3) A[P] と A[1] の番号を反転すると、最小の番号が A[1]、つまり先頭になります。
このアルゴリズムを繰り返すと、繰り返されるたびに、比較される系列の範囲が 1 つ後ろに移動します。つまり、2 回目の比較では、範囲は 2 番目の番号から N 番目の番号までで、この範囲内で最小の番号の位置 P を見つけ、2 番目から A[P] と A[2] を入れ替えます。先頭から N 番目までの最小の数は A[2] にあります。 3 回目は、3 番目の数から N 番目までの最小の数を見つけて、A[P] と A[3] を入れ替えます。このプロセスを N-1 回繰り返すと、A 配列内の N 個の数値が小さいものから大きいものへの順序で配置されます。このソート方法は選択ソートです。
************************************************* * ***************
挿入ソートアルゴリズムの説明:
上記の 2 つの方法を学ぶことで、ソートの基本的な考え方を理解することができ、順序のない配列を大きいものから小さいもの (降順) または小さいものから大きいもの (昇順) に並べ替えることもできます。ここで、既に順序付けされたデータ列があり、この既に配置されたデータ列に数値を挿入する必要があるとします。ただし、挿入後もデータ列が順序付けされていることが必要です。このとき、新しいソート方法が使用されます。挿入ソート方式が使用されます。挿入ソートの基本操作は、ソートされた順序付きデータにデータを挿入し、番号に 1 を加えた新しい順序付きデータを取得することです。
質問: 配列 A には、小さいものから大きいものの順に並べられた N 個のデータがあります。数値 X を入力し、X の値を配列 A に挿入すると、挿入された配列 A は引き続き小さいものから大きいものの順に並べられます。 。
この問題を解決するアルゴリズムは次のとおりです。
1) X を I 番目の位置に配置する場合は、サイズを比較して挿入する位置を見つけます。
2) I から始まるすべての配列要素 (I を含む) を 1 つ後ろに移動します。つまり、A[I+1]:=A[I];
クイック ソートはバブル ソートを改良したものです。その基本的な考え方は、一方向の並べ替えによって並べ替えられるデータを 2 つの独立した部分に分割し、一方の部分のすべてのデータがもう一方の部分のすべてのデータよりも小さくなり、データの 2 つの部分が順番に並べ替えられることです。迅速に並べ替えるために、並べ替えプロセス全体を再帰的に実行して、データ全体が順序付けられたシーケンスになるようにすることができます。
ソート対象の配列が A[1]...A[N] であるとします。まず、キー データとしてデータ (通常は最初のデータ) をランダムに選択し、そのデータより大きいすべての数値をその前に置きます。大きな数字はその後ろに配置されます。このプロセスはクイックソートと呼ばれます。クイックソートのアルゴリズムは次のとおりです。
1) 2 つの変数 I と J を設定します。ソートが開始されると、I:=1、J:=N になります。
2) 最初の配列要素をキー データとして使用し、それを X、つまり X:=A[1] に割り当てます。
3) J から前方に検索、つまり後方から前方に検索 (J:=J-1)、X より小さい最初の値を見つけ、その 2 つを交換します。
4) I から後方に検索します。つまり、前から後ろに検索し (I:=I+1)、X より大きい最初の値を見つけ、その 2 つを交換します。
5) I=J になるまでステップ 3 と 4 を繰り返します。
例：ソート対象の配列Aの値は：（初期キーデータX:=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]:
49 38 65 97 76 13 27
最初の交換後: 27 38 65 97 76 13 49
(2 番目の交換のアルゴリズムの 3 番目のステップに従って後ろから検索した後: 27 38 49 97 76 13 65
(アルゴリズムの 4 番目のステップに従い、前から開始して値を見つけます >
3回目の交換後: 27 38 13 97 76 49 65
(アルゴリズムの 5 番目のステップによると、アルゴリズムの 3 番目のステップが最後から再度実行され、4 番目の交換が見つかります: 27 38 13 49 76 97 65
(アルゴリズムの 4 番目のステップに従って、先頭から開始して X より大きい値、97>49 を見つけます。この 2 つを交換します。この時点では J:=4)
このとき、3 番目のステップを実行すると、I=J であることがわかり、クイック ソートの結果は 27 38 13 49 76 97 65 になります。つまり、49 より大きい数値はすべて 49 に入ります。 , したがって、49 未満の数字はすべて 49 の前にあります。
クイックソートとは、この処理を再帰的に呼び出すことです。49を中点としてデータ列を分割し、前部と後部で同様のクイックソートをそれぞれ実行することで、データ列全体のクイックソートを完了し、最後にデータ列を回転させます。この考え方に従って、上記の配列 A を簡単にソートするプロセス全体を図 6 に示します。
初期状態 {49 38 65 97 76 13 27}
簡単に並べ替えると、{27 38 13} 49 {76 97 65} に分割されます。
前部と後部をそれぞれすばやく並べ替えます {13} 27 {38}
終了終了 {49 65} 76 {97} 49 {65} 終了終了
************************************************* * *************************
図 6 クイック ソート プロセス全体にわたるクイック ソートのアルゴリズムの説明
1) N 個 (N=10 と仮定) の数値が S 配列に格納されているとします。
２）、Ｓ［１． 。 N] 内の任意の要素を比較の基準として使用します。たとえば、T=S[1] を使用します。最初の目的は、ソート結果内で T が存在する位置 K を決定することです。K の位置は次のとおりです。 。 。 K-1]<=S[K]<=S[K+1..N]、つまり、S[K] より前の数値はすべて S[K] より小さく、S[K] の後の数値はすべて S[ K] より大きい。
3) 分割統治のアイデア (つまり、大きいものと小さいものを小さくする戦略) を使用すると、S[1. 。 K-1] および S[K+1. 。 N] 次に、グループ化オブジェクト内にデータが 1 つだけになるまで、2 つのデータ セットがすばやく並べ替えられます。
特定のデータが次のような場合、最初のクイック並べ替えプロセスは次のようになります。
配列の添字: 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
ij
(1) 36 36 18 53 72 30 48 93 15 45
(2) 36 36 18 45 72 30 48 93 15 53
(3) 36 36 18 15 72 30 48 93 45 53
(4) 36 36 18 15 45 30 48 93 72 53
(5) 36 36 18 15 30 45 48 93 72 53