CODEWITHSUNDEEP
javaarraysrecursioninsertion
alexthefourth
alexthefourth

Reputation: 137

java insertion sort recursive

i have an array and have to sort them using insertion sort. i tried to use the compareTo method to run through the array and see whats bigger. I ran into a problem because i was trying to reference an array index with a string which obviously didntwork (thats at compareTo(a[key])).

any suggestions or hints as to how to do this would be appreciated.

this is what i have so far. is it a good start? or a start in the right direction?

 public void insertionSort() 
    { 
        insertionSort(a.length-1);
    } 



    private void insertionSort(int n)
    {
        String temp; 
        if(n <= 1)
        {
        //Do nothing, easiest case
        }

        else
        {
        for(int i = 1; i < a.length; i++)
        {
        int j;
        String key = a[i];

            while((j >= 0) && (a[i].compareTo(a[key]) > 0))
            {
            a[i+1] = a[i];
            j--;
            }
            a[i+1] = key;
        }   

        insertionSort(n-1);

        }
    }

Upvotes: 0

Views: 3501

Answers (3)

Cratylus
Cratylus

Reputation: 54094

Replace the inner loop as follows:

j = i - 1;  //initialize j!!!
String key = a[i];   //take value
while((j >= 0) && (a[j].compareTo(key) > 0)){//Compare with key!!!
     a[j+1] = a[j];
     j--;
}
a[j + 1] = key; //index is j here!!!!

Upvotes: 0

Ted Hopp
Ted Hopp

Reputation: 234847

Just change it to a[j].compareTo(key) (note that you want to compare a[j], not a[i]). You also need to initialize j, as smas commented.

Upvotes: 0

Andrzej Doyle
Andrzej Doyle

Reputation: 103817

My first suggestion would be that it's usually easier to understand a method if you pass in the required arguments. It's not clear at all what a is; I'd expect the public insertionSort method to take as an argument the objects to sort. (I suppose if you're defining this on your own list-like class it's not as bad, but it doesn't sound like that's the usage).

Likewise I'm not entirely sure what n is supposed to be (presumably the index beyond which you know is sorted) but you don't use it at all in the body of the private method, so you're just doing the same thing n times.

You also appear to be swapping elements of a, which you shouldn't need to do in an insertion sort. This looks more like a bubble sort.

Try writing the method as pseudocode (e.g. comments) first to lay out your approach, then flesh out each comment with a small bit of code. Doing this can avoid getting too bogged down in the detail, and usually conceptual mistakes will appear more obvious, and be easier to avoid. This might look something like:

public static int[] insertionSort(int[] input) {
    // Create the array to hold the results

    // Iterate through the contents of input and insert each one into
    // the result array in order (method call here)

    // return the result array
}

private void insertOneElement(int toInsert, int[] resultArray) {
    // Compare toInsert with first element of resultArray

    // etc.
}

Upvotes: 1

Related Questions