47
\$\begingroup\$

Last Friday I was hit with a sorting interview question that I never really had to deal with.

Develop a your own sorting algorithm.

  1. It cannot use any other Classes for help.
  2. It needs to be able to sort an array of millions of integers in size.
  3. It needs to be as fast as possible.

For instance:

int[] old = {5434, 3454, 2, 0, 356, 896, 7324, 888, 99, 78365, 111};  
int highestNumber = 78365;  

Would be

int[] new = {0, 2, 99, 111, 356, 888, 896, 3454, 5434, 7324, 78365};

I spent the night trying to come up with my own method to do this. And this is what I came up with.

public class Main {
    public static void main(String[] args) {
        int[] twentyMillion = new int [20000000];
        for (int i = 0; i < a.length; i++) {
            twentyMillion [i] = new Random().nextInt(20000000);
        }
        sortByAccendPro(twentyMillion , 20000000);
    }

    /**
     * Jasz sort algorithim.
     * 
     * @param {int[]} twentyMillion - array of twenty million random ints.
     * @param {int} highestNumber - Highest number to sort to.
     */
    public void sortByAccendPro(int[] twentyMillion, int highestNumber ) {
        int[] rangePosition = new int[twentyMillion.length];
        int[] newArray = new int[twentyMillion.length];
        int[] range = new int[highestNumber];
        long time = System.nanoTime();
        for (int i = 0; i < twentyMillion.length; i++) {
            rangePosition[i] = twentyMillion[i];
            range[twentyMillion[i]]++;
        }
        for (int i = range.length - 1, past = twentyMillion.length; i >= 0; i--) {
            range[i] = past - range[i];
            past = range[i];
        }
        for (int i = 0; i < twentyMillion.length; i++) {
            newArray[range[rangePosition[i]]] = twentyMillion[i];
            range[rangePosition[i]]++;
        }
        System.out.println("time = " + (System.nanoTime() - time));
    }
}

Steps:

  1. The first loop has the range of numbers. For instance, if the rangeArray goes from 0 to 3,000,000, it increments every case of each number it finds in that array. So every time it finds 2,750,000 it increments that position in the rangeArray.

  2. The second loop works backwards from the max position in the rangeArray. So if the size is 3,000,000 and it has 100,000 cases of 3,000,000 it says that 3,000,000 will start at 2,900,000 and go to the max.

  3. The 3rd loop loops back through the main array grabbing the same index in the range array and plugging the number in the correct position in the newArray.

It handles duplicates and with a little tinkering you can make it sort many other things. It uses more memory than I wanted in order to do sorting but wow its lightening fast. I never thought of looking into how these sorting algorithms work until I did this but can find nothing to compare it to.

What algorithm does this resemble and what can I do to make it better?

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! I have rolled back the last edit. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Heslacher May 18 '15 at 21:38
  • 1
    \$\begingroup\$ All your code becomes unusable if you do not make some daring assumptions: Good luck making an array with a size of Integer.MAX_VALUE+2 with default settings on a normal computer. Why do you all only expect positive values with a convenient upper bound? \$\endgroup\$ – Traubenfuchs May 19 '15 at 12:01
  • 4
    \$\begingroup\$ @Jasz You were asked... in an interview... to develop a new sorting algorithm for integers? And you stayed? \$\endgroup\$ – corsiKa May 19 '15 at 16:50
  • 1
    \$\begingroup\$ @BradWerth He didn't use any classes in the actual sorting algorithm, I don't think they expected him to write his own Random, implementaiton \$\endgroup\$ – Traubenfuchs May 20 '15 at 7:33
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Simon Forsberg May 21 '15 at 12:07
29
\$\begingroup\$

The algorithm you have implemented is known as counting sort. Its run-time cost is linear in the size of the input – faster than any comparison-based sorting algorithm can possibly get. (At the cost of being also linear in the difference of the maximum and minimum element in the input.) Congratulations if you've come up with this idea on your own. Since they already give you the largest number in the array as additional input, it seems very likely that they wanted to see this algorithm. (Of course, you can find the maximum yourself in linear time, if needed.)

Remarks about your code:

  • The rangePosition array is initialized with an exact copy of twentyMillion and then only ever read. Why did you create it instead of using twentyMillion directly?
  • If twentyMillion contains a negative number, your implementation will explode. Maybe you simply forgot to mention that all the inputs are guaranteed to be non-negative? Otherwise, you'd also need to know the minimum value and normalize your keys to that. (This could also help you save something if the minimum is much larger than zero.)
  • If the highestNumber is extremely large, you will get a problem. For example, you will probably not be able to allocate a new int[Integer.MAX_VALUE] without receiving an OutOfMemoryError. (And if you allow for negative numbers in the input, you might even need an array larger than Integer.MAX_VALUE!) And even if you could allocate it, iterating over it will take forever. If you want to make your code more robust, you could decide by some heuristic whether the combination of twentyMillion.length and highestNumber warrants the overhead of counting sort or you'd be better off using a comparison-based O(n log(n)) fallback-algorithm.
  • twentyMillion is a poor name for a variable that does not necessarily name an array of length 20M.
