クイックソート

勉強がてらJavaでクイックソートを実装してみました。
partionメソッドのピボットの選び方や要素数が少ない場合は、挿入ソートに切り替えるなど
改善の余地はありますが、また時間があればやってみます。

import java.util.Random;
public class QuickSort {

 static int NO = 1000000;

 public static void main(String[] args) {
  
  int A[] = makeArray(NO);
  sort(A, 0, A.length - 1);
  for (int b : A) {
    System.out.println(b);
  }
 
 }

 public static void sort(int[] A, int left, int right) {
  
  if (left < right) {
   int p = partition(A, left, right);
   sort(A, left, p - 1);
   sort(A, p + 1, right);
  }
 
 }

 private static int partition(int[] A, int left, int right) {
 
  int p = A.length % (right - left) + left;
  swap(A, right, p);

  int store = left;
  for(int i=left; i<right; ++i) {
   if(A[i] <= A[right]) {
   swap(A, store, i);
   ++store;
   }
  }
  
  swap(A, store, right);
  return store;
 }
 
 private static void swap(int[] A, int a, int b) {
  int tmp = A[a];
  A[a] = A[b];
  A[b] = tmp;
 }
 
 private static int[] makeArray(int no) {
  Random random = new Random();
  int[] A = new int[no];
  for(int i=0; i<no; ++i) {
   A[i] = random.nextInt(no); 
  }
  return A;
 }
}