QuickSort

QuickSortのプログラムを書いてみました。
再帰を使うと便利ですね。

クイックソートは、

1. データ列からPivotを選ぶ
2. Pivotより大きいものと小さいものに分ける
3. 分けたそれぞれを整列
   というようにソートしていきます。

Pivotが、データ列の中央に位置するような場合は、ソートのなかで計算量が最も少ないアルゴリズムで、計算量はO(nlogn)で済みます。
Pivotが一番端に来るような場合はO(n^2)かかってしまいます。

QuickSort.java

import java.util.*;
public class QuickSort {
    public static boolean debug = false;
    private static int partition(int[] a,int l,int r){
	if(debug)System.out.print("partition l="+l+", r="+r);
	int pivot = a[r];
	int i = l;
	int j = r-1;
	for (;;) {
	    while (a[i] < pivot) ++i;
	    while (i<j && a[j] >= pivot) --j;
	    if(debug) System.out.println("check i="+i+" ,j="+j+" ,pivot="+pivot);
	    if(i>=j) break;
	    if(debug) System.out.println("change i="+i+" ,j="+j);
	    int tmp = a[i];
	    a[i] = a[j];
	    a[j] = tmp;
	}
	int tmp = a[i];
	a[i] = a[r];
	a[r] = tmp;
	return i;
    }
    private static void quickSort(int[] a,int l,int r){
	if(l >= r) return;
	int v = partition(a,l,r);
	if(debug) System.out.println("l="+l+", r="+r+", v"+v+": "+toString(a));
	quickSort(a,l,v-1);
	quickSort(a,v+1,r);
    }
    public static void sort(int[] a){
	quickSort(a,0,a.length-1);
    }
    public static String toString(int[] a){
	StringBuffer sb = new StringBuffer();
	for (int i = 0; i < a.length; i++) sb.append(a[i]+" ");
	return sb.toString();
    }
    public static void main(String[] args) {
	if(args.length > 0 && args[0].equals("-d")) debug = true;
	Scanner sc = new Scanner(System.in);
	System.out.print("データの個数を入力してください ");
	int n = sc.nextInt();
	int[] a = new int[n];
	for (int i = 0; i < n; i++) a[i] = sc.nextInt();
	sort(a);
	System.out.println(toString(a));
    }
}