クイックソートのアルゴリズムを実装してみた

ソート(並び替え)のアルゴリズム

今回はソートが速いと言われている「クイックソート」編。
クイックソートがどんなものか知りたいかたは動画の方でご覧ください。
https://www.youtube.com/watch?v=a3yXjNhGwt0&t=1s

クイックソートをプログラムで書くとこうなります。

package sort;

/**
 * クイックソート
 */
public class QuickSort {

	public static void main(String[] args) {
		
		int array[] = {7, 4, 9, 2, 3, 8, 6, 1, 5};
		arrayPrint(array);
		quickSort(array, 0, array.length - 1);
		
	}
	
	/**
	 * ソート処理
	 * @param array
	 */
	static public void quickSort(int array[], int left, int right) {
		
		if (right - left == 0)
			return;
		
		// 基準として適当に中点をpivotに決める
		int pivotIndex = (left + right) / 2;
		int pivot = array[pivotIndex];
		
		swap(array, pivotIndex, right);
		
		int leftIndex = left;
		for (int count = left; count <= right; count++) {
			if (array[count] <= pivot) {
				swap(array, leftIndex, count);
				if (right != leftIndex) {
					leftIndex++;
				}
			}
		}
		
		// 再帰的処理
		quickSort(array, left, leftIndex-1);
		quickSort(array, leftIndex, right);
	}
	
	/**
	 * 配列入れ替え用
	 * @param array 配列
	 * @param num1
	 * @param num2
	 */
	static public void swap(int array[], int num1, int num2) {
		
		int tmp = array[num1];
		array[num1] = array[num2];
		array[num2] = tmp;
		arrayPrint(array);
	}
	
	/**
	 * 配列出力用
	 * @param array
	 */
	static public void arrayPrint(int array[]) {
		int count = 0;
		for (int a : array) {
			System.out.print(a);
			count++;
			if (count != array.length) {
				System.out.print(", ");
			}
		}
		System.out.println();
	}
}

途中経過も出力させてみてます。こうなっています。

7, 4, 9, 2, 5, 8, 6, 1, 3
2, 4, 9, 7, 5, 8, 6, 1, 3
2, 1, 9, 7, 5, 8, 6, 4, 3
2, 1, 3, 7, 5, 8, 6, 4, 9
2, 3, 1, 7, 5, 8, 6, 4, 9
1, 3, 2, 7, 5, 8, 6, 4, 9
1, 2, 3, 7, 5, 8, 6, 4, 9
1, 2, 3, 7, 5, 8, 6, 4, 9
1, 2, 3, 7, 5, 8, 6, 4, 9
1, 2, 3, 7, 5, 9, 6, 4, 8
1, 2, 3, 7, 5, 9, 6, 4, 8
1, 2, 3, 7, 5, 9, 6, 4, 8
1, 2, 3, 7, 5, 6, 9, 4, 8
1, 2, 3, 7, 5, 6, 4, 9, 8
1, 2, 3, 7, 5, 6, 4, 8, 9
1, 2, 3, 7, 5, 8, 4, 6, 9
1, 2, 3, 5, 7, 8, 4, 6, 9
1, 2, 3, 5, 4, 8, 7, 6, 9
1, 2, 3, 5, 4, 6, 7, 8, 9
1, 2, 3, 5, 6, 4, 7, 8, 9
1, 2, 3, 4, 6, 5, 7, 8, 9
1, 2, 3, 4, 5, 6, 7, 8, 9
1, 2, 3, 4, 5, 6, 7, 8, 9
1, 2, 3, 4, 5, 6, 7, 8, 9
1, 2, 3, 4, 5, 6, 8, 7, 9
1, 2, 3, 4, 5, 6, 7, 8, 9
1, 2, 3, 4, 5, 6, 7, 8, 9

ソートのアルゴリズム勉強編。クイックソートのプログラムの紹介でした。

参考になれば嬉しいです。