insert into sorted array

Question

I want to insert an element into the right place that order maintains in the sorted list. I allocated 2*n size for the array and filled the rest with 999 since they are not used currently.

ordered_insert(int number,int array[],int size){
 int i=0;
 int temp1,temp2,index;
 while(eleman>array[i]){
   i++;}

//push the rest to right by one
index=i;

if(i<size){
    temp1=array[i];
    temp2= array[i+1];
    array[i+1]=temp1;
    array[i+2]=temp2;
    i++;
    }

array[index]=number;

}

I couldn't figure out how to overwrite 999s or is there a better way instead?

Use loop to shift rest of array (or *memmove* if this is not some school assignment). — hyde, Nov 26 '13 at 16:54
There's a similar question [here](http://stackoverflow.com/questions/11245112/how-to-find-the-insertion-point-in-an-array-bsearch-works-on) but I don't find any of the answers there very satisfying. Google [binary search insert position](http://www.google.com/search?q=binary+search+insert+position) to find better results, including http://rosettacode.org/wiki/Binary_search — , Nov 26 '13 at 17:00
Depending on your usage (e.g. *many* inserts), this kind of operation would be better suited to a linked list instead of an array. — crashmstr, Nov 26 '13 at 17:55

ensc · Answer 1 · 2013-11-26T16:57:55.500

2

you can

memmove(&array[i+1], &array[i], (size - i) * sizeof array[i]);

EDIT:

The 999 trick is not needed; just record the number of used elements in size (and add appropriate boundary checks).

edited Nov 26 '13 at 16:57

answered Nov 26 '13 at 16:46

ensc

6,704
14
22

score 2 · Answer 2 · answered Nov 26 '13 at 16:54

In order to move all the latter array elements one step ahead, you will have to traverse the array backwards so that you do not over-write the elements.

Once you get the index,

int i = size;
while ( i > index ) {
  array[i] = array[i-1];
  i--;
}
array[i] = number;
size++;

score 2 · Answer 3 · answered Jul 09 '15 at 11:56

// 1. initialise i (the 'hole' index) to the last element in the array
// 2. if the preceeding array element is larger than the newValue
// 3.   move the preceeding element into the 'hole' at i, moving the hole up a position
// 4.   reverse through the array
// 5. else put the newValue into the hole and we're done 

i = ARRAY_SIZE-1;  
while (i>0 && array[i-1]>newValue) {
  array[i] = array[i-1];
  i--;
}
array[i] = newValue;

score 1 · Answer 4 · edited May 26 '21 at 10:54

1

To push the rest of the array element's you should use a loop. Just be careful: you should start pushing from the last element otherwise you will assign the rest of elements with the same value.

int i=size-1; // Not i=size (this is the size of the array not the last index)
while (i>index){
array[i] = array[i-1];
i--;
}
array[i] = number;

about assigning the unused elements with 999 it's not required just define a key to remember the last element and use it instead of size, then when inserting a new element just check if you reached the size of the array.

edited May 26 '21 at 10:54

miku

181,842
47
306
310

answered Nov 26 '13 at 17:11

rullof

7,124
6
27
36

You should start from i = size because you are adding one element. Otherwise you are over-writing the last element. – Abhishek Bansal Nov 26 '13 at 17:15
If using a key you should start from the last used index+1 but if using the size it means the number of bytes not the last index of the array so you should subtract 1 to get the last index otherwise you will exceed the size of the array. – rullof Nov 26 '13 at 17:22

score 0 · Answer 5 · answered Jan 15 '21 at 07:28

Try this:-

#include<stdio.h>

void insert(int a[], int size, int element)
{size++;
  int flag=0;
  for(int i=0;i<size;i++)
  { 
    if(a[i]>element)
    {flag++;
      for(int j=size; j>=i; j--)
    a[j] = a[j-1];
      a[i] = element;
      break;
    }
  }
  if (flag == 0)
    a[size-1] = element;
  for(int i=0;i<size;i++)
    printf(" %d", a[i]);
}

int main() 
{
  printf("Insertion of elements in array \n");
  int arr[100], size, element;
  printf("Enter the size of array:- ");
  scanf("%d",&size);
  printf("\nEnter the array(Sorted Array!):- ");
  for(int i=0;i<size;i++)
  {
    scanf("%d",&arr[i]);
  }
  printf("\nEnter element you want to insert:- ");
  scanf("%d", &element);

  insert(arr, size, element);
  
    return 0; 
}

Hi, Welcome to SO. Could you please provide a bit of context for why and how this answer works? That way people with a similar question can use this answer as well. Thanks for answering! — creyD, Jan 15 '21 at 07:50

insert into sorted array

5 Answers5

Linked