6
\$\begingroup\$

I have this implementation of Quicksort for strings. The algorithm sorts the requested range by first character, then by second, third, and so on. (Please, do not confuse this with radix sort; it is not.)

The pseudocode might look like this:

# Public API
Sort(R):
    Sort(R, 0)

Sort(R, len):
    if |R| < 2 return R
    R_p = all strings of length 'len'
    select pivot X from R
    R< = all strings S for which S[len] < X[len]
    R= = all strings S for which S[len] = X[len]
    R> = all strings S for which S[len] > X[len]
    R< = Sort(R<, len)
    R= = Sort(R=, len + 1) # Note 'len + 1'!
    R> = Sort(R>, len)
    return < R_p, R<, R=, R> > # Concatenate sorted sublists 

StringQuicksort.java:

package net.coderodde.util;

import java.util.Arrays;
import java.util.Random;

/**
 * This class implements a Quicksort for strings.
 * 
 * @author Rodion "rodde" Efremov
 * @version (Dec 17, 2015)
 */
public class StringQuicksort {

    private static final int ALPHABET_SIZE = 26;

    public static void sort(String[] array) {
        sort(array, 0, array.length);
    }

    public static void sort(String[] array, int fromIndex, int toIndex) {
        if (toIndex - fromIndex < 2) {
            return;
        }

        sortImpl(array, fromIndex, toIndex, 0);
    }

    private static void sortImpl(String[] array, 
                                 int fromIndex, 
                                 int toIndex, 
                                 int stringLength) {
        int rangeLength = toIndex - fromIndex;

        if (rangeLength < 2) {
            return;
        }

        int finger = fromIndex;

        // Put all strings of length 'stringLength' to the beginning of the 
        // requested sort range.
        for (int index = fromIndex; index < toIndex; ++index) {
            String current = array[index];

            if (current.length() == stringLength) {
                String tmp = array[finger];
                array[finger] = current;
                array[index] = tmp;
                ++finger;
            }
        }

        fromIndex = finger;

        // Choose a pivot string by median.
        String probeLeft = array[fromIndex];
        String probeRight = array[toIndex - 1];
        String probeMiddle = array[fromIndex + rangeLength >> 1];

        String pivot = median(probeLeft, probeMiddle, probeRight);

        // Process strings S for which S[stringLength] < X[stringLength].
        for (int index = fromIndex; index < toIndex; ++index) {
            String current = array[index];

            if (current.charAt(stringLength) < pivot.charAt(stringLength)) {
                String tmp = array[finger];
                array[finger] = current;
                array[index] = tmp;
                ++finger;
            }
        }

        sortImpl(array, fromIndex, finger, stringLength);

        fromIndex = finger;
        int processed = 0;

        for (int index = fromIndex; index < toIndex; ++index) {
            String current = array[index];

            if (current.charAt(stringLength) == pivot.charAt(stringLength)) {
                String tmp = array[finger];
                array[finger] = current;
                array[index] = tmp;
                ++finger;
            }
        }

        sortImpl(array, fromIndex, finger, stringLength + 1);
        sortImpl(array, finger, toIndex, stringLength);
    }

    private static String median(String a, String b, String c) {
        if (a.compareTo(b) <= 0) {
            if (c.compareTo(a) <= 0) {
                return a;
            }

            return b.compareTo(c) <= 0 ? b : c;
        } 

        if (c.compareTo(b) <= 0) {
            return b;
        }

        return a.compareTo(c) <= 0 ? a : c;
    }

    public static void main(final String... args) {
        long seed = System.nanoTime();
        Random random = new Random(seed);
        String[] array1 = createRandomStringArray(400_000, 20, random);
        String[] array2 = array1.clone();

        System.out.println("Seed = " + seed);

        long startTime = System.nanoTime();
        Arrays.sort(array1);
        long endTime = System.nanoTime();

        System.out.format("Arrays.sort in %.2f milliseconds.\n",
                          (endTime - startTime) / 1e6);

        startTime = System.nanoTime();
        StringQuicksort.sort(array2);
        endTime = System.nanoTime();

        System.out.format("StringQuicksort.sort in %.2f milliseconds.\n",
                          (endTime - startTime) / 1e6);

        System.out.println("Arrays equal: " + Arrays.equals(array1, array2));
    }

    private static String[] createRandomStringArray(int size, 
                                                    int maxLength, 
                                                    Random random) {
        String[] ret = new String[size];

        for (int i = 0; i < size; ++i) {
            ret[i] = randomString(maxLength, random);
        }

        return ret;
    }

