Return to Answer

added 1959 characters in body

Source Link

edited Mar 24, 2016 at 17:09

3.3k
1
22
40

Additionally, your sort function should only sort, not print.

Here's the final result

private static void insertionSort(int[] toSort) {
    for (int i = 1; i < toSort.length; i++) {
        // set key to value at index i
        int key = toSort[i];
        // set j as i-1 to look for previous element
        int j = i - 1;
        while (j >= 0 && toSort[j] > key) {
            toSort[j + 1] = toSort[j];
            j--;
        }
    
        toSort[j + 1] = key;
    }
}

Going further

Insertion sort is a nice sorting algorithm that works for much more than just ints; you can sort doubles, BigIntegers, or even user-defined objects. Why not generify the function? You could do the following:

private static <T extends Comparable<T>> void insertionSort(T[] toSort) {
    for (int i = 1; i < toSort.length; i++) {
        // set key to value at index i
        T key = toSort[i];
        // set j as i-1 to look for previous element
        int j = i - 1;
        while (j >= 0 && toSort[j].compareTo(key) > 0) {
            toSort[j + 1] = toSort[j];
            j--;
        }
    
        toSort[j + 1] = key;
    }
}

private static <T> void insertionSort(T[] toSort, Comparator<T> compare) {
    for (int i = 1; i < toSort.length; i++) {
        // set key to value at index i
        T key = toSort[i];
        // set j as i-1 to look for previous element
        int j = i - 1;
        while (j >= 0 && compare.compare(toSort[j], key) > 0) {
            toSort[j + 1] = toSort[j];
            j--;
        }
    
        toSort[j + 1] = key;
    }
}

This should allow you to sort arbitrarily typed arrays, except for the primitive types, unfortunately (although I did not compile the code).

Additionally, your sort function should only sort, not print.

Here's the final result

private static void insertionSort(int[] toSort) {
    for (int i = 1; i < toSort.length; i++) {
        // set key to value at index i
        int key = toSort[i];
        // set j as i-1 to look for previous element
        int j = i - 1;
        while (j >= 0 && toSort[j] > key) {
            toSort[j + 1] = toSort[j];
            j--;
        }
    
        toSort[j + 1] = key;
    }
}

Going further

private static <T extends Comparable<T>> void insertionSort(T[] toSort) {
    for (int i = 1; i < toSort.length; i++) {
        // set key to value at index i
        T key = toSort[i];
        // set j as i-1 to look for previous element
        int j = i - 1;
        while (j >= 0 && toSort[j].compareTo(key) > 0) {
            toSort[j + 1] = toSort[j];
            j--;
        }
    
        toSort[j + 1] = key;
    }
}

private static <T> void insertionSort(T[] toSort, Comparator<T> compare) {
    for (int i = 1; i < toSort.length; i++) {
        // set key to value at index i
        T key = toSort[i];
        // set j as i-1 to look for previous element
        int j = i - 1;
        while (j >= 0 && compare.compare(toSort[j], key) > 0) {
            toSort[j + 1] = toSort[j];
            j--;
        }
    
        toSort[j + 1] = key;
    }
}

This should allow you to sort arbitrarily typed arrays, except for the primitive types, unfortunately (although I did not compile the code).

Source Link

answered Mar 24, 2016 at 17:02

Justin

3.3k
1
22
40

Your code is pretty good. The biggest problem is consistent indentation. Everything inside of your class should be indented one level; this includes the main method and your insertionsort method.

private static int[] insertionsort(int[] a) {

    for (int i = 1; i < a.length; i++) {
        // set key to value at index i
        int key = a[i];
        // set j as i-1 to look for previous element
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }

        a[j + 1] = key;
        for (int f = 0; f < a.length; f++) {
            System.out.print(a[f] + " ");
        }
        System.out.println();
    }

    return a;
  }

Indented better:

private static int[] insertionsort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        // set key to value at index i
        int key = a[i];
        // set j as i-1 to look for previous element
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
    
        a[j + 1] = key;
        for (int f = 0; f < a.length; f++) {
            System.out.print(a[f] + " ");
        }
        System.out.println();
    }

    return a;
}

Good job on making the insertionsort function static. However, Java's naming convention is camelCase: insertionSort. I could have misread it as insert ions ort and gotten confused.

private static int[] insertionsort(int[] a) {

The fact that you are returning an int[] makes it appear as if you don't modify the input array a (which would be better named toSort); however, you modify a and then return it. I strongly recommend either doing one or the other. If you don't want to modify the input, then you could do it as follows:

private static int[] insertionSort(int[] toSort) {
    int[] a = Arrays.copyOf(toSort, toSort.length); // needs to import java.util.Arrays

If you do want to modify the input, I would declare the method it as follows:

private static void insertionSort(int[] a) {