Insertion sort Java not properly sorting

Question

I'm trying to program bubble sort, selection sort and insertion sort MYSELF. However, I'm having trouble with insertion sort. I'll provide my code and what each line is doing

public void sortMethod() {
    int count = 1;
    for (int j = 0; j < Unsorted.length - 1; j++) {
        int index = 0;
        if (Unsorted[count] < Unsorted[count - 1]) {
            int temp = Unsorted[count];
            for (int i = count; i > 0; i--) {
                if (Unsorted[i] > Unsorted[count]) {
                    index = i;
                    Unsorted[i] = Unsorted[i - 1];
                }
            }
            Unsorted[index] = Unsorted[count];
        }
        count = count + 1;
    }
}

Okay so int count is to figure out where the sorted array starts from. Then I declared index to find where to put the element after the sorted array and declared a temporary int for the first element of the unsorted array, if it's less than the last element of the sorted array. Then it reverses the array till the first element, and if it's greater than the element I'm adding, to assign index to its index. Essentially so I know where to place it. Then unsorted[I] = unsorted[I - 1] to shift the sorted array from where the first element of the unsorted array belongs. Then assign the first element of the unsorted array, to where it belongs. Increase the count each time

Array: 31 27 45 23 22 3 1 13 1 42 
Array after sort: 27 1 1 3 22 23 1 1 1 42 
BUILD SUCCESSFUL (total time: 0 seconds)

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) — Andreas, Sep 23 '20 at 00:02

CryptoFool · Accepted Answer · 2020-09-23T01:13:23.140

Here's the minimum amount I had to change your code to get it to do an insertion sort as I understood such a sort to work. Notice that you had more integer values you were using than were necessary, and there was an extra if in there you didn't need. I put lots of comments to mirror what I was thinking as I fixed it, so you can hopefully understand what the code is doing:

public class Test
    private static int[] Unsorted = {444, 7, 22, 4, 3, 2, 1, -34, -999};

    public static void sortMethod() {

        // We'll consider each position in the array in order.  For each round,
        // 'j' is pointing at the last item in the part of the array that we know is
        // correctly sorted.  The first item after 'j' is the next candidate.  We
        // want to INSERT it into the right place in the part of the array that
        // is already sorted. NOTE: The first item is never a candidate because
        // an array with one element is always sorted.
        for (int j = 0; j < Unsorted.length - 1; j++) {
            // save off next candidate value, the first value that may be out of order
            int temp = Unsorted[j + 1];

            // Move all the items in the sorted part of the array that are greater
            // than the candidate up one spot.  We know we have room to shift up
            // because we've saved off the value at the candiate position.
            int i = j;
            while (i >= 0 && Unsorted[i] > temp) {
                Unsorted[i + 1] = Unsorted[i];
                i = i - 1;
            }
            // Put the candidate in the hole that is left.  This inserts it such
            // that everything below it has a value smaller than it, and everything
            // above it has a value greater than it.
            Unsorted[i + 1] = temp;

            // Now the array is sorted up to  the position j is pointing to and one
            // beyond, so we'll advance j by one position for the next round
        }
    }

    public static void main(String[] args) {
        sortMethod();
        for (int i = 0 ; i < Unsorted.length ; i++)
            System.out.println(Unsorted[i]);
    }
}

Result:

Insertion sort Java not properly sorting

1 Answers1