Javaでクイックソート(quicksort)
クラスQuickSortは状態(ステート,state)を持たないから、インスタンス化する必要がないかも。
メソッドをstaticで書きなおしていい気がする。
それにしてもJavaはコードが長くなる。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
import java.util.*; public class Main { public static void main(String[] args) throws Exception { QuickSort q = new QuickSort(); int size = 20; int[] a = new int[size]; q.setRandomForArray(a); dispArrayLine(a); q.quicksort(a); dispArrayLine(a); } public static void dispArrayList(int[] a){ for(int i=0; i<a.length; i++){ System.out.println(i + " => " + a[i]); } } public static void dispArrayLine(int[] a){ for(int i=0; i<a.length; i++){ System.out.print(a[i] + " "); } System.out.println(); } } class QuickSort { public Random mRandom; public QuickSort(){ this.mRandom = new Random(); } public int getRandomInt(int min, int max){ return min + this.mRandom.nextInt(max-min+1); } public void setRandomForArray(int[] a, int min, int max){ for(int i=0; i<a.length; i++){ a[i] = this.getRandomInt(min, max); } } public void setRandomForArray(int[] a){ int min = 0; int max = 9; this.setRandomForArray(a, min, max); } public void swap(int[] a, int l, int r){ int t = a[l]; a[l] = a[r]; a[r] = t; } public int getPivot(int a, int b, int c){ if(a>b){ if(b>c){ return b; }else{ return a>c?c:a; } }else{ if(a>c){ return a; }else{ return b>c?c:b; } } } public void quicksort(int[] a, int left, int right){ if(right<=left){ return; } int l = left; int r = right; int p = this.getPivot(a[l], a[l+1], a[r]); while(true){ while(a[l]<p){ l++; } while(p<a[r]){ r--; } if(r<=l){ break; } this.swap(a,l,r); l++; r--; } this.quicksort(a, left, l-1); this.quicksort(a, r+1, right); } public void quicksort(int[] a){ int left = 0; int right = a.length-1; this.quicksort(a, left, right); } } |
