4

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);
}
public static void sort(IntComparator compFn, IntSwap swapFn, int off, int len);
Improve this question
5
  • 1
    What would a custom swap function do, other than swap the elements? Commented Feb 13, 2011 at 11:03
  • A custom swap function can be used to count the number of swaps needed, which is good when you learn programming. The Java standard library is not designed for these things, though. Commented Feb 13, 2011 at 11:08
  • I need to swap indices in two arrays. I know that I could sort twodimensional array but that would increase required memory. Each java object has rather big overhead (about 40 bytes) and I'm trying to avoid it. Commented Feb 13, 2011 at 11:15
  • Don't worry about memory usage unless you absolutely have to. For a problem like this one having the extra memory overhead to tag each object with its initial position should be fine. If on the other hand you're sorting arrays so huge they just barely fit in memory, though, this is a reasonable issue to take into account. Commented Feb 13, 2011 at 11:47
  • Reducing amount of used memory is the point of what I'm trying to do. I'm optimizing part of larger framework that loads data from DB to memory, sorts it and sends it to Jasper Reports. Currently data are stored in rows, each row has array of values. Each row may have several subreports. Subreports consists of array array of rows ... etc. I want to store all data into one (or more) big byte array and several integer arrays that contain indexes where data where row/subreport data starts. This will reduce memory about 100x times and it could also reduce CPU load (data may fit into L2/L3 cache) Commented Feb 13, 2011 at 13:19

5 Answers 5

Reset to default
4

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

}

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

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.

Improve this answer

3 Comments

1. I'm using flyweight pattern to reduce used memory, objects that i'm sorting are created when needed and then disposed. That's why I cannot use functions that sort objects. 2. java sort functions, that sort integers(and other primitive types) cannot use comparators. I'm using arrays of integers as references to byte array that contains the data. 3. each object has two references. That's why I need swap function, when swapping two items I need to update both of them.
In java, 2D arrays consists of 1D arrays and each array is an object. If last dimension of the array is small, it leads to substatial memory overhead. For example int[2][1000] needs (1000*4+40)*2+40=8120 bytes of memory(overhead only 1.5%), int[1000][2] needs (2*4+40)*1000+40 =46040 bytes of memory (huge overhead 475%).
Jack is right - the overheads can be significant. Consider using two large byte arrays, say 10^6 elements each. In memory, that's only 10^6 * 16 bits. However, storing 10^6 arrays, each containing only two bytes, on a 64-bit machine requires a pointer (64-bits) and some data (another 64-bits minimum) per element! That's 128 * 10^6 bits. Overhead is a factor of 8, which can be significant for large data.
0

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
Improve this answer

Comments

0

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.

Improve this answer

2 Comments

Of course they do. Here is simple implementation of swap function. class IntSwapImpl implements IntSwap { private final int[] ba; IntSwapImpl(int[] ba) { this.ba = ba; } @Override public void swap(int a, int b) { int v = ba[a]; ba[a] = ba[b]; ba[b] = v; } }
OK, you pass indexes as arguments rather than real values. My misunderstanding.
0

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).

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.