Mercurial > hg > Members > tatsuki > Alice
view src/main/java/alice/test/codesegment/local/bitonicsort/Sort.java @ 393:38021fceabef draft multicast
test commit
author | tatsuki |
---|---|
date | Tue, 17 Jun 2014 17:39:47 +0900 |
parents | 8f71c3e6f11d |
children |
line wrap: on
line source
package alice.test.codesegment.local.bitonicsort; public class Sort { // this method has "stack overflow" problem public static void quickSort(DataList data){ int[] stack = new int[8192]; int sp = 0; int begin = 0; int end = data.table.length-1; // index is up to length-1 while(true){ while(begin < end){ if (end-begin< 40){ bubbleSort(data,begin,end); break; } else { int where = (begin+end)/2; int pivot = data.table[where]; data.table[where] = data.table[begin]; int p = begin; for (int i=begin+1;i<=end;i++){ if (data.table[i]<pivot){ p++; if (i!=p)data.swap(p,i); } } data.table[begin] = data.table[p]; data.table[p] = pivot; stack[sp++] = p+1; stack[sp++] = end; end=p-1; } } if (sp==0) return; end = stack[--sp]; begin = stack[--sp]; } } public static void bubbleSort(DataList data ,int begin,int end){ for (int i=begin;i<end;i++){ for (int j=end;j>i;j--){ if (data.table[i] > data.table[j]){ data.swap(i,j); } } } } public static void check(DataList data){ System.out.println("checking ...."); for (int i = 0; i< data.table.length-1; i++){ if (data.table[i] > data.table[i+1]){ System.out.println("MISS "+data.table[i]+" > "+data.table[i+1]+" Position is "+i); return; } } System.out.println("sort is succeed"); } }