3
\$\begingroup\$

So, I coded a program which asks you the number of integers and the integers the user wants to sort in descending order. The program works but I feel like it is very inefficient. If I were to receive high amount of numbers the program would have to do so much processing. Therefore, how can I improve my code in simple ways? (Open to any criticism)

import java.util.Scanner;


public class Main {
private static Scanner scanner = new Scanner(System.in);
private static Scanner scanner2 = new Scanner(System.in);

public static void main(String[] args) {
    System.out.println("How many integers do you want to sort?");
    int[] IntArray = getIntegers(scanner.nextInt());
    IntArray = sortIntegers(IntArray);
    printIntegers(IntArray);

}

public static int[] getIntegers(int number) {
    System.out.println("Enter " + number + " integers.");
    int[] values = new int[number];

    for (int i = 0; i < values.length; i++) {
        values[i] = scanner2.nextInt();
    }
    return values;
}

public static int[] sortIntegers(int[] array){
    int[] unsortedArray = new int[array.length];
    for(int i = 0; i < unsortedArray.length; i++){
        unsortedArray[i] = array[i];
    }

    for(int n = 0; n < unsortedArray.length - 1; n++) {
        for (int j = 0; j < unsortedArray.length - 1; j++) {
            if (unsortedArray[j] < unsortedArray[j + 1]) {
                int k = unsortedArray[j];
                unsortedArray[j] = unsortedArray[j + 1];
                unsortedArray[j + 1] = k;
            }
        }
    }
    return unsortedArray;
}

public static void printIntegers(int[] array){
    for(int i = 0; i < array.length; i++){
        System.out.println(array[i]);
    }
}
}
\$\endgroup\$

3 Answers 3

3
\$\begingroup\$

Arrays.copyOf

Ignoring the question of whether this is the best approach for this particular problem,

public static int[] sortIntegers(int[] array){
    int[] unsortedArray = new int[array.length];
    for(int i = 0; i < unsortedArray.length; i++){
        unsortedArray[i] = array[i];
    }

Consider instead

public static int[] sortIntegers(int[] unsorted) {
    int[] numbers = Arrays.copyOf(unsorted, unsorted.length);

Using the built-in means that the compiler can take advantage of any optimizations that it might have.

The unsortedArray will be sorted by the end of the method. If we switch the name to the input, that will be unsorted the entire time.

I prefer the name numbers to array for an array of a Number type.

Efficiency

    for(int n = 0; n < unsortedArray.length - 1; n++) {
        for (int j = 0; j < unsortedArray.length - 1; j++) {
            if (unsortedArray[j] < unsortedArray[j + 1]) {
                int k = unsortedArray[j];
                unsortedArray[j] = unsortedArray[j + 1];
                unsortedArray[j + 1] = k;
            }
        }
    }

This compares each element of the array to every other element of the array. But you don't have to do that. Consider

    for (int n = numbers.length - 1; n > 0; n--) {
        for (int i = 0; i < n; i++) {
            if (numbers[i] < numbers[i + 1]) {
                int temp = numbers[i];
                numbers[i] = numbers[i + 1];
                numbers[i + 1] = temp;
            }
        }
    }

Each pass finds the smallest element and puts it in the nth spot. The original code did the same thing, but it would keep checking even though all the ones higher than n were already sorted. This stops comparing once it knows that the spot has the correct value. So we do one fewer comparison each iteration.

Rethinking

You can of course replace all this with Arrays.sort. Then you don't have to worry about the sorting logic and will be using a reasonably efficient version.

If you know that the values are unique (no duplicates in the list), you could also use a data type like SortedSet. Then it will maintain sorted order for you. You could just read the data directly into the SortedSet.

\$\endgroup\$
5
\$\begingroup\$

Extending on @yuri's answer, if you don't have any information relative to the state of "sortedness" of the numbers, quicksort is almost certainly a better option. If you happen to know that the numbers are almost sorted, it would be more efficient to use insertion sort at that point. Writing a sorting algorithm as an exercise is fine, but you're likely going to want to prefer to use Collections.sort than write your own unless you have a specific reason not to.

A few other tips:

  • IntArray is not a typical variable name in Java. Variable names should start lowercase.
  • There's really no reason to use two Scanner instances. You can use the same instance to read the initial array amount as well as each value.
  • While we're at it, there's no reason to specify the number count. The program would be more robust if you simply used a List (ArrayList implementation would work best here) and added values until you receive a non-number input like "end".
  • Generally static class members should really only exist to define constants in your class, and not hold state. Everything in your program is static, so you don't require state except for the Scanner instance. Normally you'd simply pass Scanner instance as a parameter to the static method, but you're only using it in the one method getIntegers so you could just instantiate Scanner only in the scope of getIntegers rather than use it as a parameter or class member.
  • There is already a simple means to print out contents of a List: List.toString.
  • In the off chance that an exception is thrown by Scanner (or any stream), we surround the reading with a try.. finally to ensure that no matter what, the scanner instance is closed properly.
  • Note that I maintained use of List rather than convert to an array. This is mostly because ultimately an array is only required to print out. We can accomplish everything we need using List, and most professional programmers tend to prefer the use of List over arrays except for specific circumstances.

Applying the changes above, we get the following:

public class Main {
    public static void main(String[] args) {
        List<Integer> intList = getIntegers();
        intList = sortIntegers(intList);

        printIntegers(intList);
    }

    public static List<Integer> getIntegers() {
        System.out.println("Please provide integers and 'done' when finished.");

        List<Integer> values = new ArrayList<Integer>();
        Scanner scanner = new Scanner(System.in);
        try {
            while(scanner.hasNextInt()) {
                values.add(scanner.nextInt());
            }
        } finally {
            scanner.close();
        }

        return values;
    }

    public static List<Integer> sortIntegers(List<Integer> list) {
        Collections.sort(list, Collections.reverseOrder());
        return list;
    }

    public static void printIntegers(List<Integer> list) {
        System.out.println(list.toString());
    }
}
\$\endgroup\$
0
1
\$\begingroup\$

Your current search method looks like Bubble sort. Java provides sorting algorithms, which, for primitive types I believe, use Quicksort. As @Imus points out in the comments it's actually Timsort

If you haven't yet you might want to familiarize yourself with the Big O notation as well as it helps to reason about algorithm efficiency.

There are other things in your program that look like they can be improved (e.g. copying an array). However I feel there are people who know modern Java better than me and can provide a better solution to those problems in specific.

\$\endgroup\$
3
  • \$\begingroup\$ Will check them out. About the array copying part, I just remembered there was Array library that helped doing it. Thanks. \$\endgroup\$
    – Huzo
    Jun 5, 2017 at 9:35
  • 1
    \$\begingroup\$ @yuri Actually java uses Timsort which is basically a combination of insertion sort and merge sort. (at least since java 7). Because in practice this performs better given most arrays are already partially sorted from the start. \$\endgroup\$
    – Imus
    Jun 7, 2017 at 7:10
  • \$\begingroup\$ @Imus Thanks for pointing this out! It's been a while since I last used Java so I am not really up to speed. \$\endgroup\$
    – yuri
    Jun 7, 2017 at 8:39

Your Answer

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

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