    private static String randomString(int maxLength, Random random) {
        int length = random.nextInt(maxLength + 1);
        StringBuilder sb = new StringBuilder(length);

        for (int i = 0; i < length; ++i) {
            sb.append((char)('a' + random.nextInt(ALPHABET_SIZE)));
        }

        return sb.toString();
    }
}

Some performance figures:

Seed = 110240813919222
Arrays.sort in 823.63 milliseconds.
StringQuicksort.sort in 441.81 milliseconds.
Arrays equal: true

What can I improve? Performance? Coding style? API? Naming? Any critique much appreciated!

\$\endgroup\$
  • \$\begingroup\$ You might check the tags on your "sort questions", esp. algorithm and strings. (Here, too: what is your goal coding this?) \$\endgroup\$ – greybeard Jan 3 '16 at 10:40
5
\$\begingroup\$

Both public sort() methods should check if array == null otherwise you risk a IndexOutOfBoundsException inside the private sortImpl() method.


Instead of having the comment

    // Put all strings of length 'stringLength' to the beginning of the 
    // requested sort range.  

you should extract this looping to a separate well named method making the comment removeable. While we are at the looping, the 3 loops with swapping have most code in common except for the if condition when to swap. Maybe you can use some Java 8 vodoo like java.util.function.Function<T, R> to pass to that said method a parameter which does the condition check for you.

In this way that duplicated code could be removed.

\$\endgroup\$
2
\$\begingroup\$

The following method call

StringQuicksort.sort(new String[] { "a", "a" });

will result in an ArrayIndexOutOfBoundsException.

\$\endgroup\$
  • \$\begingroup\$ That could be fixed by if ((rangeLength = toIndex - finger) < 2) return; following the "move short Strings to front"-loop, defusing fromIndex + rangeLength >> 1, too. \$\endgroup\$ – greybeard Jan 2 '16 at 22:39
0
\$\begingroup\$

A drop-in alternative implementation of sortImpl,
heeding good advice from Heslacher and mjolka:

static interface Predicate<T> {
    boolean test(T t);
}

/** Moves all strings meeting predicate <code>toFront</code>
 *      to the beginning of the range specified.
 * @return index of first element <em>not</em> meeting <code>toFront</code>,
 *  or <code>toIndex</code> */
static
int toFront(String[] array, int fromIndex, int toIndex,
            Predicate<String> toFront) {
    int finger = fromIndex;
// optional: leave initial elements meeting toFront alone
    while (true) {
        if (toIndex <= finger)
            return toIndex;
        if (!toFront.test(array[finger]))
            break;
        finger++;
    }

    for (int index = finger ; index < toIndex ; ++index) {
        String current = array[index];

        if (toFront.test(current)) {
            String tmp = array[finger];
            array[finger] = current;
            array[index] = tmp;
            finger++;
        }
    }
    return finger;
}

/** Sort <code>String</code>s starting at <code>fromIndex</code>
 *      stopping short of <code>toIndex</code>.
 * @param array        to sort
 * @param fromIndex    lowest index of those to consider 
 * @param toIndex      lowest index of those <em>not</em> to consider
 * @param stringLength lower bound, and the <code>String</code>s
 *      in the specified slice of <code>array</code>
 *      share an identical prefix of this length */
private static void sortImpl(String[] array, 
    int fromIndex, 
    int toIndex, 
    int stringLength) {
    int rangeLength;

    if ((rangeLength = toIndex - fromIndex) < 2)
        return;
    fromIndex = toFront(array, fromIndex, toIndex,
                        s -> s.length() <= stringLength);
    if ((rangeLength = toIndex - fromIndex) < 2)
        return;

    String pivot = pivot(array, fromIndex, rangeLength);

// Process strings S for which S[stringLength] < pivot[stringLength].
    char pivotChar = pivot.charAt(stringLength);
    int finger = toFront(array, fromIndex, toIndex,
                         s -> s.charAt(stringLength) < pivotChar);

    sortImpl(array, fromIndex, finger, stringLength);

    finger = toFront(array, fromIndex = finger, toIndex,
                     s -> s.charAt(stringLength) == pivotChar);

    sortImpl(array, fromIndex, finger, stringLength + 1);
    sortImpl(array, finger, toIndex, stringLength);
}

static String pivot(String[] array, int fromIndex, int rangeLength) {
    return rangeLength < 3 ? array[fromIndex] :
        median/*Of3*/(array[fromIndex],
            array[fromIndex + (rangeLength >> 1)],
            array[fromIndex +  rangeLength - 1]);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.