user2383438
user2383438

Reputation: 11

How to correct insertion sort?

This is my first insertion array, but it does not sort probably and I'm not sure where I went wrong. Any ideas?

  for (int i=1; i<array.length; i++) {
            int temp = array[i];
            for (int j=i-1; j >=0 && temp < array[j]; j--) {
                array[j+1] = array[j];
                array[j+1] = temp;
            }
            ItsATextArea.append(array[i] + "\n");
        }

Upvotes: 0

Views: 93

Answers (3)

ultddave
ultddave

Reputation: 198

You almost had it right. The 'array[j + 1] = temp;' line should be outside the loop.

        for (int i=1; i<array.length; i++) {
            int temp = array[i];
            int j = i - 1;
            for (; j >=0 && temp < array[j]; j--) {
                array[j+1] = array[j];
            }                   
            array[j+1] = temp;
        } 

Also if you're planning on printing the sorted array, do it after algorithm is finished. Because you can't really know if the inserted element "temp" is on the right position yet at the place you added the "append"-line. For example if the last element in the original array is the smallest one, all elements will need to be shifted a place to the right.

Upvotes: 1

amicngh
amicngh

Reputation: 7899

I think you are making mistake here

array[j+1] = array[j];
array[j+1] = temp;  // It must be array[j] = temp

Upvotes: 1

Bathsheba
Bathsheba

Reputation: 234885

array[j+1] = array[j];
array[j+1] = temp;

looks buggy to me. Are you sure you want to use the same element in array twice?

Upvotes: 0

Related Questions