|
1
21 package com.db4o.foundation;
22
23
24
27 public class Algorithms4 {
28
29 private static class Range {
30 int _from;
31 int _to;
32
33 public Range(int from, int to) {
34 _from = from;
35 _to = to;
36 }
37 }
38
39 public static void qsort(QuickSortable4 sortable) {
40 Stack4 stack=new Stack4();
41 addRange(stack, 0, sortable.size()-1);
42 qsort(sortable,stack);
43 }
44
45 private static void qsort(QuickSortable4 sortable, Stack4 stack) {
46 while(!stack.isEmpty()) {
47 Range range=(Range)stack.peek();
48 stack.pop();
49 int from=range._from;
50 int to=range._to;
51 int pivot = to;
52 int left = from;
53 int right = to;
54 while (left<right) {
55 while (left<right && sortable.compare(left,pivot)<0) {
56 left++;
57 }
58 while(left<right && sortable.compare(right,pivot)>=0) {
59 right--;
60 }
61 swap(sortable, left, right);
62 }
63 swap(sortable, to, right);
64 addRange(stack, from, right-1);
65 addRange(stack, right+1, to);
66 }
67 }
68
69 private static void addRange(Stack4 stack,int from,int to) {
70 if (to-from < 1) {
71 return;
72 }
73 stack.push(new Range(from,to));
74 }
75
76 private static void swap(QuickSortable4 sortable, int left, int right) {
77 if (left == right) {
78 return;
79 }
80 sortable.swap(left, right);
81 }
82
83 }
84 |
Popular Tags |
Java API By Example, From Geeks To Geeks.