Solved

How I can insert entry in sorted array

Posted on 2007-12-06
12
1,014 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 3
  • 2
  • +2
12 Comments
 
LVL 45

Expert Comment

by:Kent Olsen
ID: 20423854
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
ID: 20423929
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
ID: 20423994
Do you need to do this in an array, or can you use other (STL) containers ? Like std::map or std::list ?
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:sisqu
ID: 20424016
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
ID: 20424114
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
ID: 20424591
>> 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
 
LVL 55

Expert Comment

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

Assisted Solution

by:Kent Olsen
Kent Olsen earned 250 total points
ID: 20424981

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
ID: 20426504
>> 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
ID: 20426574
>> I don't know the requirements, so I'm just throwing out suggestions ;)
Fair enough :)
0
 
LVL 45

Expert Comment

by:Kent Olsen
ID: 20427021

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
ID: 31413273
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

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
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 viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

726 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