Solved

How I can insert entry in sorted array

Posted on 2007-12-06
12
1,011 Views
Last Modified: 2012-06-27
In C++ programming: I have a sorted array and  position of entry I want to insert in this array, the problem is that every elements of this array must shifted one position right. I wander because the size of array must increase, how it will done?  or there is easier way to insert entry. I'm not very experienced in c++. In JAVA for this there are a static System.arraycopy() method we can use to copy one array to another or copy elements of the same array from one position to another. please help :(((
0
Comment
Question by:sisqu
  • 3
  • 3
  • 2
  • +2
12 Comments
 
LVL 45

Expert Comment

by:Kdo
Comment Utility
Hi sisqu,

If the array is fixed length (define with 'int Array[SIZE]') you can not extend the array.  If it's not full you can, of course, move the items down the array and insert the new value.

If you want a dynamic array, you can certainly do that.  There are a number of classes already defined that will maintain lists for you, (TList, std::vector, etc.) but if you want to build one yourself it's pretty easy.

The key item is that the array must be define as 'int *Array' and memory allocated to it with the 'new' operator.  When an item is added, the class must check that the Array has room for the new item.


If you'd like, I'll be glad to help with the basic code to do this.  But as I said, the easiest way is to use one of the C++ classes that are part of the standard libraries.  (Your instructor may feel differently.)


Good Luck,
Kent
0
 
LVL 55

Accepted Solution

by:
Jaime Olivares earned 250 total points
Comment Utility
Basic task to acomplish this is:
reserve a new buffer (bigger), you can use c++'s new operator or malloc() classic function.
copy all the elements to the buffer, leaving a hole for the new item, memcpy() is the fastest way to do it.
copy the contents of the new item into the hole in the array, memcpy() again will be useful.

A well known technique to avoid loss of performance due to continuously reallocating memory with new element, is to reserve more space than needed, and keep the size of buffer and size of array in 2 variables.
then, the memcpy() operations will be still needed, but the reallocation will be less frequent.
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
Do you need to do this in an array, or can you use other (STL) containers ? Like std::map or std::list ?
0
 

Author Comment

by:sisqu
Comment Utility
Hi Kent
yes,  the better way to me is a part of code if you don't mind.
  So I  made a binary search in a sorted array a[] that return that the element is not in a array but it must be in position p if it was.
I wanted to write a function insert()  which insert that element in array, in position p ,shifted  all elements after p one position right like this:
 void insert (p, int *a) {.....

}
please help to make this function,or if there is easier way tell me
0
 

Author Comment

by:sisqu
Comment Utility
hi Infinity08,
No I'm not allowed to use any librares. I must do it in a array
the same or another, but also sorted with new entry
0
 
LVL 40

Expert Comment

by:evilrix
Comment Utility
>> or there is easier way to insert entry.
Well yes, it's called STL! Look at std::list and std::vector (um, not std::map as that is an associative array !).

>> In JAVA for this there are a static System.arraycopy() method we can use to copy one array to another or copy elements of the same array from one position to another.
Unfortunately, C/C++ are far less forgiving (but more flexible) than Java. If you have a fixed size array (either stack or heap based) you will need to create a new array. You will need to create a new array and copy everything from, old to new and insert the new item. You might want to consider using a linked list rather than an array as this is better suited to inserts.
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 55

Expert Comment

by:Jaime Olivares
Comment Utility
well, you can start following my little steps....
0
 
LVL 45

Assisted Solution

by:Kdo
Kdo earned 250 total points
Comment Utility

Since this is a C++ forum, let's write C++ code.

A class is called for to encapsulate all of the logic.

This should get you a good way toward understanding and completing this.

  :)



Kent



class vlist   // Variable length integer list

{

  public:

    vlist ();    // need a constructor to initialize some things

    ~vlist ();   // need to release any assigned memory
 

  int   *Array;  // Should be a private object, but this codes shorter

  int   Used;    // same here

  int   Limit;   // and here
 

  int   Add (int NewValue);  // returns 0 if not added

};
 

vlist::vlist ()

{

  Used = 0;

  Limit = 100;

  Array = new int [Limit];

}
 

vlist::~vlist ()

{

  delete Array [];

}
 

int vlist::Add (int NewValue)

{

  int *NewArray;
 

  if (Used == Limit)

  {

    NewArray = new int [Limit * 2];

    memcpy (NewArray, Array, Limit * sizeof (int));

    delete Array [];

    Array = NewArray;

  }
 

//  Now just add the new value
 

//  Return non-zero if it was added, 0 if not.  (Perhaps you don't store duplicates.)
 

}

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> Well yes, it's called STL! Look at std::list and std::vector (um, not std::map as that is an associative array !).

Why not (if the primary goal is sorting with extra data) ? I don't know the requirements, so I'm just throwing out suggestions ;)
0
 
LVL 40

Expert Comment

by:evilrix
Comment Utility
>> I don't know the requirements, so I'm just throwing out suggestions ;)
Fair enough :)
0
 
LVL 45

Expert Comment

by:Kdo
Comment Utility

Sorry.  :)  Forgot a little thing in Add().  Just in case you haven't figured that out yet:


int vlist::Add (int NewValue)

{

  int *NewArray;

 

  if (Used == Limit)

  {

    NewArray = new int [Limit * 2];

    memcpy (NewArray, Array, Limit * sizeof (int));

    delete Array [];

    Array = NewArray;

    Limit *= 2;             // Need to record that the array has grown.  :)

  }

 

Open in new window

0
 

Author Closing Comment

by:sisqu
Comment Utility
Thanks to you all, guys!! You were so useful for me, I think I must split points between jaime_olivares and Kdo, they two give me something to think about
0

Featured Post

6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

Join & Write a Comment

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

8 Experts available now in Live!

Get 1:1 Help Now