CODEWITHSUNDEEP
javaarrayssorting
Arthur
Arthur

Reputation: 3962

Inserting an integer into a sorted array

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.

Upvotes: 4

Views: 5513

Answers (3)

Elliott Frisch
Elliott Frisch

Reputation: 201467

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]

Upvotes: 0

akhil_mittal
akhil_mittal

Reputation: 24167

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]

Upvotes: 0

ch271828n
ch271828n

Reputation: 17617

Change

if(k < s[i]) {

to

if(k < a[i]) {

in line 4.

Upvotes: 4

Related Questions