27452

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?

Answer1:

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

Answer2:

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).

Answer3:

To push the rest of the array element's you should use a loop. Just be carfare 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.

Answer4:

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

Recommend

  • Jquery ui draggable - auto resize parent containment [duplicate]
  • How can I fill out void* C pointer in Go?
  • sizeof(array) / sizeof(int) [duplicate]
  • How to best show progress info when using ADO.NET?
  • C Pointer confusion
  • Difference between 2D char Array and char** (OR, 3D char Array and char*** etc)
  • wcstombs() has invalid output on Android
  • Conflicting Types Error
  • Pipe for multiple processes
  • Can we reuse allocated memory
  • Why must we Forward Declare a class and include the corresponding header file in a header file
  • Getting segmentation fault while using malloc
  • OSStatus error -50 (invalid parameters) AudioQueueNewInput recording audio on iOS
  • How to work with AMMediaType for video filters
  • Problem in concatenation of objects in javascript
  • What is this strange character in chrome's resource css viewer?
  • Is there any way to call saveCurrentTurnWithMatchData without sending a push notification?
  • Angular Bootstrap Carousel Slide Transition not working correctly
  • cell spacing in div table
  • How to unpack 32bit integer packed in a QByteArray?
  • Angular2 - Template reference inside NgSwitch
  • XSLT foreach repeating nodes to flat
  • How to create a 2D image by rotating 1D vector of numbers around its center element?
  • Thread 1: EXC_BAD_ACCESS (code =1 address = 0x0)
  • Silverlight DependencyProperty.SetCurrentValue Equivalent
  • How to use carriage return with multiple line?
  • How to rebase a series of branches?
  • Why is the size of this struct 32?
  • When should I choose bucket sort over other sorting algorithms?
  • How do I rollback to a specific git commit
  • Unanticipated behavior
  • Easiest way to encapsulate a HTML5 webpage into an android app?
  • Busy indicator not showing up in wpf window [duplicate]
  • costura.fody for a dll that references another dll
  • Observable and ngFor in Angular 2
  • How to Embed XSL into XML
  • UserPrincipal.Current returns apppool on IIS
  • Conditional In-Line CSS for IE and Others?
  • java string with new operator and a literal
  • How to push additional view controllers onto NavigationController but keep the TabBar?