|
/* Copyright (c) 1995-2000, The Hypersonic SQL Group.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the Hypersonic SQL Group nor the names of its
* contributors may be used to endorse or promote products derived from this
* software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE HYPERSONIC SQL GROUP,
* OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* This software consists of voluntary contributions made by many individuals
* on behalf of the Hypersonic SQL Group.
*
*
* For work added by the HSQL Development Group:
*
* Copyright (c) 2001-2009, The HSQL Development Group
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the HSQL Development Group nor the names of its
* contributors may be used to endorse or promote products derived from this
* software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
* OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/**
* FastQSorts the [l,r] partition (inclusive) of the specfied array of Rows,
* using the comparator.
*
* Modified from the original method in Hypersonic with the addition of the
* comparator. (fredt@users)
*
* @author Thomas Mueller (Hypersonic SQL Group)
* @version 1.7.2
* @since 1.7.2
*/
public class Sort {
public static final void sort(Object[] w, ObjectComparator comparator, int l, int r) {
int i;
int j;
Object p;
if (l > r) {
return;
}
while (r - l > 10) {
i = (r + l) >>> 1;
if (comparator.compare(w[l], w[r]) > 0) {
swap(w, l, r);
}
if (comparator.compare(w[i], w[l]) < 0) {
swap(w, l, i);
} else if (comparator.compare(w[i], w[r]) > 0) {
swap(w, i, r);
}
j = r - 1;
swap(w, i, j);
p = w[j];
i = l;
while (true) {
while (comparator.compare(w[++i], p) < 0) {
;
}
while (comparator.compare(w[--j], p) > 0) {
;
}
if (i >= j) {
break;
}
swap(w, i, j);
}
swap(w, i, r - 1);
sort(w, comparator, l, i - 1);
l = i + 1;
}
for (i = l + 1; i <= r; i++) {
Object t = w[i];
for (j = i - 1; j >= l && comparator.compare(w[j], t) > 0; j--) {
w[j + 1] = w[j];
}
w[j + 1] = t;
}
}
/**
* Swaps the a'th and b'th elements of the specified Row array.
*/
private static void swap(Object[] w, int a, int b) {
Object t = w[a];
w[a] = w[b];
w[b] = t;
}
}
interface ObjectComparator {
int compare(Object a, Object b);
}
|
![FastQSorts the [l,r] partition (inclusive) of the specfied array of Rows, using the comparator.](../../JavaImages/Sort.PNG)