\$\endgroup\$
  • 3
    \$\begingroup\$ Thanks dang I thought I made my own algorithm :( that is exactly how my method works. The max value is a problem. The true question was sorting by mod value but I noticed you could use it in many other ways so I converted it to this. You're right about the rangePosition I don't think its needed either \$\endgroup\$ – Xjasz May 18 '15 at 21:19
24
\$\begingroup\$

It's an interview, and you have been given the opportunity to show off what you know. If I were "assessing" your submission, what would be my impression?

Don't use things badly. Your code here is horrible:

    for (int i = 0; i < a.length; i++) {
        twentyMillion [i] = new Random().nextInt(20000000);
    }

Creating a new Random inside the loop is a poor use of the class. Create a single random Instance, and reuse it:

Random rand = new Random();
for (int i = 0; i < a.length; i++) {
    twentyMillion [i] = rand.nextInt(20000000);
}

Use constants for magic numbers.... 20,000,000 is a constant, and should be declared as such:

private static final int dataSize = 20_000_000;

Note that I use the _ in there to show off the fact that I know it exists as a language feature (since Java 7 at least).

Next, I don't see any Java-8 features in there. For an interview I would expect you to "wow" me... but there's nothing that's exciting technically in your code. For example, an easy-win would be the creation of the input array:

    Random rand = new Random();
    int[] toSort = IntStream.generate(() -> rand.nextInt(dataSize))
                                   .limit(dataSize)
                                   .toArray();

I would likely put that in a method to show some functional extraction too:

private static final int[] generateData(int size) {
    Random rand = new Random();
    return IntStream.generate(() -> rand.nextInt(size))
                    .limit(size)
                    .toArray();
}

Right, that shows some familiarity with Java 8, some language structures, code discipline, and so on.

What about the actual sort algorithm?

As fast as possible

That's a loaded question. The fastest sort is dependent on constraints that are not given in your requirements. A counting sort would be fast for a finite dataset, but has potentially large space requirements. Other sorts are more than fast enough, but have much smaller additional memory requirements.

An interview question asking "as fast as possible" can only be answered accurately with: "what are your other constraints". I would consider this a "trick question".

As an aside, your variable names have already been covered in other answers, but I want to reiterate that they need more work.

\$\endgroup\$
  • 1
    \$\begingroup\$ +1 for the random catch. For the Random class to work properly, you would need to keep the same random seed for all items inside of the loop. Otherwise, you will end up with a ton of non-random numbers. You can try this out on your own by creating a console application with 2 functions. Have one function declare Random inside of the loop and the other outside. Then have the loop run for 1000 iterations and each time printing out the output. It would be obvious which way is the proper way to use Random. \$\endgroup\$ – Jason Hutchinson May 19 '15 at 12:24
  • 2
    \$\begingroup\$ Random actually has a Random::ints(long,int,int) method. So you can use new Random().ints(dataSize, 0, dataSize).toArray(). Is that wow enough? :p \$\endgroup\$ – Olivier Grégoire May 19 '15 at 17:34
  • \$\begingroup\$ @OlivierGrégoire - That is, in fact, wow enough. ;-) \$\endgroup\$ – rolfl May 19 '15 at 17:36
  • \$\begingroup\$ "... to show off the fact that I know it exists ..." - ha ha, snort, nice one :-) \$\endgroup\$ – user7649 May 20 '15 at 5:38
10
\$\begingroup\$

What you did looks like Bucket Sort, however your exact algorithm is a mystery to me. The problem with Bucket Sort is that you may need up to 4Gi buckets when sorting arbitrary integers. This is a bit too much. With 16GiB memory you could pack them into 4 new int[1<<30] arrays, but the algorithm would get pretty slow (due to bad memory locality and much more bookkeeping data than items to sort).

So I guess, I'd resort to Quick Sort for an unlimited range. For a limited range, your algorithm is fine.

 * @param {int} highestNumber - Highest number to sort to.

The method would be more general if it didn't require this argument. It's redundant and you could compute it yourself. This would cost some time, so in extreme cases you may want to provide both versions.

    int[] rangePosition = new int[twentyMillion.length];
    int[] newArray = new int[twentyMillion.length];
    int[] range = new int[highestNumber];
    long time = System.nanoTime();

You're cheating by starting the measurement in the middle of the algorithm. Sure, it's not really the middle, but still.

Despite your explanation, I'm completely lost concerning how it works. Probably not your fault. So I'll present my (untested but trivial) version instead of reviewing:

int[] counts = new int[highestNumber];
for (int x : twentyMillion) {
    ++counts[x];
}
int insertionIndex = 0;
for (int i = 0; i < counts.length; ++i) {
    for (int j = 0; j < counts[i]; ++j) {
        twentyMillion[insertionIndex++] = i;
    }
}
// No return value needed as the input array gets overwritten.

It looks like you fill the newArray just for fun and neither use it nor return. If the JVM was smart and evil enough, it could reduce your whole method to the two nanoTime lines. In simpler cases, similar things indeed happen, so don't let your benchmarks ignore the values to be computed.

\$\endgroup\$
  • \$\begingroup\$ this s rapidest way i was talking about \$\endgroup\$ – Abr001am May 18 '15 at 20:20
  • \$\begingroup\$ @Agawa001 I see! But that's only needed if there's some content you want to preserve (you're sorting shoes according to their size and the size is not the only property). For ints, there's nothing but the value, so simply overwriting the whole array according to counts is good enough. \$\endgroup\$ – maaartinus May 18 '15 at 23:27
  • \$\begingroup\$ He actually uses just counting sort. If it were bucket sort, he'd put more than one value in each bucket. Bucket sort and radix sort are advanced types of counting sort. Also I've heard of 'Tim Sort' which seems quicker than quicksort, even though it is only a hybrid of merge sort and insertion sort. \$\endgroup\$ – klaar Aug 18 '16 at 9:11

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.