Posted at

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));
}
}