java sorting with comparator and swap function

I need to sorting function with custom comparator and swap function. I can write one myself, but I'm wondering if someone else didn't already do it. Java runtime contains many specialized sorting function for sorting arrays of primitive types, objects etc., but none of them take swap function as an argument. Google search also didn't find anything useful.

public interface IntComparator
{
    int compare(int a, int b);
}
public interface IntSwap
{
    void swap(int a, int b);
}
publi开发者_StackOverflowc static void sort(IntComparator compFn, IntSwap swapFn, int off, int len);

Here is what I was looking for. It's based on java runtime algorithm for sorting integers. With proper implementation of Sortable interface, it can sort just about anything.

public class Sort {
    public static void sort(Sortable sortable, int off, int len) {
        // Insertion sort on smallest arrays
        if (len < 7) {
            for (int i = off; i < len + off; i++) {
                for (int j = i; j > off && sortable.compare(j - 1, j) > 0; j--) {
                    sortable.swap(j, j - 1);
                }
            }
            return;
        }


    // Choose a partition element, v
    int m = off + (len >> 1); // Small arrays, middle element
    if (len > 7) {
        int l = off;
        int n = off + len - 1;
        if (len > 40) { // Big arrays, pseudomedian of 9
            int s = len / 8;
            l = med3(sortable, l, l + s, l + 2 * s);
            m = med3(sortable, m - s, m, m + s);
            n = med3(sortable, n - 2 * s, n - s, n);
        }
        m = med3(sortable, l, m, n); // Mid-size, med of 3
    }

    // Establish Invariant: v* (<v)* (>v)* v*
    int a = off, b = a, c = off + len - 1, d = c;
    while (true) {
        while (b <= c && sortable.compare(b, m) <= 0) {
            if (sortable.compare(b, m) == 0) {
                sortable.swap(a, b);
                m = a;
                a++;
            }
            b++;
        }
        while (c >= b && sortable.compare(c, m) >= 0) {
            if (sortable.compare(c, m) == 0) {
                sortable.swap(c, d);
                m = d;
                d--;
            }
            c--;
        }
        if (b > c) {
            break;
        }
        sortable.swap(b++, c--);
    }

    // Swap partition elements back to middle
    int s, n = off + len;
    s = Math.min(a - off, b - a);
    vecswap(sortable, off, b - s, s);
    s = Math.min(d - c, n - d - 1);
    vecswap(sortable, b, n - s, s);

    // Recursively sort non-partition-elements
    if ((s = b - a) > 1) {
        sort(sortable, off, s);
    }
    if ((s = d - c) > 1) {
        sort(sortable, n - s, s);
    }
}

private static int med3(Sortable sortable, int a, int b, int c) {
    return sortable.compare(a, b) < 0 ? (sortable.compare(b, c) < 0 ? b : sortable.compare(a, c) < 0 ? c : a)
            : sortable.compare(b, c) > 0 ? b : sortable.compare(a, c) > 0 ? c : a;
}

private static void vecswap(Sortable sortable, int a, int b, int n) {
    for (int i = 0; i < n; i++, a++, b++) {
        sortable.swap(a, b);
    }
}

}

I need to swap indices in two arrays. I know that I could sort twodimensional array but that would increase required memory.

No. If I understand you correctly, it does not result in any overhead.

Remember that Java does not store arrays or objects directly in variables (or arrays!). It stores references. Even if each element referred to from an array is 40 bytes large, it will be stored as a reference in the array.

Thus, I suggest you go with the built in sorting mechanisms. They won't shuffle around lots of data, only the references.

Because sort() for an array of Object is stable, you may be able to get useful information inside a custom Comparator. This one counts swaps while sorting by String length.

import java.util.Arrays;
import java.util.Comparator;

/** @see http://stackoverflow.com/questions/4983746 */
public class SortTest {

    private static class LengthComparator implements Comparator<String> {

        private int count;

        public int compare(String s1, String s2) {
            int a = s1.length();
            int b = s2.length();
            if (a < b) {
                return -1;
            } else if (a > b) {
                count++;
                return 1;
            } else {
                return 0;
            }
        }
    }

    public static void main(String[] args) throws Exception {
        String[] sa = {"One", "Two", "Three", "Four", "Five"};
        System.out.println(Arrays.toString(sa));
        LengthComparator byLength = new LengthComparator();
        Arrays.sort(sa, byLength);
        System.out.println(Arrays.toString(sa));
        System.out.println(byLength.count);
    }
}

Console:

[One, Two, Three, Four, Five]
[One, Two, Four, Five, Three]
2

Regarding to swap: Java passed argument by value, so methods swap(int a, int b) and swap(Object a, Object b) don't work as expected.

If you propose these interfaces, at least add some comments to what they should do. From the discussion I got that you want something like this:

/**
 * A Sortable represents a indexed collection of comparable
 * elements.
 * It does not offer direct access to its elements, only
 * comparison and swapping by indices.
 *
 * In the method specifications we are using this[i] to
 * mean the 
 */
public interface Sortable {

    /**
     * Compares two elements by their indices.
     * @return -1 if this[first] < this[second],
     *          0 if this[first] = this[second]
     *          1 if this[first] > this[second]
     * @throws IndexOutOfBoundsException if one
     *      or both indices are outside of the
     *      limits of this sequence.
     */
    public int compare(int first, int second);

    /**
     * Swaps two elements by their indices.
     * This is roughly equivalent to this sequence:
     * <pre>
     *   temp = this[first];
     *   this[first] = this[second];
     *   this[second] = temp;
     * </pre>
     */
    public void swap(int first, int second);

}

interface Sorter {
   /**
    * sorts an interval of a sequence.
    * @param sequence the sequence to be sorted.
    * @param off the start of the interval to be sorted.
    * @param the length of the interval to be sorted.
    */
   public void sort(Sortable sequence, int off, int len);
}

And then you could have your sort algorithm implement Sorter, while your data structure implements Sortable. Of course one could split the both functions of Sortable in an IndexComparator and IndexSwapper (not Int... like you named them), but they are both directly coupled to your data structure (consisting of your two arrays).