Parallel sort not finding the top numbers

Question

I'm writing a program which is supposed to find the 25 top numbers in a large array using threads. My algorithm seems to work fine, however when comparing the result to an Arrays.sort-ed version of the original array, it seems like my top 25-list misses some of the numbers. I really hate posting this much code in a question, but I'm completely stuck on this, and has been for a couple of hours now. I'd love some help figuring out what's wrong. Here are my classes:

Main.java

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

public class Main {
    public static void main(String[] args) {
        final int NUM_THRS = 4;

        int[] numbers = new int[500];
        Random generator = new Random(500);

        for(int i = 0; i < numbers.length; i++) {
            numbers[i] = Math.abs(generator.nextInt());
        }

        Thread[] thrs = new Thread[NUM_THRS];
        NumberThread[] nthrs = new NumberThread[NUM_THRS];

        long startTime = System.currentTimeMillis();

        for(int i = 0; i < thrs.length; i++) {
            int start = getStart(i, thrs.length, numbers.length);
            int stop = getStop(i, thrs.length, numbers.length);

            nthrs[i] = new NumberThread(numbers, start, stop);
            thrs[i] = new Thread(nthrs[i]);
            thrs[i].start();
        }

        for (int i = 0; i < thrs.length; i++) {
            try {
                thrs[i].join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        int[] top = new int[25];
        int[] indices = new int[NUM_THRS];

        for (int i = 0; i < indices.length; i++) {
            indices[i] = 24;
        }


        for(int i = 0; i < top.length; i++) {
            top[i] = getMax(nthrs, indices);
        }

        for (int i = 0; i < top.length; i++) {
            System.out.println(top[i]);
        }   

    }

    public static int getMax(NumberThread[] thrs, int[] indices) {
        int maxNum = 0;
        int maxIdx = 0;
        for(int i = 0; i < indices.length; i++) {
            if(indices[i] >= 0) {
                if(thrs[i].topNums[indices[i]] > maxNum) {
                    maxNum = thrs[i].topNums[indices[i]];
                    maxIdx = i;
                }
            }
        }
        System.out.println("iterate");
        indices[maxIdx] = indices[maxIdx]-1;
        return maxNum;
    }

    public static int getStart(int i, int total, int len) {
        return i*len/total;
    }

    public static int getStop(int i, int total, int len) {
        if(i != total-1) {
            return (i+1)*len/total;
        }

        return len-1;
    }
}

NumberThread.java

public class NumberThread implements Runnable {

    int start, stop;
    int[] numbers;
    int[] topNums;

    public NumberThread(int[] numbers, int start, int stop) {
        this.numbers = numbers;
        this.start = start;
        this.stop = stop;
        this.topNums = new int[25];

        System.out.println(start + " " + stop);
    }

    @Override
    public void run() {
        for (int i = start; i <= stop; i++) {
            inner: for (int j = topNums.length-1; j > 0; j--) {
                if(numbers[i] > topNums[j]) {
                    topNums[j] = numbers[i];
                    break inner;
                }
            }
        }
    }
}

The numbers printed after main are not the same as the top numbers when I Arrays.sort the numbers-array and print the top 25. Some numbers seem to be missing.

Thanks a lot in advance.

Answer 1

I think that your NumberThread classes Run method isn't doing what it should do. It needs to find the 25 largest numbers in the partition you assign to it, for example if the array you are searching was already sorted then the 25 largest numbers could all be in 1 partition but what its's actually doing is overwriting the first number it finds that's smaller than the current number so you end up with less than 25 numbers and they might not be the largest.

For example consider the sequence 98 99 1 2 3... 98 would get written to topNums[19] but then overwritten with 99.

I'm also not sure about the getMax function, it seems to be trying to merge the different topNums arrays together; however the arrays aren't sorted so I don't see how it can work.