How can I get N smallest number in an array?

Question

I'm trying to get the N smallest numbers (given by the user) in an array without using methods like sort()... in the last step, I keep getting only the smallest values and 0 for the rest.. where's the problem?

        //1- Scanner to take inputs
        Scanner input = new Scanner(System.in);

        //2- Take the array size as input and store it in "sizeOfArr" var
        System.out.print("Enter the array size: ");
        int sizeOfArr = input.nextInt();

        //3- Assign the input as an array size
        int array[] = new int[sizeOfArr];

        //4- Looping on the array and update its values by inputs taken from the user
        for(int i = 0; i < array.length; i++) {
            System.out.print("Enter "+ (i+1) + "-st element: ");
            array[i] = input.nextInt();
        }

        //5- Print out the array after convert it to String
        System.out.println(Arrays.toString(array));

        //6- Find the smallest element in the array and print it
        int minVal = array[0];
        for(int i = 0; i < array.length; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
            }
        }
//        System.out.println(minVal);

        //7- Find the (n) smallest of number defined by the user
        System.out.print("Enter the number of smallest numbers do you want: ");
        int n = input.nextInt();

        //8- new array to store n smallest numbers
        int smallestNums[] = new int[n];

        //9- trying to loop on the original array n times
        int counter;
        for(int i = 0; i < n ; i++) {

            //10- trying to loop on the original array to store the smallest values in smallestNum[] array.
            for(int j = 0; j < array.length; j++) {
                smallestNums[i] = minVal;
            }

            if(smallestNums[i] == smallestNums[i]) {
                break;
            }

        }

        System.out.println(Arrays.toString(smallestNums));

Answer 1

Here is one way. Just do a partial sort with the outer loop limit equal to the number of items required. This is variant of the selection sort. This example, varies n in the outer list for demo purposes.

int[] array = { 10, 1, 5, 8, 7, 6, 3 };
for (int n = 1; n <= array.length; n++) {
    int[] smallest = getNSmallest(n, array);
    System.out.printf("smallest %2d = %s%n", n,
            Arrays.toString(smallest));
}

prints

smallest  1 = [1]
smallest  2 = [1, 3]
smallest  3 = [1, 3, 5]
smallest  4 = [1, 3, 5, 6]
smallest  5 = [1, 3, 5, 6, 7]
smallest  6 = [1, 3, 5, 6, 7, 8]
smallest  7 = [1, 3, 5, 6, 7, 8, 10]

Here is the method. The first thing to do is copy the array so the original is preserved. Then just do the sort and return array of smallest elements.

public static int[] getNSmallest(int n, int[] arr) {
    int[] ar = Arrays.copyOf(arr, arr.length);
    int[] smallest = new int[n];
    for (int i = 0; i < n; i++) {
        for (int k = i + 1; k < ar.length; k++) {
            if (ar[i] > ar[k]) {
                int t = ar[i];
                ar[i] = ar[k];
                ar[k] = t;
            }
        }
        smallest[i] = ar[i];
    }
    return smallest;
}

Answer 2

For this task, you don't have to sort the whole array. Only a group of N elements has to be sorted. I.e. only a partial sorting is required.

Below, I've provided two implementations for this problem. The first utilizes only plane arrays and loops, the second makes use of the PriorytyQueue.

The first solution maintains a variable pos which denotes the position in the result array which isn't assigned yet. Note that the default value for an element of the int[] is 0. It's important to be able to distinguish between the default value and a zero-element from the given array. Hence we can't rely on the values and have to track the number of elements that are assigned.

Every element of the source array gets compared with all the elements of the result array that are already assigned. The new element will be added to the result array in two cases:

• nested loop has reached an unoccupied position pos in the result array;
• an element in the result array that is greater than the next element from the given array has been found.

In the first case, a new element gets assigned the position denoted by pos. In the second case, a new element has to be inserted nested loop iterates over the given array at the current position i and all elements must be shifted to the right. That's what the method shiftElements() does.

The First solution - Arrays & Loops

    public static int[] getSmallest(int[] arr, int limit) {
        int[] result = new int[Math.min(limit, arr.length)];
        int pos = 0;
        for (int next: arr) {
            for (int i = 0; i < Math.min(pos + 1, result.length); i++) {
                if (i == pos) result[i] = next;
                else if (result[i] > next) {
                    shiftElements(result, next, i, Math.min(pos + 1, result.length));
                    break;
                }
            }
            pos++;
        }
        return result;
    }

    private static void shiftElements(int[] arr, int val, int start, int end) {
        int move = arr[start];
        arr[start] = val;
        for (int i = start + 1; i < end; i++) {
            int temp = arr[i];
            arr[i] = move;
            move = temp;
        }
    }

Maybe you'll be more comfortable with the first version, but if you are somehow familiar with the Collections framework, then it's a good time to get acquainted with PriorytyQueue. In the nutshell, this collection is backed by an array and maintains its element in the same order as they were added, but when an element is being deleted collection retrieves the smallest one according to the natural order or based on the Comparator, which can be provided while instantiating the PriorytyQueue. It uses a sorting algorithm that is called a heapsort which allows removing a single element in O(log N) time.

The Second solution - PriorytyQueue

    public static int[] getSmallestWithPriorityQueue(int[] arr, int limit) {
        Queue<Integer> queue = new PriorityQueue<>();
        populateQueue(queue, arr);
        int[] result = new int[Math.min(limit, arr.length)];
        for (int i = 0; i < result.length; i++) {
            result[i] = queue.remove();
        }
        return result;
    }

    private static void populateQueue(Queue<Integer> queue, int[] arr) {
        for (int next: arr) {
            queue.add(next);
        }
    }

main & utility-method to generate an array

    public static void main(String[] args) {
        int[] source = generateArr(100, 10);
        System.out.println("source : " + Arrays.toString(source));

        int[] result1 = getSmallest(source, 3);
        System.out.println("result(Arrays & Loops) : " + Arrays.toString(result1));

        int[] result2 = getSmallestWithPriorityQueue(source, 3);
        System.out.println("result(PriorityQueue)  : " + Arrays.toString(result2));
    }

    public static int[] generateArr(int maxVal, int limit) {
        Random random = new Random();
        return IntStream.generate(() -> random.nextInt(maxVal + 1))
                .limit(limit)
                .toArray();
    }

output

source : [61, 67, 78, 53, 74, 51, 50, 83, 59, 21]
result(Arrays & Loops) : [21, 50, 51]
result(PriorityQueue)  : [21, 50, 51]

Answer 3

Randomized select allows to find k-th ranked element in linear time on average. It alters the input order, so practically, it makes sense to just sort and return k-th element of the sorted array. Especially if there are several such calls on the given input array.