Inserting into array in order

Question

In simple terms, part of the project I'm working on has me taking an array that is descending in order and adding an element so that it the array remains in order. Initially I thought it would be simple just to add the element into the array and then sort after implementing Comparable, but then found out that sorting algorithms of any kind are prohibited; Collections as well. Kind of out of ideas on how to proceed from here, any hints?

EX:

int[] x = [ 7, 6, 6, 5, 3, 2, 1 ] 

add 4

[ 7, 6, 6, 5, 4, 3, 2, 1 ]

Clarification to say that I am not completely out of ideas, just efficient ones. What I am able to reason so far:

int[] bigger = new int[x.length];
int add = 4;
for (int i = 0; i < bigger.length; i++){
     if ( add > x[i] && add < x[i+1]){
         bigger[i] = x[i];
         bigger[i+1] = add;
     else{
         bigger[i] = x[i];
     }
}

I know it will throw an IndexOutOfBounds error for x, but I feel there must be a simpler method than this, right?

Yes. Here's a hint, int[] newArray = new int[oldArray.length+1]; and I suggest you look at merge from mergeSort. — Elliott Frisch
– Elliott Frisch, Commented Dec 3, 2013 at 2:40
This is painfully simple. Scan the pre-sorted array until you find an element that's less than the one you want to insert. Insert your new element at that location, sliding the found element and everything to the "right" of it farther right. If you fail to find an element less than the one you want to insert, add your new element at the end. If you use the copy-as-you-go approach above, fall out of the search loop when you find the insert point, and fall into a loop to finish the copy. — Hot Licks
– Hot Licks, Commented Dec 3, 2013 at 3:09

Sureshkumar Panneerselvan · Accepted Answer · 2013-12-03 02:48:49Z

2

Once you find the right place i.e. if(value < list[i]){ is true then move all available elements to right. You are moving only one by using list[i+1]= list[i];

   list[numElements] = value;
    for(int i = 0; i < numElements; i++){
        //May be I should use a nested loop?
        //for(k = 0; k <)
         if(value < list[i]){
             for(int j= numElements-1; j>=i; j--){
                  list[j+1]= list[j];
              }
              list[i] = value;
              break;
        }
    }
    numElements++;

answered Dec 3, 2013 at 2:48

Sureshkumar Panneerselvan

5906 silver badges23 bronze badges

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

2 Comments

Hot Licks Over a year ago

If list is [5 4 2] and value is 3, won't you stop on the first iteration?

Hot Licks Over a year ago

And this assumes that you've already copied the array to the new larger one, as a separate step.

Mengjun · Accepted Answer · 2013-12-03 03:26:57Z

Actually, only one for-loop can implement your function.

    int[] x = {7, 6, 6, 5, 3, 2, 1 };
    //Declare an int array with length = x.length+1;
    int[] bigger = new int[x.length+1];
    int add = 4;
    /** Define a variable to indicate that if a property location is found.*/
    boolean found = false;
    /** Define a variable to store an index for insert*/
    int indexToInsert = 0;
    for (int i = 0; i < x.length; i++){
         if ( !found && add >= x[i]){
             found = true;
             indexToInsert = i;
             bigger[indexToInsert] = add;
             i--;
         }
         else{
             if(found)
             {
                 bigger[i+1] = x[i]; 
             }else
             {
                 bigger[i] = x[i];
             }

         }
    }

    /*
     * If a property index is not found. Then put the value at last. 
     */
    if(!found)
    {
        indexToInsert = x.length;//
        bigger[indexToInsert] = add;
    }

Some example is run as follows:

Initail array is [7, 6, 6, 5, 3, 2, 1]

add = 4

 [7, 6, 6, 5, 4, 3, 2, 1]

add = -1

 [7, 6, 6, 5, 3, 2, 1, -1]

add = 100

 [100, 7, 6, 6, 5, 3, 2, 1]

Hot Licks · Accepted Answer · 2013-12-03 03:20:59Z

1

int add = 4;

int[] newArray = new int[oldArray.length + 1];

int oldPos = 0;
int newPos = 1;
while (oldPos < oldArray.length) {
    if (add > oldArray[oldPos]) {
        break;
    }
    newArray[newPos] = oldArray[oldPos];
    oldPos++;
    newPos++;
}

newArray[newPos] = add;
newPos++;

while (oldPos < oldArray.length) {
    newArray[newPos] = oldArray[oldPos];
    oldPos++;
    newPos++;
}

Or one could use System.arraycopy to finish out the copy operation -- slower for a small array but faster for a large one.

answered Dec 3, 2013 at 3:20

Hot Licks

47.8k19 gold badges96 silver badges156 bronze badges

Collectives™ on Stack Overflow

Inserting into array in order

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related