6 - Stack

A Stack is a collection of items in which only the most recently added item may be removed. The latest added item is at the top. Basic operations are push and pop. Often top and isEmpty are available, too. Also known as "last-in, first-out" or LIFO (see NIST-DADS' definition of stack). We may think a stack is a cramp storage area, where the first item going in, will certainly last to comes out.

Basic operation of stack are :

1. push
2. pop

The program bellow is an example of simple stack operation :

#include "iostream"
using namespace std;

#define n 10
int Stack[n]; //declaring a stack
int Top; //declaring the Top index of a stack
int i; //general counter

void initialize(void)
{
Top = -1;
}

int stillunfilledup(void)
{
if (Top < n-1) //stack is not full yet
{
return 1;
}
else
{
return 0;
}
}

void push(int X)
{
Top =Top +1;
Stack[Top] = X;
}

int notempty(void)
{
if (Top > -1)
{
return 1;
}
else
{
return 0;
}
}

int pop()
{
int X=Stack[Top];
Top = Top -1;
return X;
}


int main(void)
{
int X;
int i;

initialize();


cin >> X;
while (X != 9999) //loop for pushing. As long as the user do not input 999, the loop runs
{
if (stillunfilledup()) //stack is not full yet
{
push(X);
}
else //stack is full
{
cout << "Stack is full";
break;
}
cin >> X;
}

cout << endl << endl << endl;
for (i = 0; i < n; i++)//loop for popping
{
if (notempty())
{
X = pop();
cout << "Pops the " << Top+1 << " th member" << X << endl;
}
else
{
cout << "empty";
}
}
}

5 - Sorting Algorithm : Shell Sort

Another sorting algorithm is Shell Sort. It is based on insertion sort. This sorting method performs multiple passes through the array. Every time it passes the array it performs insertion sort. It divide the arry into several sets. A set grows every time the algorithm works on the array. Of course we need to understand that each members' location is not adjacent to each other (NOT CONTIGOUS). I will present two Shell sort alogoritms : one is for ascending sort and the other is for descending sort :

The first one is ascending sort :
#include "iostream"
using namespace std;

int main(void)
{
int data[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int temp;
int increment;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

increment = 3;
while (increment > 0)
{
for (i=0; i < 8; i++)
{
j = i;
temp = data[i];
while ((j >= increment) && (data[j-increment] > temp))
{
data[j] = data[j - increment];
j = j - increment;
}
data[j] = temp;
}
if (increment/2 != 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

return 0;
}

And here is for descending sort :
#include "iostream"
using namespace std;

int main(void)
{
int data[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int temp;
int increment;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

increment = 3;
while (increment > 0)
{
for (i=0; i < 8; i++)
{
j = i;
temp = data[i];
while ((j >= increment) && (data[j-increment] < temp))
{
data[j] = data[j - increment];
j = j - increment;
}
data[j] = temp;
}
if (increment/2 != 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

return 0;
}

4 - Sorting Algorithm : Insertion Sort

Another sorting algorithm that we can use is insertion sort. We can use it for doing ascending or descending sorting :

1. If we need to do ascending sort, then we need to compare two elements : if we find an element whose value is greater than temp place its value to right.
2. If we need to do descending sort, then we need to compare two elements : if we find an element whose value is less than temp place its value to right.

First we have a program Insertion Sort - Ascending :
#include "iostream"
using namespace std;

int main (void)
{
int data[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int k;
int temp;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

for (i = 1; i < 8; i++)
{
temp = data[i];
j = i-1;
while ((j >= 0) && (data[j] > temp))
{
data[j+1] = data[j];
j = j-1;
}
data[j+1] = temp;
}

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}
return 0;
}

Next we are presented with Insertion Sort - Descending :

#include "iostream"
using namespace std;

int main (void)
{
int data[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int k;
int temp;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

for (i = 1; i < 8; i++)
{
temp = data[i];
j = i-1;
while ((j >= 0) && (data[j] < temp))
{
data[j+1] = data[j];
j = j-1;
}
data[j+1] = temp;
}
cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}
return 0;
}

Next we will discuss Shell Sort

3 - Sorting Algorithm : Selection Sort

The code below is an example of Selection Sort - ascending. It ascending sorts an array :
#include "iostream"
using namespace std;

int main (void)
{
int data[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int k;
int temp;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

for (i = 0; i < 8; i++)
{
int k = i;
for (j = i + 1; j < 8; j++)
{
if (data[j] < data[k]) // Ascending Sort
{
k = j;
}
}
int t = data[i];
data[i] = data[k];
data[k] = t;
}

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

return 0;
}

Next we have descending sort :
#include "iostream"
using namespace std;

int main (void)
{
int data[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int k;
int temp;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

for (i = 0; i < 8; i++)
{
int k = i;
for (j = i + 1; j < 8; j++)
{
if (data[j] > data[k]) //descending sort
{
k = j;
}
}
int t = data[i];
data[i] = data[k];
data[k] = t;
}

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

return 0;
}

2 - Sorting Algorithm : Bubble Sort

One of the algorithm for sorting is Bubble Sort. It is called bubble sort because the way it sorts is like bubble in a glass of soda. The smallest integer will "bubble up" after the sorting. The program bellow is an example of such algorithm. It ascending sorts the array.

#include "iostream"
using namespace std;

int main (void)
{
int arrInt[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int temp;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << arrInt[i];
}

for (j=0; j<8;j++)
{
for (i = 0; i < 7; i++)
{
if (arrInt[i] > arrInt[i+1])
{
temp = arrInt[i];
arrInt[i] = arrInt[i+1];
arrInt[i+1] = temp;
}
}
}

cout << endl;
for (i = 0; i < 8; i++)
{
cout << arrInt[i];
}
}


Next we have another example descending sort :

#include "iostream"
using namespace std;

int main (void)
{
int arrInt[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int temp;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << arrInt[i];
}

for (j=0; j<8;j++)
{
for (i = 0; i < 7; i++)
{
if (arrInt[i] < arrInt[i+1])
{
temp = arrInt[i];
arrInt[i] = arrInt[i+1];
arrInt[i+1] = temp;
}
}
}

cout << endl;
for (i = 0; i < 8; i++)
{
cout << arrInt[i];
}
}

The bubble sort algorithm is arguably one of the easiest algorithm to memorize even though it is not particularly efficient. Therefore next we are going to explore another sorting algorithm : Selection Sort for sorting an array in ascending and descending manners.

Recursion - Basic

Recursion
An algorithmic technique where a function, in order to accomplish a task, calls itself with some part of the task. To be short it is a function that calls itself. NIST-DADS states that a recursive function consists of two major parts or cases, the second part having three components.
1.base case(s), in which the problem is simple enough to be solved directly, and
2.recursive case(s). A recursive case has three components:
1.divide the problem into one or more simpler or smaller parts of the problem,
2.call the function (recursively) on each part, and
3.combine the solutions of the parts into a solution for the problem.
Depending on the problem, any of these may be trivial or complex.
To make us understand what sort of algorithm this technique is, lets have a look at the code bellow :
#include
using namespace std;
void RecursiveIncrement(int i)
{
if (i ==10) //Base case : display value of i if i == 10
{
cout << i;
}
else //Recursive case : display value of i
{
cout << i << endl;
RecursiveIncrement(++i);
}
}

int main(void)
{
RecursiveIncrement(1);
return 0;
}
The program above display integer values from 1 to 10. The base case display the value of i if its value is 10. The recursive case display the values from 1 to 9.
We have another example of such algorithm. The program work just like the previous program except that it will display the value of 10 to 1. The source code is presented below :

#include
using namespace std;

void RecursiveDecrement(int i)
{
if (i == 1)
{
cout << i;
}
else
{
cout << i << endl;
RecursiveDecrement(--i);
}
}

int main(void)
{
RecursiveDecrement(10);
return 0;
}

Those two programs are fairly simple. We are going to explore the usage of recursion to navigate several type of data list.