01: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
02:
03: This file is part of the db4o open source object database.
04:
05: db4o is free software; you can redistribute it and/or modify it under
06: the terms of version 2 of the GNU General Public License as published
07: by the Free Software Foundation and as clarified by db4objects' GPL
08: interpretation policy, available at
09: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
10: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
11: Suite 350, San Mateo, CA 94403, USA.
12:
13: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
14: WARRANTY; without even the implied warranty of MERCHANTABILITY or
15: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16: for more details.
17:
18: You should have received a copy of the GNU General Public License along
19: with this program; if not, write to the Free Software Foundation, Inc.,
20: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
21: package com.db4o.foundation;
22:
23: /**
24: * @exclude
25: */
26: public class Algorithms4 {
27:
28: private static class Range {
29: int _from;
30: int _to;
31:
32: public Range(int from, int to) {
33: _from = from;
34: _to = to;
35: }
36: }
37:
38: public static void qsort(QuickSortable4 sortable) {
39: Stack4 stack = new Stack4();
40: addRange(stack, 0, sortable.size() - 1);
41: qsort(sortable, stack);
42: }
43:
44: private static void qsort(QuickSortable4 sortable, Stack4 stack) {
45: while (!stack.isEmpty()) {
46: Range range = (Range) stack.peek();
47: stack.pop();
48: int from = range._from;
49: int to = range._to;
50: int pivot = to;
51: int left = from;
52: int right = to;
53: while (left < right) {
54: while (left < right
55: && sortable.compare(left, pivot) < 0) {
56: left++;
57: }
58: while (left < right
59: && sortable.compare(right, pivot) >= 0) {
60: right--;
61: }
62: swap(sortable, left, right);
63: }
64: swap(sortable, to, right);
65: addRange(stack, from, right - 1);
66: addRange(stack, right + 1, to);
67: }
68: }
69:
70: private static void addRange(Stack4 stack, int from, int to) {
71: if (to - from < 1) {
72: return;
73: }
74: stack.push(new Range(from, to));
75: }
76:
77: private static void swap(QuickSortable4 sortable, int left,
78: int right) {
79: if (left == right) {
80: return;
81: }
82: sortable.swap(left, right);
83: }
84:
85: }
|