1
\$\begingroup\$

I have written a little number sorting algorithm that puts a random array of integers into ascending order, my code is below and it is working fine. However there is the very ugly and unsatisfying break at lines 42 to 44. I would love some advice on how to get rid of that. I had to put this break in there to prevent overflow errors when the index goes into negative numbers. I am sure I can avoid this by looking at the algorithm from another angle but at the moment I just cant see it.

package algorithms;

import java.util.Arrays;

/**
 * This class will place any list of numbers in numerical order
 * @author Richard
 *
 */
public class SortNumbers {

/**
 * This method will take a random set of numbers and
 * place them in numerical order
 * @param args
 */
public static void main(String[] args) {
    //create array
    int[] numbers = new int[]{9,8,7,6,5,4,3,2,1,10,11,15,14};

    //find length of array to control loop
    int length = numbers.length-1; 

    //do not exceed length of array in loop
    for (int outer = 0; outer<length; outer++){

        //reset second counter
        int inner = 0;

        //keep looping while two consecutive numbers are not in order
        while (numbers[outer+inner]>numbers[outer+inner+1]) {

            //swap numbers that are not in order
            int temp = numbers[outer+inner];
            numbers[outer+inner] = numbers[outer+inner+1];
            numbers[outer+inner+1] = temp;

            //decrement and see if numbers need swapped again
            inner--;

            //break on negative index to prevent overflow error
            if (outer+inner<0) {
                break;
            }
        }   
    }
    //convert finished array to string and print
    System.out.println(Arrays.toString(numbers));

}

}
\$\endgroup\$
1
  • \$\begingroup\$ If this was Code Review, I might answer. An alternative to a two-part termination condition as shown by mdfst13 in his answer is planting a sentinel: find the first minimum, shift up elements before by one place, put minimum at index 0 and don't bother with "running off the low end of the array" ever after. \$\endgroup\$
    – greybeard
    Oct 22, 2017 at 2:23

1 Answer 1

2
\$\begingroup\$
    //find length of array to control loop
    int length = numbers.length-1; 

    //do not exceed length of array in loop
    for (int outer = 0; outer<length; outer++){

        //reset second counter
        int inner = 0;

        //keep looping while two consecutive numbers are not in order
        while (numbers[outer+inner]>numbers[outer+inner+1]) {

            //swap numbers that are not in order
            int temp = numbers[outer+inner];
            numbers[outer+inner] = numbers[outer+inner+1];
            numbers[outer+inner+1] = temp;

            //decrement and see if numbers need swapped again
            inner--;

            //break on negative index to prevent overflow error
            if (outer+inner<0) {
                break;
            }
        }
    }

Consider

    for (int i = 1; i < numbers.length; i++) {
        // insert the ith element in its correct position among the elements up to i
        for (int j = i; j > 0 && numbers[j - 1] > numbers[j]; j--) {
            int temp = numbers[j - 1];
            numbers[j - 1] = numbers[j];
            numbers[j] = temp;
        }
    }

Rather than calculate inner + outer, we just track one value, which we call j. Because we set it to the value of i, it will have the same values as inner + outer had in the original.

By moving the check for negative values into the loop control, we don't have to break. We do end up doing an extra check because of that.

I prefer more horizontal whitespace to break up each line into more easily readable pieces.

I reduced the comments down to just one, which I believe is the only line that actually requires thinking to read. I tried to explain the goal of that section of code rather than simply restate what the code does.

Incidentally, this algorithm is called an insertion sort. It's one of the \$\mathcal{O}(n^2)\$ sorts. The built-in sort that Java uses is capable of \$\mathcal{O}(n\log n)\$ complexity. You would normally only use an insertion sort for small input sizes. For any decent sized input, a loglinear sort like quicksort or mergesort would be faster. Of course, you may be on purpose, for learning purposes. When you do that, including the tag can better focus feedback.

\$\endgroup\$

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.