Java
様々なソートアルゴリズムを試してみる
kght6123
解説
Javaの配列の中の値を並び替えする、アルゴリズムを実現するコードをいろいろ作ってみたので
その時のロジックを紹介します！
記憶にないですが、確か、プログラミングコンテスト向けに勉強したときのものだと思います。
どなたかの参考になれば、、、、と思います。
（総称型を使って、大体の型で使えるように意識して作ってます。）
ソースコード
public static void main(final String... args) {
final Integer[] values = new Integer[]{42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69};
sort(values);
final Integer[] values1 = new Integer[]{5, 4, 6, 1, 2, 7, 3};
sort(values1);
}
private static void sort(final Integer[] values) {
System.out.print("raw : ");
System.out.println(out(values, " "));
System.out.print("bubble : ");
System.out.println(out(bubble(copy(values, new Integer[values.length])), " "));
System.out.print("selection : ");
System.out.println(out(selection(copy(values, new Integer[values.length])), " "));
System.out.print("insertion : ");
System.out.println(out(insertion(copy(values, new Integer[values.length])), " "));
System.out.print("merge : ");
System.out.println(out(merge(copy(values, new Integer[values.length])), " "));
System.out.print("quick : ");
System.out.println(out(quick(copy(values, new Integer[values.length])), " "));
}
private static <T> T[] copy(final T[] src, final T[] dest) {
System.arraycopy(src, /*srcPos*/0, dest, /*destPos*/0, /*length*/src.length);
return dest;
}
private static <T> String out(final T[] values, final String c) {
String out = "";
for(T value : values) {
out = out.concat(value.toString()).concat(c);
}
return out;
}
/**
* バブルソート（Collections.sortで代用可能）
*
* 一番下の要素から順に、下の要素を上の要素と比較して、下の方が小さければ互いに交換。
*
* @param values
* @return
*/
public static <T extends Comparable<T>> T[] bubble(final T[] values) {
return bubble(values, 0, values.length);
}
public static <T extends Comparable<T>> T[] bubble(final T[] values, final int from, final int to) {
final int length = to - 1;
// 一番下の要素から順にループし、一番先頭に移動した最小値はループから除外
for (int i = from; i < length; i++) {
for (int j = length; j > i; j--) {
// まだ並び替えしてない範囲のとき
// 前後の値を比較
final T prev = values[j-1];
final T now = values[j];
if(prev.compareTo(now) > 0) {
// 値の入れ替え
values[j-1] = now;
values[j] = prev;
}
//System.out.println(out(values, " "));
}
//System.out.println(out(values, " "));
}
return values;
}
/**
* 選択ソート（Collections.sortで代用可能）
*
* 最小値を「選択」し、順に並べていく
*
* @param values
* @return
*/
public static <T extends Comparable<T>> T[] selection(final T[] values) {
final int length = values.length - 1;
// 一番下の要素から順にループし、一番先頭に移動した最小値はループから除外
for (int i = 0; i < length; i++) {
int min_i = length;
for (int j = length; j > i; j--) {
// 前後の値を比較
if(values[j-1].compareTo(values[min_i]) < 0) {
min_i = j-1;
}
//System.out.println(out(values, " "));
}
// 値の入れ替え
final T temp = values[min_i];
values[min_i] = values[i];
values[i] = temp;
//System.out.println(out(values, " "));
}
return values;
}
/**
* 挿入ソート（Collections.sortで代用可能）
*
* 小さい整列済みに新たな要素を「挿入」し、整列済みの範囲を拡大する
* ☆ 図にした方が良いかも ☆
*
* @param values
* @return
*/
public static <T extends Comparable<T>> T[] insertion(final T[] values) {
final int length = values.length;
for (int i = 1; i < length; i++) {
final T select = values[i];
if (select.compareTo(values[i - 1]) < 0) {
// 一つ前の値が、今の値（select）より大きいとき
// 今の値（select）を適切な位置に値を挿入する
int j = i;
do {
// 前方向に検索し、値をひとつ後方にずらしていく
values[j] = values[j - 1];// ひとつ前の値で次の値を上書き
j--;// 前へ
} while(j > 0 // 「0」より大きい間だけ処理
&& select.compareTo(values[j - 1]) < 0);// 前の前の値は今の値（select）より大きい
values[j] = select;// 今の値（select）を適切な位置に設定
}
}
return values;
}
/**
* マージソート
*
* 並べ替えたい配列を再帰的に分割していき、再び併合（マージ）していくことで、並び替えを実現
* ☆ 図にした方が良いかも ☆
*
* 処理上は本当に配列を分割しない。
*
* @param values
* @return
*/
public static <T extends Comparable<T>> T[] merge(final T[] values) {
final int length = values.length;
// 分割範囲を作るループ
for (int split = 2; split < length; split+=2) {
// 分割範囲ごとにソートするループ
for (int from = 0; from < length; from+=split) {
// バブルソートを範囲指定できるようにして、分割範囲のみをソート
final int to = from + split;
if(to > length)
bubble(values, from, length);
else
bubble(values, from, to);
}
}
return values;
}
/**
* クイックソート
*
* 軸要素を選択（先頭）し、配列全体を軸より大きいと小さいに分割する
* ☆ 図にした方が良いかも ☆
*
* 処理上は本当に配列を分割しない。
*
* @param values
* @return
*/
public static <T extends Comparable<T>> T[] quick(final T[] values) {
//final int length = values.length;
// 軸を設定、左側に空きができる
int left = 0;
int right = values.length - 1;
final T jiku = values[left];
// 右と左の値が等しくなる（軸の位置になる）までループ
while (left < right) {
// 右側から軸より小さい値を探す（みつからなかったら軸は最小値、leftの位置が先頭に）
for (;jiku.compareTo(values[right]) < 0 && left < right; right--){}
if (left < right) {
values[left] = values[right];// 小さい値と左側の空きを入れ替える、右側に空きができる
left++;// 小さい値が左側に入ったので次へ
}
// 左側から軸より大きい値を探す（みつからなかったら軸は最大値、leftの位置が末尾に）
for (;jiku.compareTo(values[left]) > 0 && left < right; left++){}
if (left < right) {
values[right] = values[left];// 大きい値と右側の空きを入れ替える、左側に空きができる
right--;// 大きい値が右側に入ったので次へ
}
}
values[left] = jiku;// 軸の位置を設定
return values;
}