Javaで基本的なアルゴリズム

@Contents

ソートアルゴリズム

0から100までの乱数を生成し、アルゴリズムを使って昇順に並び替えてみる。

-> 選択法

「ある要素」と「それ以外の要素」を次々に比較。

import java.util.ArrayList;
import java.util.Collections;

public class SelectionSort {
    public static void main(String[] args) {

        ArrayList<Integer> list = new ArrayList<Integer>();

        // 100までの数字を生成
        for (int i = 0; i <= 100; i++) {
            list.add(i);
        }

        // シャッフル
        Collections.shuffle(list);

        // 乱数を出力
        System.out.println(list);

        // 「選択法」で並べ替え
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if (list.get(i) > list.get(j)) {
                    int temp = list.get(i);
                    list.set(i, list.get(j));
                    list.set(j, temp);
                }
            }
        }
        // 並び替えた結果を出力
        System.out.println(list);
    }
}
[67, 32, 47, 9, 17, 14, 78, 83, 43, 75, 62, 31, 24, 94, 53, 6, 70, 39, 86, 77, 7, 52, 51, 97, 20, 26, 68, 23, 41, 21, 28, 34, 5, 38, 72, 57, 90, 2, 46, 69, 40, 65, 85, 50, 59, 25, 73, 93, 35, 44, 66, 63, 30, 22, 92, 8, 11, 36, 29, 99, 74, 91, 3, 61, 79, 18, 49, 42, 45, 37, 33, 84, 12, 55, 13, 48, 96, 1, 0, 87, 19, 80, 95, 54, 56, 71, 98, 16, 10, 76, 27, 82, 89, 64, 60, 81, 4, 15, 58, 88, 100]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]

-> 交換法

最後尾の2要素から次々に「隣同士を比較」。

import java.util.ArrayList;
import java.util.Collections;

public class BubbleSort {
    public static void main(String[] args) {

        ArrayList<Integer> list = new ArrayList<Integer>();

        // 100までの数字を生成
        for (int i = 0; i <= 100; i++) {
            list.add(i);
        }

        // シャッフル
        Collections.shuffle(list);

        // 乱数を出力
        System.out.println(list);

        // 「交換法」で並べ替え
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = list.size() - 1; j > i; j--) {
                if (list.get(j - 1) > list.get(j)) {
                    int temp = list.get(j - 1);
                    list.set(j - 1, list.get(j));
                    list.set(j, temp);
                }
            }
        }
        // 並び替えた結果を出力
        System.out.println(list);
    }
}
[24, 56, 0, 89, 20, 67, 66, 47, 57, 35, 28, 90, 25, 33, 97, 12, 7, 100, 71, 51, 52, 45, 6, 43, 95, 39, 8, 30, 32, 40, 73, 81, 91, 4, 60, 54, 64, 16, 19, 70, 69, 75, 74, 88, 29, 65, 55, 49, 11, 17, 9, 31, 23, 22, 82, 46, 62, 41, 83, 77, 18, 21, 99, 5, 48, 26, 44, 42, 68, 14, 96, 2, 1, 93, 10, 13, 37, 3, 79, 85, 53, 50, 58, 15, 59, 94, 27, 72, 76, 80, 87, 92, 61, 86, 98, 36, 78, 38, 84, 63, 34]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]

-> 挿入法

新しいリストの末尾に既存のリストの要素を挿入し、最後尾の要素と挿入した要素を比較。

import java.util.ArrayList;
import java.util.Collections;

public class InsertionSort {
    public static void main(String[] args) {

        ArrayList<Integer> list = new ArrayList<Integer>();

        // 100までの数字を生成
        for (int i = 0; i <= 100; i++) {
            list.add(i);
        }

        // シャッフル
        Collections.shuffle(list);

        // 乱数を出力
        System.out.println(list);

        ArrayList<Integer> new_list = new ArrayList<Integer>(100);

        // 「挿入法」で並べ替え
        for (int i = 0; i < list.size(); i++) {
            new_list.add(i);
            for (int j = i; j > 0; j--) {
                if (new_list.get(j - 1) > new_list.get(j)) {
                    int temp = new_list.get(j - 1);
                    new_list.set(j - 1, new_list.get(j));
                    new_list.set(j, temp);
                }
            }
        }
        // 並び替えた結果を出力
        System.out.println(new_list);
    }
}
[60, 6, 93, 92, 26, 19, 32, 96, 27, 48, 35, 50, 88, 23, 22, 10, 13, 73, 4, 7, 31, 44, 89, 56, 47, 80, 51, 20, 66, 54, 36, 58, 17, 100, 49, 84, 11, 2, 9, 87, 25, 16, 46, 75, 53, 81, 34, 64, 67, 68, 76, 29, 71, 62, 78, 57, 1, 97, 3, 99, 38, 39, 15, 28, 45, 8, 63, 90, 21, 40, 43, 86, 33, 52, 94, 65, 61, 42, 69, 77, 91, 70, 82, 41, 74, 83, 98, 5, 59, 24, 55, 95, 0, 72, 30, 85, 18, 37, 14, 12, 79]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]

-> 更新予定

アルゴリズムは他にも沢山あるから、随時試してみる予定↓

  • シェルソート
    • 間隔の離れた要素の組に対してソートを行い、だんだんと比較する要素間の間隔を小さくしながらソートを繰り返す
    • 単純に近くの要素を比較する場合よりも速く、要素を所定の位置に移動させられる
  • クイックソート
    • 実用上もっとも高速な並べ替えアルゴリズム
    • ピボットと呼ぶ要素を軸に分割を繰り返して整列を行う
      • 分割統治法
  • マージソート
    • 並べ替えたい配列を再帰的に分割していき、再び併合して並び替えるアルゴリズム
  • 線形探索
    • リストや配列に入ったデータに対する検索する際に先頭から順に比較を行い、それが見つかれば終了
  • 二分探索(バイナリサーチ)
    • 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索
    • 未ソートのリストや大小関係の定義されない要素を含むリストには使用不可
  • 動的計画法
    • 対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法
    • 特定のアルゴリズムを指すのではなく、上記のような手法を使うアルゴリズムの総称

おまけ

-> エラトステネスのふるい

  • エラトステネスのふるいとは指定された整数以下の全ての素数を発見するための単純なアルゴリズムのこと
  • 素数とは、自明な正の因数(1と自分自身)以外に因数を持たない自然数
public class PrimeNumber {
    public static void main(String[] args) {

        for (int i = 2; i <= 100; i++) {
            if (i != 2 && i % 2 == 0) {
                continue;
            } else if (i != 3 && i % 3 == 0) {
                continue;
            } else if (i != 5 && i % 5 == 0) {
                continue;
            } else if (i != 7 && i % 7 == 0) {
                continue;
            } else {
                System.out.print(i + " ");
            }
        }
    }
}
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

To comment

@Contents
閉じる