|
345
|
1 package alice.test.codesegment.local.bitonicsort;
|
|
|
2
|
|
|
3 public class Sort {
|
|
|
4
|
|
|
5 // this method has "stack overflow" problem
|
|
|
6 public static void quickSort(DataList data){
|
|
|
7 int[] stack = new int[8192];
|
|
|
8 int sp = 0;
|
|
|
9 int begin = 0;
|
|
|
10 int end = data.table.length-1; // index is up to length-1
|
|
|
11 while(true){
|
|
|
12 while(begin < end){
|
|
|
13 if (end-begin< 40){
|
|
|
14 bubbleSort(data,begin,end);
|
|
|
15 break;
|
|
|
16 } else {
|
|
|
17 int where = (begin+end)/2;
|
|
|
18 int pivot = data.table[where];
|
|
|
19 data.table[where] = data.table[begin];
|
|
|
20 int p = begin;
|
|
|
21 for (int i=begin+1;i<=end;i++){
|
|
|
22 if (data.table[i]<pivot){
|
|
|
23 p++;
|
|
|
24 if (i!=p)data.swap(p,i);
|
|
|
25 }
|
|
|
26 }
|
|
|
27 data.table[begin] = data.table[p];
|
|
|
28 data.table[p] = pivot;
|
|
|
29 stack[sp++] = p+1;
|
|
|
30 stack[sp++] = end;
|
|
|
31 end=p-1;
|
|
|
32 }
|
|
|
33 }
|
|
|
34 if (sp==0) return;
|
|
|
35 end = stack[--sp];
|
|
|
36 begin = stack[--sp];
|
|
|
37
|
|
|
38 }
|
|
|
39 }
|
|
|
40
|
|
|
41 public static void bubbleSort(DataList data ,int begin,int end){
|
|
|
42 for (int i=begin;i<end;i++){
|
|
|
43 for (int j=end;j>i;j--){
|
|
|
44 if (data.table[i] > data.table[j]){
|
|
|
45 data.swap(i,j);
|
|
|
46 }
|
|
|
47 }
|
|
|
48 }
|
|
|
49
|
|
|
50
|
|
|
51 }
|
|
|
52
|
|
|
53 public static void check(DataList data){
|
|
|
54 System.out.println("checking ....");
|
|
|
55 for (int i = 0; i< data.table.length-1; i++){
|
|
|
56 if (data.table[i] > data.table[i+1]){
|
|
|
57 System.out.println("MISS "+data.table[i]+" > "+data.table[i+1]+" Position is "+i);
|
|
|
58 return;
|
|
|
59 }
|
|
|
60 }
|
|
|
61 System.out.println("sort is succeed");
|
|
|
62 }
|
|
|
63 }
|
