java insertion sort recursive

Question

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);

        }
    }

"i have a string of arrays" -- you mean "an array of strings", right? — Ted Hopp
– Ted Hopp, Commented Sep 28, 2011 at 16:02

Andrzej Doyle · Accepted Answer · 2011-09-28 16:06:48Z

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.
}

Cratylus · Accepted Answer · 2011-09-28 19:10:31Z

0

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!!!!

edited Sep 28, 2011 at 19:10

answered Sep 28, 2011 at 16:09

Cratylus

54.3k73 gold badges222 silver badges349 bronze badges

2 Comments

alexthefourth Over a year ago

ran into an array out of bounds exception at a[i+1] = key

Cratylus Over a year ago

It should be a[j+1]=key.Also delete the recursion. I.e. delete insertionSort(n-1);

Ted Hopp · Accepted Answer · 2011-09-28 16:13:49Z

0

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.

edited Sep 28, 2011 at 16:13

answered Sep 28, 2011 at 16:04

Ted Hopp

235k49 gold badges413 silver badges533 bronze badges

Collectives™ on Stack Overflow

java insertion sort recursive

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related