CODEWITHSUNDEEP
c++
J.J.
J.J.

Reputation: 105

How to insert values into an array alphabetically?

I need the insert function to take an argument and then add it to a list, but instead of it simply adding it to the end, it finds the alphabetical position and adds it there. So, if the array was {1, 3, 4} and we were adding 2 to the array, it would find the index to add it, which would be index 1, shift all of the index past that insertion point down. However, I simply cannot for the life of me figure out how to write the logic behind it.

Assume the array isn't full and there is extra space to move the items down in the array.

I can't use another array to copy values or anything like that. I NEED to shift the values down the array and insert the value at the proper point all within the insertion function.

/*************************************
 * insert()
 *************************************/
bool people::insert(person arg)
{
    person temp;
    int i, value, insertionPoint;

    // Check to see if array is full

    cout << "Array size is " << len << endl;

    if (len >= LIST_SIZE)
    {
        cout << "Array null" << endl;
        return false;
    }

    // Adds item if array is empty.
    if (len == 0)
    {
        cout << "FIRST VALUE ADDED which is: " << arg.firstName << endl;
        map[0] = arg;
    }

    // Find Insertion Point

    for (i = 0; i < len; i++)
    {
        if(arg < map[i])
        {
            insertionPoint = i;
        }
        else
        {
            insertionPoint = len;
        }
    }

    for (i = insertionPoint; value > insertionPoint; value--)
    {
        map[value] = map[value - 1];
    }

    return true;
}

Upvotes: 1

Views: 410

Answers (1)

Joseph Larson
Joseph Larson

Reputation: 9068

You have to start at the tail of the list. It looks like you have map[] as your array and len as the current number of elements.

So let's look at some code. You're loop to find the insertion point is flawed. Aside from a binary search being faster:

int insertionPoint = len;
for (int i = 0; i < len; i++)
{
    if(arg < map[i])
    {
        insertionPoint = i;
        break;
    }
}

That's much cleaner. There's no reason to continue to search once you find the insertion point.

Now you have insertionPoint set, so you need to make room. You want to move all pointers from [insertionPoint] to [len-1] up one point, but if you start at [insertionPoint], you'll step all over the rest.

So you do it backwards:

for (int index = len; index > insertionPoint; --index) {
    map[index] = map[index - 1];
}

At that point, you can then:

map[insertionPoint] = arg;
++len;
I'm adding this as the OP has said he's disallowed from using break. I don't know why that would be, but okay. 
int insertionPoint = 0;
while (insertionPoint < len && arg < map[insertionPoint]) {
    ++insertionPoint;
}

This loop won't go past the end. If we find ourselves off the end, insertionPoint will become equal to len, which is what it needs to be. But the loop stops when it should.

Upvotes: 3

Related Questions