開発プロジェクトでは、思っているよりも頻繁にさまざまなアルゴリズムが使用されます。たとえば、手間をかけずにデータ内を移動できるように、特定のパラメーター (列) でデータを並べ替える必要があるとします。したがって、就職面接官が特定の基本的なアルゴリズムについて質問し、コードを使用してそれを実装するタスクを与えることは、まったく不思議ではありません。 ![就職面接の Q&A: Java のアルゴリズム、パート 1 - 1]()
そして、あなたがこの Web サイトにアクセスしているということは、大胆にもあなたが Java で書いていると仮定することにします。だからこそ、今日私は、いくつかの基本的なアルゴリズムと、それらを Java で実装する方法の具体的な例についてよく理解しておくことをお勧めします。「一部」とは次のことを意味します。
![Java university]()
![Java webinar]()
そして、あなたがこの Web サイトにアクセスしているということは、大胆にもあなたが Java で書いていると仮定することにします。だからこそ、今日私は、いくつかの基本的なアルゴリズムと、それらを Java で実装する方法の具体的な例についてよく理解しておくことをお勧めします。「一部」とは次のことを意味します。
- 配列ソートアルゴリズムの概要:
- バブルソート、
- 選択ソート、
- 挿入ソート、
- シェルソート、
- クイックソート、
- マージソート、
- 貪欲なアルゴリズム
- 経路探索アルゴリズム
- 深さ優先検索
- 幅優先検索
- ダイクストラの最短経路優先アルゴリズム
1. ソートアルゴリズムの概要
バブルソート
この並べ替えアルゴリズムは主にその単純さで知られていますが、最も遅いアルゴリズムの 1 つでもあります。例として、数値を昇順でバブルソートする場合を考えてみましょう。ランダムな数列を想像してみましょう。シーケンスの先頭から始めて、これらの番号に対して次の手順を実行します。- 2 つの数値を比較します。
- 左側の数字が大きい場合は、それらを交換します。
- 位置を 1 つ右に移動します。
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
bubbleSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void bubbleSort(int[] array) {
for(int i = array.length -1; i > 1; i--) {
for (int j = 0; j < i; j++) { //
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}
選択の並べ替え
このアルゴリズムはバブル ソートに似ていますが、動作が少し速くなります。もう一度例として、昇順に並べたい一連の数値を考えてみましょう。このアルゴリズムの本質は、すべての数値を順番に反復処理して最小の要素を選択し、それを取得して左端の要素 (0 番目の要素) と交換することです。ここではバブル ソートと似た状況になりますが、この場合、ソートされた要素は最小になります。したがって、要素を通過する次のパスは、インデックス 1 を持つ要素から開始されます。すべての要素が並べ替えられるまで、これらのパスを繰り返します。Java での実装:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
for (int i = 0; i < array.length-1; i++) { // An ordinary outer loop
int min = i;
for (int j = i + 1; j < array.length; j++) { // An ordinary loop, but one that accounts for the sorted numbers
if (array[j] < array[min]) {
min = j;
}
}
int temp = array[i]; // Put the sorted number in the proper cell
array[i] = array[min];
array[min] = temp;
}
}
}
挿入ソート
昇順に並べたいさらに別の数列を考えます。このアルゴリズムは、マーカーを配置することで構成されます。マーカーの左側にあるすべての要素は、要素間ですでに部分的に並べ替えられています。アルゴリズムの各ステップで、要素の 1 つが選択され、部分的にソートされたシーケンス内の目的の位置に配置されます。したがって、ソートされた部分は、すべての要素が検査されるまで拡大します。すでに並べ替えられている要素のサブセットをどのように取得するのか、またマーカーを配置する場所をどのように決定するのか疑問に思っていますか? しかし、最初の要素で構成される配列はすでにソートされていますね。Java での実装を見てみましょう。
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
insertionSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) { // i is the dividing marker
int temp = array[i]; // Make a temporary copy of the marked element
int j = i;
while (j > 0 && array[j - 1] >= temp) { // Until a smaller element is found
array[j] = array[j - 1]; // We shift the element to the right
--j;
}
array[j] = temp; // Insert the marked element in its proper place
}
}
}
シェルソート
このソートは基本的に、修正された挿入ソートです。私は何を話しているのでしょうか？まずは物事を第一に考えましょう。まず間隔を選択する必要があります。この選択を行うには多くのアプローチがあります。これについてはあまり詳しく説明しません。配列を半分に分割して数値を取得しましょう。これが間隔になります。したがって、配列に 9 つの要素がある場合、間隔は 9/2 = 4.5 になります。配列のインデックスは整数のみであるため、小数部分を破棄して 4 を取得します。この間隔を使用してグループを形成します。要素のインデックスが 0 の場合、そのグループ内の次の要素のインデックスは 0+4、つまり 4 になります。3 番目の要素のインデックスは 4+4、4 番目の要素は 8+4 などとなります。2 番目のグループでは、最初の要素は 1,5,9 になります... 3 番目と 4 番目のグループでも、状況は同じになります。結果として、数値配列 {6,3,8,8,6,9,4,11,1} から 4 つのグループが得られます: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} これらは一般配列内での位置を保持しますが、同じグループのメンバーとしてマークしました: {6,3,8,8,6,9,4,11,1} 次に、挿入これらのグループに並べ替えが適用されると、次のようになります。 I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} 一般的な配列では、グループが占めるセルは同じままですが、その内部順序は上記のグループの順序に従って変更されます: {1,3,4,8,6,9,8,11,6} 配列はもう少し注文しましたね？次の間隔は 2 で除算されます: 4/2 = 2 2 つのグループがあります: I — {1,4,6,8,6} II — {3,8,9,11} 一般的な配列では、次のようになります。 : {1,3,4,8,6,9,8,11,6} 両方のグループに対して挿入ソート アルゴリズムを実行し、次の配列を取得します: {1,3,4,8,6,9,6, 11、8} これで、配列はほぼソートされました。アルゴリズムの最後の反復を実行する必要があります。間隔を 2 で割ります: 2/2 = 1。配列全体で構成されるグループを取得します: {1,3,4,8,6,9,6,11 ,8} これに対して挿入ソート アルゴリズムを実行すると、次の結果が得られます: {1,3,4,6,6,8,8,9,11} Java コードでこのソートを実現する方法を見てみましょう。
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
int length = array.length;
int step = length / 2;
while (step > 0) {
for (int numberOfGroup = 1; numberOfGroup < length - step; numberOfGroup++) { // We pass over all of our groups
int j = numberOfGroup;
while (j >= 0 && array[j] > array[j + step]) { // Insertion sort inside the group
int temp = array[j];
array[j] = array[j + step];
array[j + step] = temp;
j--;
}
}
step = step / 2; // Shrink the interval
}
}
}
クイックソート
これは最も人気のあるアルゴリズムの 1 つであるため、特に注意する価値があります。このアルゴリズムの要点は、要素のリストからピボット要素が選択されることです。他のすべての要素をピボット要素を基準にして並べ替えます。ピボット要素より小さい値は左側にあります。右側の値より大きい値。次に、右側と左側の部分でもピボット要素が選択され、同じことが起こります。値はこれらの要素を基準にして並べ替えられます。次に、新しく形成されたパーツ内でピボット要素が選択され、ソートされたシーケンスが得られるまで同様に繰り返されます。このアルゴリズムの次の Java 実装では再帰が使用されます。
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
fastSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void fastSort(int[] array) {
recursionFastSort(array, 0, array.length - 1);
}
public static void recursionFastSort(int[] array, int min, int max) {
if (array.length == 0) // Condition for exiting recursion if the array length is 0
return;
if (min> = max) // Terminate the recursion, since there is nothing to divide
return;
int middle = min + (max - min) / 2; // Select the middle
int middleElement = array[middle];
int i = min, j = max;
while (i <= j) { // Every element less than the middle element will be to the left, and large ones will be to the right
while (array[i] < middleElement) {
i++;
}
while (array[j] > middleElement) {
j--;
}
if (i <= j) { // Swap places
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (min < j) // Make a recursive call on the elements that are less than middle
recursionFastSort(array, min, j);
if (max > i) // Make a recursive call on the elements larger than middle
recursionFastSort(array, i, max);
}
}
マージソート
このタイプも人気です。これは、「分割統治」の原則に基づいた多くのアルゴリズムのうちの 1 つです。このようなアルゴリズムは、まず問題を管理可能な部分に分割します (クイックソートもそのようなアルゴリズムの例です)。では、このアルゴリズムの要点は何でしょうか?分ける：
配列は、ほぼ同じサイズの 2 つの部分に分割されます。これら 2 つの部分はそれぞれ、さらに 2 つに分割され、分割できない最小の部分が残るまで同様に分割されます。各配列に 1 つの要素がある場合、つまり、すでにソートされている配列の場合、最小の分割不可能な部分が得られます。征服する:
ここで、アルゴリズムに「マージ」という名前を付けたプロセスを開始します。これを行うには、結果として得られる 2 つの並べ替えられた配列を取得し、それらを 1 つにマージします。この場合、2 つの配列の最初の要素のうち最小のものが結果の配列に書き込まれます。この操作は、これら 2 つの配列内のすべての要素がコピーされるまで繰り返されます。つまり、2 つの最小配列 {6} と {4} がある場合、それらの値を比較し、この結合結果 {4,6} を生成します。配列 {4,6} と {2,8} をソートした場合、まず値 4 と 2 を比較し、次に結果の配列に 2 を書き込みます。その後、4 と 8 を比較し、4 と書きます。最後に 6 と 8 を比較します。したがって、6 を書き込み、その後にのみ 8 を書き込みます。その結果、次の結合された配列が得られます: {2,4,6,8}。これは Java コードではどのように見えるでしょうか? このアルゴリズムを実行するには、再帰を使用すると便利です。
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
testArr = mergeSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static int[] mergeSort(int[] array1) {
int[] sortArr = Arrays.copyOf(array1, array1.length); // Array for sorting
int[] bufferArr = new int[array1.length];// Buffer array
return recursionMergeSort(sortArr, bufferArr, 0, array1.length);
}
public static int[] recursionMergeSort(int[] sortArr, int[] bufferArr,
int startIndex, int endIndex) {
if (startIndex> = endIndex - 1) { // Return the array when there is only one element left in the array range under consideration
return sortArr;
}
// Make a recursive call to get two sorted arrays:
int middle = startIndex + (endIndex - startIndex) / 2;
int[] firstSortArr = recursionMergeSort(sortArr, bufferArr, startIndex, middle);
int[] secondSortArr = recursionMergeSort(sortArr, bufferArr, middle, endIndex);
// Merge the sorted arrays:
int firstIndex = startIndex;
int secondIndex = middle;
int destIndex = startIndex;
int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
while (firstIndex < middle && secondIndex < endIndex) {
result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
}
while (firstIndex < middle) {
result[destIndex++] = firstSortArr[firstIndex++];
}
while (secondIndex < endIndex) {
result[destIndex++] = secondSortArr[secondIndex++];
}
return result;
}
}
2. 貪欲なアルゴリズム
貪欲アルゴリズムは、最終的なソリューションも最適であるという前提で、各段階で局所的に最適な決定が行われるアプローチです。「最適な」ソリューションとは、特定のステップ/段階で最も明白かつ即座に利益をもたらすソリューションです。このアルゴリズムを調べるために、かなり一般的な問題であるナップザック問題を取り上げてみましょう。少しの間、泥棒になったふりをしてください。あなたはナップザック（リュックサック）を持って夜の店に侵入しました。あなたの目の前には、盗むことができる商品がいくつかあります。しかし同時に、ナップザックの容量には限界があります。30単位以下の重量を運ぶことができます。また、バックパックに収まる最も貴重なグッズ一式も持ち去りたいと考えています。バッグに何を入れるかどうやって決めますか？それで、- まだ取得されていない最も高価なアイテムを選択してください。
- ナップザックに収まる場合は入れます。入らない場合はそのままにしておきます。
- 私たちはもうすべてを盗んでしまったのでしょうか？そうでない場合は、ステップ 1 に戻ります。イエスの場合は、目的を達成したので、すぐに店から逃げます。
public class Item implements Comparable- {
private String name;
private int weight;
private int value;
public Item(String name, int weight, int value) {
this.name = name;
this.weight = weight;
this.value = value;
}
public String getName() {
return name;
}
public int getWeight() {
return weight;
}
public int getValue() {
return value;
}
@Override
public int compareTo(Item o) {
return this.value > o.value ? -1 : 1;
}
}
public class Bag {
private final int maxWeight;
private List<Item> items;
private int currentWeight;
private int currentValue;
public Bag(int maxWeight) {
this.maxWeight = maxWeight;
items = new ArrayList<>();
currentValue = 0;
}
public int getMaxWeight() {
return maxWeight;
}
public int getCurrentValue() {
return currentValue;
}
public int getCurrentWeight() {
return currentWeight;
}
public void addItem(Item item) {
items.add(item);
currentWeight += item.getWeight();
currentValue += item.getValue();
}
}
- maxWeightはバックパックの容量で、オブジェクトの作成時に設定されます。
- items はバックパック内のオブジェクトを表します。
- currentWeight、currentValue — これらのフィールドには、バックパック内のすべてのアイテムの現在の重量と値が保存されます。addItem メソッドで新しいアイテムを追加すると、値が増加します。
public class Solution {
public static void main(String[] args) {
List<Item> items = new ArrayList<>();
items.add(new Item("Guitar", 7, 800));
items.add(new Item("Iron", 6, 500));
items.add(new Item("Tea pot", 3, 300));
items.add(new Item("Lamp", 4, 500));
items.add(new Item("Television", 15, 2000));
items.add(new Item("Vase", 2, 450));
items.add(new Item("Mixer", 2, 400));
items.add(new Item("Blender", 3, 200));
Collections.sort(items);
Bag firstBag = new Bag(30);
fillBackpack(firstBag, items);
System.out.println("Knapsack weight is " + firstBag.getCurrentWeight() +
". The total value of items in the knapsack is " + firstBag.getCurrentValue());
}
}
public static void fillBackpack(Bag bag, List<Item> items) {
for (Item item : items) {
if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
bag.addItem(item);
}
}
}
ナップザックの重量は29です。ナップザック内のアイテムの合計値は3700です
これは貪欲なアルゴリズムの例です。各ステップでローカルに最適なソリューションが選択され、最終的にはグローバルに最適なソリューションが得られます。私たちの場合、最良の選択肢は最も高価なアイテムです。しかし、これが最善の解決策なのでしょうか? バックパックをより合計価値の高いアイテムで埋めるために、ソリューションを少し改善することが可能だと思いませんか? これをどのように行うかを見てみましょう。
public static void effectiveFillBackpack(Bag bag, List- items) {
Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
for (Item item : items) {
sortByRatio.put((double)item.getValue() / item.getWeight(), item);
}
for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
bag.addItem(entry.getValue());
}
}
}
Bag secondBag = new Bag(30);
effectiveFillBackpack(secondBag, items);
System.out.println("The weight of the knapsack is " + secondBag.getCurrentWeight() +
". The total cost of items in the knapsack is " + secondBag.getCurrentValue());
ナップザックの重量は29です。ナップザック内のアイテムの合計コストは4150です。
少しは良くなりましたね。貪欲なアルゴリズムは、最終的なソリューションも最適になることを期待して、すべてのステップで局所的に最適な選択を行います。この仮定は常に有効であるとは限りませんが、多くのタスクでは、貪欲なアルゴリズムによって最適な最終ソリューションが得られます。このアルゴリズムの時間計算量は O(N) です。なかなかいいですね。
GO TO FULL VERSION