13.2 Common Algorithms
13.2 Common Algorithms
Libraries are a store, or a collection, of functions, variables, and classes that can be reused by a programmer in many different programs. Among the thousands of possible functions there are some common, standard functions that are particularly useful. A function that is a series of steps to achieve a specific purpose is called an algorithm, and the following subsections examine a select number of useful functions a programmer might want included in a library for use in his software. These subsections are in no particular order.
13.2.1 Bubble Sort
Imagine for a moment a series of 10 gamers playing a game and each receives a high score. Some of their scores will be higher than others, and the scores must be shown on a high score board at the end of the game. The board lists the top 10 players in order of their scores, highest to lowest. The purpose of this section therefore is to code a function that accepts a list of data as an argument, like a list of scores. And, given a list of data, it is to sort that data in descending numerical order, from the highest to lowest. An effective and simple algorithm for sorting data like this is called a bubble sort. The algorithm follows, first in written form.
Let's assume we have the following numbers:
-
5, 7, 8, 93, 41, 1
-
If the list (of numbers) contains fewer than two items, then it doesn't need sorting; otherwise it can be sorted.
-
Take the first item in the list (5), and the next (7). Compare the two items. If the second item is greater than the first, then swap their positions in the list. So the list becomes:
-
7, 5, 8, 93, 41, 1
-
-
Move on to the second item in the list (5), and take the next item too (the third item; 8 in this case). Compare the two items. If the third item is greater than the second, then swap their positions in the list. So the list becomes:
-
7, 8, 5, 93, 41, 1
-
-
Repeat this process for each item in the list until the end is reached.
-
Once the loop is completed, repeat from the beginning. When a complete iteration (cycle) of the list has occurred and no exchanges have been made, then the sorting is completed since every item is already in the right order.
To demonstrate the bubble sort algorithm, consider the following program:
#include <iostream> void bubbleSort(int *array,int length)//Bubble sort function { if((!array) || (length < 2)) return; bool bCompleted = false; while(!bCompleted) { bCompleted = true; for(int i=0;i<length;i++) { for(int j=0;j<i;j++) { if(array[i]<array[j]) { int temp=array[i]; //swap array[i]=array[j]; array[j]=temp; bCompleted = false; } } } } } void printElements(int *array,int length) //print array elements { for(int i=0;i<length;i++) std::cout<<array[i]<<std::endl; } int main(int argc, char *argv[]) { int numbers[] = {5,9,3,1,4,8}; bubbleSort(numbers, 6); printElements(numbers, 6); return 0; } The bubble sort technique is designed to sort data in some kind of order, either ascending or descending. Its use is, of course, not restricted to just a high score board, and is only limited by your imagination. For example, it can be used to determine who finished first in a race or which player has the most or least money, or to rank a series of creatures on a scale of most powerful to least powerful, and so on.
13.2.2 Linked Lists
In a real-time strategy game a player can usually build up an army, develop buildings, and collect resources. For example, a player's army might contain seven tanks, 50 snipers, three helicopters, and so on. Naturally, as new units are created and old ones are destroyed in conflict, the list and number of units any army may have will change. The players may keep a mental list of troops and equipment; however, the computer must also keep track of each army's units and resources to make sure the game is played properly. After all, it would be rather annoying if a computer game forgot about specific units and buildings that a player spent valuable time developing, and they just vanished into thin air. So therefore, a computer must also keep track of everything a player does, as well as everything any opposing armies do. Since the list of units any army has will change as new ones are created and old ones destroyed, the computer must keep track of a continually changing list of units. What is needed is a list of items that can grow and shrink according to however many items need to be stored. This problem can be solved using linked lists.
A linked list is a linear list of items. The list begins at the first item, and each item maintains a pointer to the next item in the list as well as a pointer to the previous item. The last item has a next pointer to NULL (which means nothing, nowhere, undefined), as shown in Figure 13.1. And the first item has a previous pointer to NULL since there is no item before it. Consider the following class declaration:
class cListItem { private: public: cListItem *m_Next; cListItem *m_Previous;xs std::string MonitorName; cListItem(); }; cListItem::cListItem() { m_Next = m_Previous = NULL; } 
Figure 13.1
Figure 13.2
As shown in the illustration above, to add item 4 to the list, the next pointer of the current last item (3) is changed; it is no longer NULL and instead now points to the newly added item 4. The newly added item 4 becomes the last item in the list and its next pointer is NULL.
void AddItem(cListItem *List, cListItem *Item) { if(!List) { List = Item; } else { cListItem *NextItem = List; while(NextItem->m_Next) NextItem = NextItem->m_Next; NextItem->m_Next = Item; } } 
Figure 13.3
Here, we illustrate removing item 3 from the list. First, the next pointer of item 3 is taken, which points to item 4. The previous pointer of item 3 is also taken, which points to item 2. Item 3 can now be deleted and the gap it occupied is repaired as 2 is linked to 4. The next pointer of 2 is 4, and the previous pointer of 4 is 2.
void RemoveItem(cListItem *Item) { if(!Item) return; cListItem *PreviousItem = Item->m_Previous; cListItem *NextItem = Item->m_Next; delete Item; if(PreviousItem) PreviousItem->m_Next = NextItem; if(NextItem) NextItem->m_Previous = PreviousItem; } void ClearList(cListItem *List) { cListItem *Item = List; while(Item) { cListItem *NextItem = Item->m_Next; delete Item; Item = NextItem; } } The following program adds some items to a list.
#include <iostream> #include <sstream> class cListItem { private: public: cListItem *m_Next; cListItem *m_Previous; std::string MonitorName; cListItem(); }; cListItem::cListItem() { m_Next = m_Previous = NULL; } void AddItem(cListItem *List, cListItem *Item) { if(!List) { List = Item; } else { cListItem *NextItem = List; while(NextItem->m_Next) NextItem = NextItem->m_Next; NextItem->m_Next = Item; } } void RemoveItem(cListItem *Item) { if(!Item) return; cListItem *PreviousItem = Item->m_Previous; cListItem *NextItem = Item->m_Next; delete Item; if(PreviousItem) PreviousItem->m_Next = NextItem; if(NextItem) NextItem->m_Previous = PreviousItem; } void ClearList(cListItem *List) { cListItem *Item = List; while(Item) { cListItem *NextItem = Item->m_Next; delete Item; Item = NextItem; } } void PrintList(cListItem *List) { if(List) { cListItem *NextItem = List; while(NextItem) { std::cout<<NextItem->MonitorName + "\n"; NextItem = NextItem->m_Next; } } } int main(int argc, char *argv[]) { cListItem *List = new cListItem(); List->MonitorName = "0"; //Fill the list for(int counter = 1; counter < 10; counter++) { std::string MonitorName = ""; std::stringstream ss; ss<<counter; ss >> MonitorName; cListItem *Item = new cListItem(); Item->MonitorName = MonitorName; AddItem(List, Item); } PrintList(List); ClearList(List); return 0; } | Note | For a ready-made list class, try searching the net for std::vector. |
13.2.3 Stacks-Pop and Push
One of the most important concepts on a computer is the idea of undo. For example, some letters are typed into a word processor, and then some more, and then perhaps a picture is inserted. If a user then clicks on the Undo button, the most recent action will be undone. More importantly, each action will be undone in reverse order. So, the most recent action will be undone first, and then the next item to be undone is the action prior to that, and then prior to that, and so on for however many operations need to be undone. This kind of structure is called a stack, also known as a LIFO stack (Last In First Out), and it is based upon a linked list.
When an item is added to the list, it is said to be pushed onto the top of the stack, like bricks being added to the levels of a tower. When the most recent item is taken off the list (the top item), it is said to be popped off the stack.
Figure 13.4
Really, a stack is a linked list with an addition feature added. We already know how Push works from the linked list's AddItem method, where items are added to the end (or top) of the list. Pop is therefore a method that returns the last item and removes it from the list. Thus, a stack class may be easily coded by adding the following linked list method:
cListItem *Pop(cListItem *Item) { if(!Item) return NULL; cListItem *PreviousItem = Item->m_Previous; cListItem *NextItem = Item->m_Next; if(PreviousItem) PreviousItem->m_Next = NextItem; if(NextItem) NextItem->m_Previous = PreviousItem; return Item; } | Note | The Pop method is almost the same as RemoveItem. The difference is that Pop removes an item from the list, but does not delete it from memory. RemoveItem, however, deletes an item from both the list and memory. |
| Note | For a ready-made stack class, try searching the net for std::stack. |
13.2.4 Binary Heaps
Sorting a list of items is useful, as demonstrated with bubble sort. But there are times when, given a set of data, the only item of interest is the highest or the lowest item of the set. Each time a programmer queries the set, by popping off the top item from the stack for example, the only item he expects to receive is the highest, or lowest, depending on his needs. In such cases, a faster though more complex structure known as a binary heap can be used. A binary heap is faster because this structure ensures only the highest or lowest item is sorted through the data, and it spends no time sorting other elements in the set.
A binary heap looks like a tree, as shown in Figure 13.5. Each item is called a node. The node at the top is called a root node, and the others are descendant nodes, or child nodes. Each node in a binary heap can have no more than two child nodes (hence the name binary). The root node will always be the item of interest: the one that is either the greatest or the lowest value in a set. The others below will be either less than or greater than the top node, depending on whether the tree is being sorted by highest or lowest. For the purposes of this and the following examples, it will be assumed that the lowest value will always be the root node. Thus, the top node will be the lowest of the set and all others below will be higher, but not necessarily in any order.
Figure 13.5
13.2.4.1 A Breakdown
Binary heaps can be represented in many ways, using different data structures including linked lists, but one of the more efficient for our purposes is a one-dimensional array, in the form of Numbers[size]. Here, the nodes are stored in a linear list with the root node being the first element of the array at 1. This element is then followed by its two child nodes, and so on. In short, given the index of some node X in the array, say at position 5, it's possible to find the array index for its two child nodes by using a formula. The formula to find the first child of node X is to multiply the array index of X by 2, and since the second child appears next to the first, the formula for the second child is to multiply by 2 and add 1. So, for node X at position 5, child node 1 is at position 10, and child node 2 is at position 11. For this reason, the first child will have an index that is always an even number, and the second child will have an index that is always odd.
13.2.4.2 Child and Parent
Given the position of some node X in the array it is similarly possible to find its parent using the inverse formulas for finding a child. If X has an even index, then it is the first child of a node and its parent index can be found by dividing its own index by 2. If X is odd, then it is the second child, and the formula will be its own index minus 1 and then divided by 2.
13.2.4.3 Pushing Items
class cBinaryHeap { private: protected: public: int m_Items[50]; int m_itemCount; }; The above is a sample class set up to be a binary heap. It contains an array for the items, and a counter to determine how many items are in the list. This counter begins at 0, meaning the list is empty. Nodes that are added to a binary heap are said to be pushed onto the heap. A node is pushed onto the end of the array, and consequently made a child of the last parent node. It may not remain here, however. The newly added node may, after all, be the lowest in the heap, in which case it needs to filter its way through the hierarchy of nodes until it reaches the top. The method by which a node is added occurs as follows:
-
The item is added at the bottom of the tree.
-
It is then compared with its parent. If its value is greater than its parent, it remains where it is; otherwise it is swapped with its parent.
-
The item is then compared with its new parent, and this process repeats every time it is less than its parent. The process will stop when it reaches a parent that is not greater, or when it reaches the top of the heap, in which case it has become the lowest item.
Figure 13.6
Figure 13.7
Figure 13.8
The following code demonstrates how this procedure works.
void Push(int Number) { //Add New Item m_itemCount++; m_Items[m_itemCount] = Number; //Bubble to top if(m_itemCount <= 1) return; bool Swap = true; int CurrentItem = m_itemCount; while(Swap) { Swap = false; //Get Parent Item int ParentIndex = 1; if(CurrentItem%2 == 0) //if even number ParentIndex = CurrentItem/2; else ParentIndex = (CurrentItem-1)/2; if(m_Items[ParentIndex] > m_Items[CurrentItem]) { //Swap int tmpItem = m_Items[ParentIndex]; m_Items[ParentIndex] = m_Items[CurrentItem]; m_Items[CurrentItem] = tmpItem; if(ParentIndex == 1) //If top item return; CurrentItem = ParentIndex; Swap = true; continue; } return; } }
13.2.4.4 Popping Items
The Push method is effective because it ensures that whatever item is placed on the heap will filter to the top if it is the lowest. This means that when the top item is popped off the list, it will be the lowest item among them. But at this point, once the top item is removed, what happens to the rest of the items? If the items are not sorted beyond the top item being the lowest, then how can the next lowest become the new top item? The process of popping an item off the binary heap works as follows:
-
The top item is removed.
-
The last item then becomes the new top item.
-
The top item is then compared to its lowest child. If its lowest child is higher than itself, then they swap places.
-
If they swap places, then the item compares itself to its new lowest child, and so the process repeats.
-
The process stops when none of its children are lower or it has reached the bottom of the heap. This ensures the top item will always be the lowest after an item has been popped.
Figure 13.9
Figure 13.10
Figure 13.11
The following code demonstrates how this process works.
int Pop() { if(m_itemCount <= 0) return 0; //Empty int Number = m_Items[1]; //Get First Item m_Items[1] = m_Items[m_itemCount]; //Last To Front m_itemCount--; if(m_itemCount <= 1) //If no items, or last item return Number; //Sink to bottom int CurrentItem = 1; bool Swap = true; while(Swap) { Swap = false; int FirstChildIndex = CurrentItem * 2; int SecondChildIndex = (CurrentItem * 2) + 1; int LowestIndex = FirstChildIndex; //Check if second is lowest if(SecondChildIndex <=m_itemCount) if(m_Items[SecondChildIndex] < m_Items[FirstChildIndex]) LowestIndex = SecondChildIndex; if(m_Items[CurrentItem] > m_Items[LowestIndex]) { //Swap int TmpNumber = m_Items[LowestIndex]; m_Items[LowestIndex] = m_Items[CurrentItem]; m_Items[CurrentItem] = TmpNumber; CurrentItem = LowestIndex; //If no further children, then return if((CurrentItem*2) > m_itemCount) return Number; Swap = true; } return Number; } }
13.2.4.5 Application
The previous two sections demonstrated how items can be pushed and popped from a binary heap. In this section some code is provided to demonstrate an application that uses the newly developed binary heap class. This sample application simply pushes on a few numbers in no particular order and then pops them off the heap. Naturally, the items are all popped off in numerical order, with the smaller items being first and the later ones being higher. The following code lists the full source of this application, with comments, and it can also be found in the downloadable sample files for this chapter.
#include <iostream> #include <sstream> class cBinaryHeap { private: protected: public: int m_Items[50]; int m_itemCount; cBinaryHeap() { for(int i=0; i<50; i++) m_Items[i] = -1; m_itemCount = 0; } void Push(int Number) { //Add New Item m_itemCount++; m_Items[m_itemCount] = Number; //Bubble to top if(m_itemCount <= 1) return; bool Swap = true; int CurrentItem = m_itemCount; while(Swap) { Swap = false; //Get Parent Item int ParentIndex = 1; if(CurrentItem%2 == 0) //if even number ParentIndex = CurrentItem/2; else ParentIndex = (CurrentItem-1)/2; if(m_Items[ParentIndex] > m_Items[CurrentItem]) { //Swap int tmpItem = m_Items[ParentIndex]; m_Items[ParentIndex] = m_Items[CurrentItem]; m_Items[CurrentItem] = tmpItem; if(ParentIndex == 1) //If top item return; CurrentItem = ParentIndex; Swap = true; continue; } return; } } int Pop() { if(m_itemCount <= 0) return 0; //Empty int Number = m_Items[1]; //Get First Item m_Items[1] = m_Items[m_itemCount]; //Last To Front m_itemCount--; if(m_itemCount <= 1) //If no items, or last item return Number; //Sink to bottom int CurrentItem = 1; bool Swap = true; while(Swap) { Swap = false; int FirstChildIndex = CurrentItem * 2; int SecondChildIndex = (CurrentItem * 2) + 1; int LowestIndex = FirstChildIndex; //Check if second is lowest if(SecondChildIndex <=m_itemCount) if(m_Items[SecondChildIndex] < m_Items[FirstChildIndex]) LowestIndex = SecondChildIndex; if(m_Items[CurrentItem] > m_Items[LowestIndex]) { //Swap int TmpNumber = m_Items[LowestIndex]; m_Items[LowestIndex] = m_Items[CurrentItem]; m_Items[CurrentItem] = TmpNumber; CurrentItem = LowestIndex; //If no further children, then return if((CurrentItem*2) > m_itemCount) return Number; Swap = true; } return Number; } } }; int main(int argc, char *argv[]) { cBinaryHeap Heap; Heap.Push(5); Heap.Push(1); Heap.Push(53); Heap.Push(9); std::cout<<Heap.Pop()<<"\n"; //1 std::cout<<Heap.Pop()<<"\n"; //5 std::cout<<Heap.Pop()<<"\n"; //9 std::cout<<Heap.Pop()<<"\n"; //53 return 0; } 
EAN: 2147483647
Pages: 225