4

I'm trying to write a method that takes a sorted array and an integer, creates a new array that is 1 size larger, and inserts the new integer and keeps it sorted.

I've tried a few different implementations and had them to work - but for this specific one, I can't grasp where it's going wrong.

    int[] array1 = new int[]{1, 2, 3, 4, 6, 7, 8};
    int[] printArray = insert(array1, 5);

are the arrays, and the method is

public static int[] insert(int[] a, int k) {
    int[] s = new int[a.length + 1];
    for(int i = 0; i < a.length; i++) {
        if(k < s[i]) {
            s[i] = k;
            for(int j = i + 1; j < s.length; j++) {
                s[j] = a[i];
                i++;
            }
            return s;
        } else {
            s[i] = a[i];
        }
    }
    return s;
}

This method prints out 1, 2, 3, 4, 6, 7, 8, 0, instead of 1, 2, 3, 4, 5, 6, 7, 8.

Improve this question
0

3 Answers 3

Reset to default
4

Change

if(k < s[i]) {

to

if(k < a[i]) {

in line 4.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

How did I miss that.... Been staring at too many a's, k's, j's, and i's that they just all look the same. Thanks
@Turtle, Good catch !!
@Turtle I am trying to do it yet again in using 1 for loop, could you take a look at this: imgur.com/mp3oMs8
It is printing 1, 2, 3, 4, 5, 0, 7, 8. The number after the inserted always comes out 0, then finishes the array correctly.
@arthur change 'else{ s[]=...; }' directly into 's[]=...'. Hope you get my meaning.
0

Actually in the following line you are creating an array with all elements zero:

int[] s = new int[a.length + 1];

s[0] to s[7] will be 0.

Your loop counter i runs from 0 to a.length but the point to note is all the elements of array s will be zero. You are comparing k with s[i] which is zero and for that reason the shifting of arrays never happen (if block never executes).

You need to do two things to fix it.

  1. Initialize element zero of s with the value of a[0].
  2. Compare element with previous element to figure out position to insert.

The final code is:

public static int[] insert(int[] a, int k) {
        int[] s = new int[a.length + 1];
        s[0] = a[0];
        for(int i = 1; i < a.length; i++) {
            if(k < s[i-1]) {
                s[i] = k;
                for(int j = i + 1; j < s.length; j++) {
                    s[j] = a[i];
                    i++;
                }
                return s;
            } else {
                s[i] = a[i];
            }
        }
        return s;
    }

Now you will get: [1, 2, 3, 4, 6, 5, 7, 8]

Improve this answer

1 Comment

This is not correct with values int[] arr = {34,49,71,101,120,180}; int[] printArray = insert(arr, 5);
0

I would start by using Arrays.copyOf(int[], int) to create a new array that is one larger than the input. Then iterate that array until I reached the index that the new value belongs at. Then use System.arraycopy(Object,int,Object,int,int) to copy the values into the end of the array. That might look something like

public static int[] insert(int[] a, int k) {
    int[] s = Arrays.copyOf(a, a.length + 1);
    for (int i = 0; i < s.length; i++) {
        if (a[i] < k) {
            continue;
        }
        System.arraycopy(a, i, s, i + 1, s.length - i - 1);
        s[i] = k;
        break;
    }
    return s;
}

Which I tested with Arrays.toString(int[]) like

public static void main(String s[]) throws IOException {
    int[] array1 = new int[] { 1, 2, 3, 4, 6, 7, 8 };
    int[] printArray = insert(array1, 5);
    System.out.println(Arrays.toString(printArray));
}

And I get the (expected)

[1, 2, 3, 4, 5, 6, 7, 8]
Improve this answer

1 Comment

So to add John Smith to a phone book you start on page one and read the phone book up to Joe Smith and then add the new entry :)

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.