Java sorting using comparison and swap function

Question

I need a sort function with a custom compare and swap function. I can write it myself, but I wonder if anyone else has done this. Java runtime contains many specialized sorting functions for sorting arrays of primitive types, objects, etc., but none of them accept the swap function as an argument. A Google search also did not find anything useful.

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

Answer 1

Here is what I was looking for. It is based on the java runtime algorithm for sorting integers. With the correct implementation of the Sortable interface, it can sort almost everything.

  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); } } 

}

Answer 2

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

No. If I understand you correctly, this does not lead to any overhead.

Remember that Java does not store arrays or objects directly in variables (or arrays!). It stores links. Even if each element referencing the array is 40 bytes in size, it will be saved as a reference in the array.

So, I suggest you go with the built-in sorting mechanisms. They will not mix a lot of data, only links.

Answer 3

Since sort() for the Object array is stable, you can get useful information inside a custom Comparator . It takes into account swaps when 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

Answer 4

As for swap: Java passed the argument by value, so the methods swap(int a, int b) and swap(Object a, Object b) do not work properly.

Answer 5

If you offer these interfaces, at least add some comments on what they should do. From the discussion, I realized 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 can implement the Sorter sorting algorithm, and your data structure implements Sortable . Of course, you could separate both Sortable functions in IndexComparator and IndexSwapper (not Int ... as you called them), but they are both directly related to your data structure (consisting of your two arrays).