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
– hyde, Commented Nov 26, 2013 at 16:54
There's a similar question here but I don't find any of the answers there very satisfying. Google binary search insert position to find better results, including rosettacode.org/wiki/Binary_search — user2404501
– user2404501, Commented Nov 26, 2013 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
– crashmstr, Commented Nov 26, 2013 at 17:55

Abhishek Bansal · Accepted Answer · 2013-11-26 16:54:22Z

2

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++;

answered Nov 26, 2013 at 16:54

Abhishek Bansal

12.7k4 gold badges34 silver badges46 bronze badges

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

Comments

ensc · Accepted Answer · 2013-11-26 16:57:55Z

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, 2013 at 16:57

answered Nov 26, 2013 at 16:46

ensc

7,06220 silver badges25 bronze badges

Comments

push2eject · Accepted Answer · 2015-07-09 11:56:56Z

2

// 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;

answered Jul 9, 2015 at 11:56

push2eject

2133 silver badges8 bronze badges

Comments

miku · Accepted Answer · 2021-05-26 10:54:13Z

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, 2021 at 10:54

miku

189k47 gold badges314 silver badges317 bronze badges

answered Nov 26, 2013 at 17:11

rullof

7,5027 gold badges29 silver badges37 bronze badges

2 Comments

Abhishek Bansal Over a year ago

You should start from i = size because you are adding one element. Otherwise you are over-writing the last element.

rullof Over a year ago

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.

Rishi Sharma · Accepted Answer · 2021-01-15 07:28:32Z

0

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; 
}

answered Jan 15, 2021 at 7:28

Rishi Sharma

32 bronze badges

1 Comment

creyD Over a year ago

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!

Collectives™ on Stack Overflow

insert into sorted array

5 Answers 5

Comments

Comments

Comments

2 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related