An array stores a list of items. And there are certainly many things that we can do with a list of items. We can add a new item, delete old one, search for a particular item, print the list, invert it, and so many, many other stuff.
Here's an example array, one that stores a list of locations.
Each location contains a name and an (x,y) coordinate
The items in the array above are of course not simple elements. Think of each as an object or as a struct, one that can be defined something like as follows:
struct Location {
string name;
int x, y;
}
The array itself can be declared as follows:
Location locations[5];
int numItems = 0;
numItems here stores the number of locations stored so far. Everytime, u add an item to locations, u need to increment its value, and vice versa.
addItem
Now, suppose we would like to add a new item to the array, and we want the array to remain sorted based on location names, like as shown below:
The question is how to add a new item - for example, 'Chiang Mai', 300, 275
We would like add the 'Chang Mai' item between 'Bangi' and 'Ciwedey'. 'Bangi' is in index 1, and 'Ciwedey' in index 2. We can't just write 'Chiang Mai' into index 2 - we would lost 'Ciwedey' then. What we have to do then is to move 'Ciwedey' one step to the right, like as shown here:
Hence, assuming something like as above, the code for the addItem function that performs the above would look like as follows:
void addItem(Location loc)
set index to 2
set locations[index+1] to locations[index];
set locations[index] to loc;
increment numItems
In the pseudocode above, loc is the object/struct that contacts 'Chang Mai'.
But of course, it can be that simple if we have only one item to shift. What if we have more, like as shown here:
We need to shift the last element first then, and continue backward from there. This is done in the code below:
void addItem(Location loc)
set index to 2
for each location i from numLoc down to index+1
set locations[i] to locations[i-1]
set locations[index] to loc
increment numItems
When we run code as per the logic above, as follows, we should get the list shown below:
Ok, things look better now. But what about the index for insertion? We can't assume that it's always going to be at index 2, especially if the list is to remain sorted. So the question is, how to compute the index at which the insertion is to be done. This can be done as shown below:
Suppose you are adding a 'Changkat' item, as shown below. You need to check one by one the existing items in the array, to see which one is occupying a position that rightfully belongs to 'Changkat'. So you start with 'Alor Star'.
Compare between 'Changkat' and 'Alor Star' - which is bigger? 'Changkat' of course, so you move on to the next item in the array:
'Changkat' is still bigger than 'Bangi', so we have to move on:
'Changkat' is bigger than 'Ciwedey' too, so we go to the next item:
Now, 'Changkat' is not more than 'Dengkil'.
It means we need to park 'Changkat' where 'Dengkil' is. The index for insertion is then 3.
The modified code for addItem is then as follows:
set index to 0
while locations[index].name is less than loc.name
increment index
for each location i from numLoc down to index+1
set locations[i] to locations[i-1]
set locations[index] to loc
increment numItems
Consider now how much work will need to be done by the code. The main work is done in the loops. The worst possible number of iterations for the while loop is the entire length of the list, if the new item is to be added at the very end. How do we express this?
We say that the worst case complexity of this particular loop is O(N), where N is the length of the list.
In the same way, consider the for loop. In the worst possible scenario (one that corresponds to the most amount of work), we are inserting right at the first index. We then need to do shifts, the number of which is equal to the length of the list. The complexity here is then O(N) as well.
The overall complexity of the code is O(N) + O(N) = O(2N). But we don't bother with the coefficient 2, since mathematically O(N) means in the worst possible case,
where f(N) is the actual number of steps, and c is a constant.
So what the equation above is saying is that the actual number of steps is at most the length of the list multiplied by a certain constant c.
deleteItem
We consider now the task of deleting an item. Suppose for example, we need to remove 'Bangi':
We can't leave a gap at the spot where 'Bangi' is to be removed. Otherwise there would be gaps here and there after a few deletions, and our items would not be in contiguous locations. We need to shift items to fill up the gap left by a deleted item, as shown in the picture above.
In code, it would look as follows to delete item at index:
void deleteItem(int index)
for i from index to numItem-1
set locations[i] to locations[i+1]
decrement numItems
Here's a question: what is the complexity of the delete operation?
searchItem
How do we search for an item? We are given the task for example of finding 'Ciwedey' in the list:
As depicted above, and as in the case for addItem, you will need to go one by one, checking the element in the array with the target.
Now here's for you to think:
1. Write the pseudocode for the search operation
2. What's the complexity?
No comments:
Post a Comment