ソートアルゴリズムの実装

一般的？なソートアルゴリズムのJava実装まとめ。

• 選択法（セレクションソート）
• 交換法（バブルソート）
• 挿入法（インサーションソート）
• シェルソート
• クイックソート

選択法（セレクションソート）

import java.util.Arrays;

public class SelectionSort {

	public static void main(String[] args) {

		int[] array = new int[] { 5, 4, 6, 7, 1, 9, 8, 2, 3 };

		for (int i = 0; i < array.length; i++) {
			int min = i;
			for (int j = i + 1; j < array.length; j++){
				if (array[min] > array[j]){
					min = j;
				}
			}
			int tmp = array[i];
			array[i] = array[min];
			array[min] = tmp;
		}
		System.out.println(Arrays.toString(array));
	}
}

交換法（バブルソート）

import java.util.Arrays;

public class BubbleSort {

	public static void main(String[] args) {

		int[] array = new int[] { 5, 4, 6, 7, 1, 9, 8, 2, 3 };
		
		for(int i = 0; i < array.length; i++){
			for(int j = 0; j < array.length - 1 - i; j++){
				if(array[j] > array[j + 1]){
					int tmp = array[j];
					array[j] = array[j + 1];
					array[j + 1] = tmp;
				}
			}
		}
		System.out.println(Arrays.toString(array));
	}
}

挿入法（インサーションソート）

import java.util.Arrays;

public class InsertionSort {

	public static void main(String[] args) {

		int[] array = new int[] { 5, 4, 6, 7, 1, 9, 8, 2, 3 };
		
		for(int i = 1; i < array.length; i++){
			int insertionData = array[i];
			int j = i;
			for(; j >= 1 && array[j - 1] > insertionData; j--){
				array[j] = array[j - 1];
			}
			array[j] = insertionData;
		}
		System.out.println(Arrays.toString(array));
	}
}

シェルソート

import java.util.Arrays;

public class ShellSort {

	public static void main(String[] args) {

		int[] array = new int[] { 5, 4, 6, 7, 1, 9, 8, 2, 3 };

		// 間隔は 4, 2, 1, 0と狭まっていく
		for (int range = array.length / 2; range > 0; range /= 2) {
			// 間隔内での移動
			for (int h = 0; h < range; h++) {
				// ここから挿入法
				// ソート対象データは間隔ごとの要素になるのでループの増分値はi += range
				for (int i = h + range; i < array.length; i += range) {
					int insertionData = array[i];
					int j = i;
					for (; j >= range && array[j - range] > insertionData; j -= range) {
						array[j] = array[j - range];
					}
					array[j] = insertionData;
				}
			}
		}
		System.out.println(Arrays.toString(array));
	}
}

クイックソート

import java.util.Arrays;

public class QuickSort {

	public static void main(String[] args) {

		int[] array = new int[] { 5, 4, 6, 7, 1, 9, 8, 2, 3 };

		sort(array, 0, array.length - 1);
		System.out.println(Arrays.toString(array));
	}

	private static void sort(int[] array, int left, int right) {
		if (left <= right) {
			// 基準値
			int pivotData = array[(left + right) / 2];
			int leftPointer = left;
			int rightPointer = right;

			while (leftPointer <= rightPointer) {
				// 左から基準値を超える要素を探す。（存在しない場合は基準値自体が対象となる）
				while (array[leftPointer] < pivotData) {
					leftPointer++;
				}
				// 右から基準値を超える要素を探す。（存在しない場合は基準値自体が対象となる）
				while (array[rightPointer] > pivotData) {
					rightPointer--;
				}

				if (leftPointer <= rightPointer) {
					int tmp = array[leftPointer];
					array[leftPointer] = array[rightPointer];
					array[rightPointer] = tmp;
					leftPointer++;
					rightPointer--;
				}
			}
			// 左半分、右半分を再帰的に呼び出す
			sort(array, left, rightPointer);
			sort(array, leftPointer, right);
		}
	}
}