INTRODUCTION:

DATA STRUCTURE:
Definition: Data Structures are the programmatic way of storing data so that it can be
stored, updated and retrieved efficiently and effectively.

Examples: For example, we can store a list of items having the same data-type using
the array data structure.

Suppose we want to store ‘n’ number of integers, we will have to declare ‘n’ int variables.
On the other hand, using an array, we can do it in a single statement (int array[n];). Similarly, if
we want to add these ‘n’ numbers, we will have to write all the int variables, but using an array,
we can do it very easily using loops. Similarly, using an array data structure, we can sort, find
and change values very easily.

There are many other examples where data structures are used in real life. Facebook,
Google Maps and many other social media apps use a data structure called Graph. Facebook
uses it to show you mutual connections with your friends on Facebook. Similarly, Google Maps
uses Graphs to show you the shortest path from your location to another location on map.

TYPES OF DATA STRUCTURES:

Although there is not a fixed representation of the division of types of data structures,
they can be categorized as primitive (built-in) and non-primitive (user-defined). Non-primitive
Data Structures are also called as fundamental data structures or classic data structures,
because they are mostly used in almost all application areas and they are used to construct many
other data structures. The below diagram shows types of data structures.

Data structures can also be categorized as static data structures (whose size cannot be
changed) and dynamic data structures (which can change their size).

ALGORITHM:
Definition: An Algorithm is a step-by-step procedure, which defines a set of instructions
to be executed in a certain order to get the desired output.

From the data structure point of view, following are some important categories of
algorithms −
 • Search − Algorithm to search an item in a data structure.
• Sort − Algorithm to sort items in a certain order.
• Insert − Algorithm to insert item in a data structure.
• Update − Algorithm to update an existing item in a data structure.
• Delete − Algorithm to delete an existing item from a data structure.

PROPERTIES OF AN ALGORITHM:
An algorithm is defined as a finite set of instructions that, if followed, performs a
particular task. All algorithms must satisfy the following criteria/properties/characteristics:
Input: An algorithm has zero or more inputs, taken or collected from a specified set of
objects.
Output: An algorithm has one or more outputs having a specific relation to the inputs.
Definiteness: Each step must be clearly defined; each instruction must be clear and
unambiguous.
Finiteness: The algorithm must always finish or terminate after a finite number of steps.
Effectiveness: All operations to be accomplished must be sufficiently basic that they can
be done exactly and in finite length.
Feasibility − Should be feasible (possible) with the available resources.

Independent − An algorithm should have step-by-step directions, which should be

independent of any programming code.

NOTES:

1) We can represent an algorithm in many ways.

• Natural language: We either implement an algorithm in a natural language like English.

• Flow charts: Flow Charts are represented in form of Graphic representations, only if the
algorithm is small and simple.
• Pseudo code: Pseudocode (or “fake” code) is an artificial and informal language that helps
you develop algorithms without having to worry about the details of any programming
language (say C++ language) syntax.

Pseudocode is similar to everyday English; it’s convenient and user friendly,

although it isn’t an actual computer programming language. Pseudocode does not
execute on computers. Rather, it helps you “think out” a program before attempting to
write it in a programming language, such as C++.

• Write an algorithm to add two numbers entered by the user (A Natural Language
Example)

• Step 1: Start
• Step 2: Declare variables num1, num2 and sum.
• Step 3: Read values num1 and num2.
• Step 4: Add num1 and num2 and assign the result to sum.
• sum←num1+num2
• Step 5: Display sum
• Step 6: Stop

• Pseudo Code of above example:

• BEGIN
 • NUMBER s1, s2, sum
• OUTPUT("Input number1:")
• INPUT s1
• OUTPUT("Input number2:")
• INPUT s2
• sum=s1+s2
• OUTPUT sum
• END
NOTES:
We design an algorithm to get a solution of a given problem. A problem can be solved in
more than one ways.
Hence, many solution algorithms can be derived for a
given problem. The next step is to analyze those proposed
solution algorithms and implement the best suitable solution.

Q = Why to learn Data Structures and Algorithms?

Ans = As applications are getting complex and data rich, there are three common problems that
applications face now-a-days.
• Data Search − Consider an inventory of 1 million(106) items of a store. If the application
is to search an item, it has to search an item in 1 million(106) items every time slowing
down the search. As data grows, search will become slower.
• Processor speed − Processor speed although being very high, falls limited if the data
grows to billion records.
• Multiple requests − As thousands of users can search data simultaneously on a web
server, even the fast server fails while searching the data.
To solve the above-mentioned problems, data structures come to rescue. Data can be
organized in a data structure in such a way that all items may not be required to be searched,
and the required data can be searched almost instantly.
Data Structure is a systematic way to organize data in order to use it efficiently. Following
terms are the foundation terms of a data structure.
1) Interface − Each data structure has an interface. An interface provides what type of
operations a data structure supports, type of parameters they can accept and return
type of these operations.
2) Implementation − Implementation provides the internal representation of a data
structure. Implementation also provides the definition of the algorithms used in the
operations of the data structure.

CHARACTERISTICS OF A DATA STRUCTURE:

• Correctness − Data structure implementation should implement its interface correctly.

• Time Complexity − Running time or the execution time of operations of data structure
must be as small as possible.
• Space Complexity − Memory usage of a data structure operation should be as little as
possible.
 ANALYSIS OF ALGORITHMS:

PERFORMANCE ANALYSIS AND MEASUREMENT:

What is performance analysis?

If we want to go from city "A" to city "B", there can be many ways of doing this. We can
go by flight, by bus, by train and also by bicycle. Depending on the availability and convenience,
we choose the one which suits us.

Similarly, in computer science, there are multiple algorithms to solve a problem. When
we have more than one algorithm to solve a problem, we need to select the best one.
Performance analysis helps us to select the best algorithm from multiple algorithms to solve a
problem.

Performance analysis of an algorithm is the process of calculating space and time required
by that algorithm.

Efficiency of an Algorithm:

Efficiency of an algorithm can be analyzed at two different stages, before implementation

and after implementation. They are the following −

A Priori Analysis (Performance Analysis) − this is a theoretical analysis of an algorithm.

Efficiency of an algorithm is measured by assuming that all other factors, for example, processor
speed, are constant and have no effect on the implementation.

A Posterior Analysis (Performance Measurement) − this is an empirical analysis of an

algorithm. The selected algorithm is implemented using programming language. This is then
executed on target computer machine. In this analysis, actual statistics like running time and
space required, are collected.

PERFORMANCE ANALYSIS CALCULATION:

When we have multiple algorithms to solve a problem, we need to select a suitable

algorithm to solve that problem. We compare algorithms with each other which are solving the
same problem, to select the best algorithm. To compare algorithms, we use a set of parameters
or set of elements like memory required by that algorithm, the execution speed of that algorithm,
easy to understand, easy to implement, etc.

When we want to analyze an algorithm, we consider two important factors i.e. space
complexity and time complexity.

Space Complexity: Space Complexity of an algorithm represents the amount of memory

space required by the algorithm in its life cycle.

Time Complexity: Time Complexity of an algorithm represents the amount of time

required by the algorithm to run to completion.

ALGORITHM COMPLEXITY:

SPACE COMPLEXITY:
When we design an algorithm to solve a problem, it needs some computer memory to complete
its execution. For any algorithm, memory is required for the following purposes...

1. To store program instructions.

2. To store constant values.
3. To store variable values.
 4. And for few other things like function calls, jumping statements etc.

Space complexity of an algorithm can be defined as follows...

Total amount of computer memory required by an algorithm to complete its execution is
called as space complexity of that algorithm.
Generally, when a program is under execution it uses the computer memory for THREE
reasons. They are as follows...
Instruction Space: It is the amount of memory used to store compiled version of instructions.

1. Environmental Stack: It is the amount of memory used to store information of partially

executed functions at the time of function call.
2. Data Space: It is the amount of memory used to store all the variables and constants.

Note - When we want to perform analysis of an algorithm based on its Space complexity, we
consider only Data Space and ignore Instruction Space as well as Environmental Stack.
That means we calculate only the memory required to store Variables, Constants, Structures, etc.

To calculate the space complexity, we must know the memory required to store different
datatype values (according to the compiler). For example, the C++ Programming Language
compiler requires the following...

1. 4 bytes to store Integer value.

2. 4 bytes to store Floating Point value.
3. 1 byte to store Character value.
4. 8 bytes to store double value.

Consider the following piece of code...

Example 1
int square(int a)
{
return a*a;
}

In the above piece of code, it requires 4 bytes of memory to store variable 'a' and another
4 bytes of memory is used for return value.
That means, totally it requires 8 bytes of memory to complete its execution. And this 8
bytes of memory is fixed for any input value of 'a'. This space complexity is said to be Constant
Space Complexity.
If any algorithm requires a fixed amount of space for all input values then that space
complexity is said to be Constant Space Complexity.

Consider the following piece of code...

Example 2
int sum(int A[ ], int n)
{
int sum = 0, i;
for(i = 0; i < n; i++)
sum = sum + A[i];
return sum;
}
In the above piece of code it requires:
'n*4' bytes of memory to store array variable 'a[ ]'
4 bytes of memory for integer parameter 'n'
8 bytes of memory for local integer variables 'sum' and 'i' (4 bytes each)
4 bytes of memory for return value.
That means, totally it requires '4n+16' bytes of memory to complete its execution. Here,
the total amount of memory required depends on the value of 'n'. As 'n' value increases the space
required also increases proportionately. This type of space complexity is said to be Linear Space
Complexity.
If the amount of space required by an algorithm is increased with the increase of input value,
then that space complexity is said to be Linear Space Complexity.

TIME COMPLEXITY:
Every algorithm requires some amount of computer time to execute its instruction to
perform the task. This computer time required is called time complexity.

The time complexity of an algorithm can be defined as follows...

The time complexity of an algorithm is the total amount of time required by an algorithm to
complete its execution.

Generally, the running time of an algorithm depends upon the following...

1. Whether it is running on Single processor machine or Multi processor machine.
2. Whether it is a 32 bit machine or 64 bit machine.
3. Read and Write speed of the machine.
4. The amount of time required by an algorithm to perform Arithmetic operations, logical
operations, return value and assignment operations etc.,

5. Input data.

Note - When we calculate time complexity of an algorithm, we consider only input data and
ignore the remaining things, as they are machine dependent. We check only, how our program
is behaving for the different input values to perform all the operations like Arithmetic, Logical,
Return value and Assignment etc.,

Calculating Time Complexity of an algorithm based on the system configuration is a very

difficult task because the configuration changes from one system to another system. To solve
this problem, we must assume a model machine with a specific configuration. So that, we can
able to calculate generalized time complexity according to that model machine.

To calculate the time complexity of an algorithm, we need to define a model machine. Let us
assume a machine with following configuration...

1. It is a Single processor machine

2. It is a 32 bit Operating System machine
3. It performs sequential execution
4. It requires 1 unit of time for Arithmetic and Logical operations
5. It requires 1 unit of time for Assignment and Return value
6. It requires 1 unit of time for Read and Write operations

Now, we calculate the time complexity of following example code by using the above-defined
model machine...

Consider the following piece of code...

Example 1
int sum(int a, int b)
{
return a+b;
}

In the above sample code, it requires 1 unit of time to calculate a+b and 1 unit of time
to return the value. That means, totally it takes 2 units of time to complete its execution. And it
does not change based on the input values of a and b. That means for all input values, it require
the same amount of time i.e. 2 units.

If any program requires a fixed amount of time for all input values then its time complexity is
said to be Constant Time Complexity.

Consider the following piece of code...

Example 2
int sum(int A[], int n)
{
int sum = 0, i;
for(i = 0; i < n; i++)
sum = sum + A[i];
return sum;
}

For the above code, time complexity can be calculated as follows...

In above calculation
Cost is the amount of computer time required for a single operation in each line.
Repetition is the amount of computer time required by each operation for all its repetitions.
Total is the amount of computer time required by each operation to execute.
So above code requires '4n+4' Units of computer time to complete the task. Here the
exact time is not fixed. And it changes based on the n value. If we increase the n value then the
time required also increases linearly.

Totally it takes '4n+4' units of time to complete its execution and it is Linear Time
Complexity.

If the amount of time required by an algorithm is increased with the increase of input value
then that time complexity is said to be Linear Time Complexity.
 ASYMPTOTIC NOTATIONS:
Whenever we want to perform analysis of an algorithm, we need to calculate the
complexity of that algorithm. But when we calculate the complexity of an algorithm it does not
provide the exact amount of resource required. So instead of taking the exact amount of
resource, we represent that complexity in a general form (Notation) which produces the basic
nature of that algorithm. We use that general form (Notation) for analysis process.
Asymptotic notation of an algorithm is a mathematical representation of its complexity.
Note - In asymptotic notation, when we want to represent the complexity of an algorithm, we
use only the most significant terms in the complexity of that algorithm and ignore least significant
terms in the complexity of that algorithm (Here complexity can be Space Complexity or Time
Complexity).
For example, consider the following time complexities of two algorithms...

• Algorithm 1 : 5n2 + 2n + 1
• Algorithm 2 : 10n2 + 8n + 3

Generally, when we analyze an algorithm, we consider the time complexity for larger values
of input data (i.e. 'n' value). In above two time complexities, for larger value of 'n' the term '2n +
1' in algorithm 1 has least significance than the term '5n2', and the term '8n + 3' in algorithm 2
has least significance than the term '10n2'.
Here, for larger value of 'n' the value of most significant terms ( 5n2 and 10n2 ) is very larger
than the value of least significant terms ( 2n + 1 and 8n + 3 ). So for larger value of 'n' we ignore
the least significant terms to represent overall time required by an algorithm. In asymptotic
notation, we use only the most significant terms to represent the time complexity of an
algorithm.

Majorly, we use THREE types of Asymptotic Notations and those are as follows...

1. Big - Oh (O)
2. Big - Omega (Ω)
3. Big - Theta (Θ)

Big - Oh Notation (O)

Big - Oh notation is used to define the upper bound of an algorithm in terms of Time
Complexity.
That means Big - Oh notation always indicates the maximum time required by an
algorithm for all input values. That means Big - Oh notation describes the worst case of an
algorithm time complexity.
Big - Oh Notation can be defined as follows...
Consider function f(n) as time complexity of an algorithm and g(n) is the most
significant term.
If f(n) <= C g(n) for all n >= n0, C > 0 and n0 >= 1.
Then we can represent f(n) as O(g(n)).
f(n) = O(g(n))
Consider the following graph drawn for the values of f(n) and C g(n) for input (n) value on
X-Axis and time required is on Y-Axis.
 In above graph after a particular input value n0, always C*g(n) is greater than f(n) which
indicates the algorithm's upper bound.
Example
Consider the following f(n) and g(n)...
f(n) = 3n + 2
g(n) = n
If we want to represent f(n) as O(g(n)) then it must satisfy f(n) <= C g(n) for all values of C
> 0 and n0>= 1
f(n) <= C g(n)
⇒3n + 2 <= C n
Above condition is always TRUE for all values of C = 4 and n >= 2.
By using Big - Oh notation we can represent the time complexity as follows...
3n + 2 = O(n)

Big - Omege Notation (Ω)

Big - Omega notation is used to define the lower bound of an algorithm in terms of Time
Complexity.
That means Big-Omega notation always indicates the minimum time required by an
algorithm for all input values. That means Big-Omega notation describes the best case of an
algorithm time complexity.
Big - Omega Notation can be defined as follows...
Consider function f(n) as time complexity of an algorithm and g(n) is the most
significant term.
If f(n) >= C g(n) for all n >= n0, C > 0 and n0 >= 1.
Then we can represent f(n) as Ω(g(n)).
f(n) = Ω(g(n))
Consider the following graph drawn for the values of f(n) and C g(n) for input (n) value on
X-Axis and time required is on Y-Axis.
 In above graph after a particular input value n 0, always C g(n) is less than f(n) which
indicates the algorithm's lower bound.
Example
Consider the following f(n) and g(n)...
f(n) = 3n + 2
g(n) = n
If we want to represent f(n) as Ω(g(n)) then it must satisfy f(n) >= C g(n) for all values
of C > 0 and n0>= 1
f(n) >= C g(n)
⇒3n + 2 >= C n
Above condition is always TRUE for all values of C = 1 and n >= 1.
By using Big - Omega notation we can represent the time complexity as follows...
3n + 2 = Ω(n)

Big - Theta Notation (Θ)

Big - Theta notation is used to define the average bound of an algorithm in terms of Time
Complexity.
That means Big - Theta notation always indicates the average time required by an
algorithm for all input values. That means Big - Theta notation describes the average case of an
algorithm time complexity.
Big - Theta Notation can be defined as follows...
Consider function f(n) as time complexity of an algorithm and g(n) is the most
significant term.
If C1 g(n) <= f(n) <= C2 g(n) for all n >= n0, C1 > 0, C2 > 0 and n0 >= 1.
Then we can represent f(n) as Θ(g(n)).
f(n) = Θ(g(n))
Consider the following graph drawn for the values of f(n) and C g(n) for input (n) value on
X-Axis and time required is on Y-Axis.
 In above graph after a particular input value n0, always C1 g(n) is less than f(n) and C2 g(n)
is greater than f(n) which indicates the algorithm's average bound.
Example
Consider the following f(n) and g(n)...
f(n) = 3n + 2
g(n) = n
If we want to represent f(n) as Θ(g(n)) then it must satisfy C1 g(n) <= f(n) <= C2 g(n) for all
values of C1 > 0, C2 > 0 and n0>= 1
C1 g(n) <= f(n) <= C2 g(n)
⇒ C1 n <= 3n + 2 <= C2 n
Above condition is always TRUE for all values of C1 = 1, C2 = 4 and n >= 2.
By using Big - Theta notation we can represent the time complexity as follows...
3n + 2 = Θ(n)
 STATIC DATA STRUCTURES:

ARRAY OPERATIONS WITH MEMORY REPRESENTATION:

Array: An Array is a linear data structure which is a finite collection of items of similar
data-types stored in successive or consecutive or contiguous (next to each other) memory
locations.

Arrays can be declared in various ways in different languages. For illustration, let's take
C++ array declaration:

As per the above illustration, following are the important points to be considered.
• Index starts with 0.
• Array length is 10 which means it can store 10 elements.
• Each element can be accessed via its index. For example, we can fetch an element at
index 6 as : array[6];
BASIC OPERATIONS WITH ARRAYS: MEMORY REPRESENTATION OF ARRAYS:
Following are the basic operations supported by an array.
• Traverse − print all the array elements one by one.
• Insertion − Adds an element at the given index.
• Deletion − Deletes an element at the given index.
• Search − Searches an element using the given index or by the value.
• Update − Updates an element at the given index.
MEMORY REPRESENTATION OF ARRAYS:

Following are some representations of arrays in memory (RAM).

STACK:

Stack: Stack is a linear data structure which follows a particular order in which the
operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out).

There are many real-life examples of a stack. Consider an example of plates or deck of
cards stacked over one another. It is named as stack because it behaves like a real-world stack.

A real-world stack allows operations at one end only. For example, we can place or
remove a card or plate from the top of the stack only. Likewise, Stack Data Structure allows all
data operations at one end only. At any given time, we can only access the top element of a
stack.
This feature makes it LIFO or FILO data structure. LIFO stands for Last-in-first-out, FILO
stands for First-In-Last-Out while. Here, the element which is placed (inserted or added) last, is
accessed first. In stack terminology, insertion operation is called PUSH operation and removal
operation is called POP operation

STACK REPRESENTATION:
The following diagram depicts a stack and its operations –
 A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack
can either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to
implement stack using arrays, which makes it a fixed size stack implementation.

BASIC OPERATIONS:

Stack operations may involve initializing the stack, using it and then de-initializing it. Apart
from these basic stuffs, a stack is used for the following two primary operations −
• push() − Pushing (storing) an element on the top of stack.
• pop() − Removing (accessing) an element from the top of stack.
When data is PUSHed onto stack.
To use a stack efficiently, we need to check the status of stack as well. For the same purpose,
the following functionality is added to stacks −
• peek() / top() − get the top data element of the stack, without removing it.
• isFull() − check if stack is full.
• isEmpty() − check if stack is empty.
At all times, we maintain a pointer to the last PUSHed data on the stack. As this pointer
always represents the top of the stack, hence named top. The top pointer provides top value
of the stack without actually removing it.
First we should learn about procedures to support stack functions –
PEEK() / TOP():
Algorithm of peek() / top() function −
begin procedure peek
return stack[top]
end procedure
Implementation of peek() function in C++ programming language −
Example

int peek() {
return stack[top];
}
ISFULL():
Algorithm of isfull() function −

begin procedure isfull

if top equals to MAXSIZE - 1

return true
else
return false
endif

end procedure
Implementation of isfull() function in C++ programming language −
Example

bool isfull() {
if(top == MAXSIZE - 1)
return true;
else
return false;
}

ISEMPTY():
Algorithm of isempty() function −

begin procedure isempty

if top is less than zero

return true
else
return false
endif

end procedure
Here's the C++ code −
Example

bool isempty() {
if(top < 0)
return true;
else
return false;
}

PUSH OPERATION:

The process of putting a new data element onto stack is known as a Push Operation. Push
operation involves a series of steps −
• Step 1 − Checks if the stack is full.
• Step 2 − If the stack is full, produces an error and exit.
• Step 3 − If the stack is not full, increments top to point next empty space.
 • Step 4 − Adds data element to the stack location, where top is pointing.
• Step 5 − Returns success.

If the linked list is used to implement the stack, then in step 3, we need to allocate space
dynamically.
Algorithm for PUSH Operation
A simple algorithm for Push operation can be derived as follows −

begin procedure push: stack, data

if stack is full
return null
endif

top ← top + 1
stack[top] ← data

end procedure
Implementation of this algorithm in C++, is very easy. See the following code −
Example

void push(int data) {

if(!isFull()) {
top = top + 1;
stack[top] = data;
} else {
cout << "Could not insert data, Stack is full.\n";
}
}

POP OPERATION:

Accessing the content while removing it from the stack, is known as a Pop Operation. In
an array implementation of pop() operation, the data element is not actually removed,
instead top is decremented to a lower position in the stack to point to the next value. But in
linked-list implementation, pop() actually removes data element and deallocates memory
space.
A Pop operation may involve the following steps −
• Step 1 − Checks if the stack is empty.
• Step 2 − If the stack is empty, produces an error and exit.
• Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
 • Step 4 − Decreases the value of top by 1.
• Step 5 − Returns success.

Algorithm for Pop Operation

A simple algorithm for Pop operation can be derived as follows −

begin procedure pop: stack

if stack is empty
return null
endif

data ← stack[top]
top ← top - 1
return data

end procedure
Implementation of this algorithm in C, is as follows −
Example

int pop() {
int data;
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
cout << "Could not retrieve data, Stack is empty.\n";
}
}

NOTE: Complete program shared in separate file.

QUEUES:

Queue: Like Stack, Queue is a linear structure which follows a particular order in which
the operations are performed. The order is First In First Out (FIFO) , i.e., the data item stored first
will be accessed first. Unlike stacks, a queue is open at both its ends (operations can be
performed at both ends). One end (rear) is always used to insert data (enqueue) and the other
(front) is used to remove data (dequeue).

EXAMPLES:

• Any queue of consumers for a in a departmental store, airport etc. where the
consumer that came first is served first.
• Another real-world example of queue can be a single-lane one-way road, where
the vehicle which enters first, exits first.

• More real-world examples can be seen as queues at the ticket windows and bus-
stops.
• CPU scheduling, Disk Scheduling.
• When data is transferred asynchronously between two processes.
• Queue is used for synchronization. e.g: IO Buffers, pipes, file IO, etc.
• Handling of interrupts in real-time systems.
• Call Center phone systems uses Queues to hold people calling them in an order.

The difference between stacks and queues is in removing. In a stack we remove the
item the most recently added; in a queue, we remove the item the least recently added.

QUEUE REPRESENTATION:

As we now understand that in queue, we access both ends for different reasons. The
following diagram given below tries to explain queue representation as data structure −

As in stacks, a queue can also be implemented using Arrays, Linked-lists, Pointers and
Structures. For the sake of simplicity, we shall implement queues using one-dimensional array.

BASIC OPERATIONS:

Queue operations may involve initializing or defining the queue, utilizing it, and then
completely erasing it from the memory. Here we shall try to understand the basic operations
associated with queues −
• enqueue() − add (store) an item to the queue.
 • dequeue() − remove (access) an item from the queue.
Few more functions are required to make the above-mentioned queue operation efficient.
These are −
• peek() / front() − Gets the element at the front of the queue without removing it.
• isfull() − Checks if the queue is full.
• isempty() − Checks if the queue is empty.
In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing
(or storing) data in the queue we take help of rear pointer.
Let's first learn about supportive functions of a queue −
PEEK():
This function helps to see the data at the front of the queue. The algorithm of peek()
function is as follows −
Algorithm
begin procedure peek
if queue is empty
display error msg
else
return queue[front]
end procedure
Implementation of peek() function in C++ programming language −
Example

int peek()
{
if(isEmpty() == true)
{
cout << "\n====>ERROR! Could not FRONT VALUE<====\n";
cout << "......Queue is Empty.....\n";
}
else
{
return Q[front_index];
}

ISFULL():
As we are using single dimension array to implement queue, we just check for the rear
pointer to reach at MAXSIZE to determine that the queue is full. In case we maintain the queue
in a circular linked-list, the algorithm will differ. Algorithm of isfull() function −
Algorithm

begin procedure isfull

if rear equals to MAXSIZE - 1

return true
else
return false
endif

end procedure
Implementation of isfull() function in C++ programming language −
Example

bool isFull()
{
if(rear_index == MAX_SIZE - 1)
{
return true;
}
else
{
return false;
}
}

ISEMPTY():
Algorithm of isempty() function −
Algorithm

begin procedure isempty

if front is equal to -1 AND rear is equal to -1

return true
else
return false
endif

end procedure
If the value of both front and rear is equal to -1, it tells that the queue is not yet initialized, hence
empty.
Here's the C++ programming code −
Example

bool isEmpty()
{
if(front_index == -1 && rear_index == -1)
{
return true;
}
else
{
return false;
}
}

ENQUEUE OPERATION:

Queues maintain two data pointers, front and rear. Therefore, its operations are
comparatively difficult to implement than that of stacks.
The following steps should be taken to enqueue (insert) data into a queue −
• Step 1 − Check if the queue is full.
• Step 2 − If the queue is full, produce overflow error and exit.
• Step 3 − If the queue is not full, increment rear pointer to point the next empty space.
 • Step 4 − Add data element to the queue location, where the rear is pointing.
• Step 5 − return success.

Sometimes, we also check to see if a queue is initialized or not, to handle any unforeseen
situations.
Algorithm for enqueue operation
procedure enqueue(data)
if queue is empty
rear  front  0
q[rear]  data
if queue is full
error msg

else
rear ← rear + 1
queue[rear] ← data
endif

end procedure
Implementation of enqueue() in C++ programming language −
Example

void enqueue(int value)

{
cout<<"Enqueuing "<< value <<" \n";

// Empty Case
if (isEmpty() == true)
{
front_index = 0;
rear_index = 0;
Q[rear_index] = value;
}
// Full Case
else if(isFull() == true)
{
cout << "\n====>ERROR! Could not Insert Data<====\n";
cout << "......Queue is Full.....\n";
}
// In Between Case
else
{
rear_index++;
 Q[rear_index] = value;
}
}

DEQUEUE OPERATION:

Accessing data from the queue is a process of two tasks − access the data where front is
pointing and remove the data after access. The following steps are taken to
perform dequeue operation −
• Step 1 − Check if the queue is empty.
• Step 2 − If the queue is empty, produce underflow error and exit.
• Step 3 − If the queue is not empty, access the data where front is pointing.
• Step 4 − Increment front pointer to point to the next available data element.
• Step 5 − Return success.

Algorithm for dequeue operation

procedure dequeue

if queue is empty
error msg
else if rear == front
data = q[front]
rear  front  -1
else
data = q[front]
front ← front + 1
return data

end procedure
Implementation of dequeue() in C programming language −
Example

int dequeue()
{
cout<<"Dequeuing \n";

int q_data;

// Empty Case
if(isEmpty())
{
cout << "\n====>ERROR! Could not Get Data<====\n";
cout << "......Queue is Empty.....\n";
 }
// Only ONE ELEMENT in Queue
else if(front_index == rear_index)
{
q_data = Q[front_index];
rear_index = -1;
front_index = -1;
}
// More than ONE Elements
else
{
q_data = Q[front_index];
front_index++;
}
return q_data;
}

NOTE: Complete program shared in separate file.

A BIG PROBLEM WITH ABOVE QUEUE:

Let’s take an example that we have a queue as:
0 1 2 3 4 0 1 2 3 4
12345 ➔ --  --  --  4  5
front = 0 , rear = 4 front = 3 , rear = 4
(after dequeuing 3 elements)
In the above implementation the problem is that, we will not be able to use the space
emptied in the queue that is left of front pointer in this case.

SOLUTION? Ans = Circular Queue

CHANGES IN ABOVE CODE (CIRCULAR QUEUE):

1) isFull():
Just replace:
if(rear_index == MAX_SIZE - 1)

with:
if((rear_index + 1) % MAX_SIZE == front_index)

2) enqueue():
In the last else condition, Just replace:
rear_index++;

with:
rear_index = (rear_index + 1) % MAX_SIZE;

3) dequeue():
In the last else condition, Just replace:
front_index++;

with:
front_index = (front_index + 1) % MAX_SIZE;

4) displayQueue():
 There will be changes in this method as well, but display is not a
functionality of a queue. It is just a checking process.

Code will be shared in separate file.

PRIORITY QUEUE:

Priority Queue: A Priority Queue is a data structure in which each element is assigned a
priority. The priority of the element will be used to determine the order in which the elements
will be processed.

The general rules for processing the elements of a priority queue are:
1) An element/item with higher priority will be processed before an element with lower
priority.
2) Two elements with same priority are processed on a FCFS (First Come First Serve) basis.

Below is a diagram about how priority queue works.

APPLICATIONS OF PRIORITY QUEUE:

1) CPU Scheduling
2) Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree, etc
3) All queue applications where priority is involved.
INSERTION OPERATION:

RECURSION:

The process of solving a problem by reducing it to smaller versions of itself is called

recursion. Recursion is a very powerful way to solve certain problems for which the
solution would otherwise be very complicated.

Recursive definition: A definition in which something is defined in terms of a smaller

version of itself.

The concept of recursion in computer science works similarly. Here, we talk about
recursive algorithms and recursive functions. An algorithm that finds the solution to a given
problem by reducing the problem to smaller versions of itself is called a recursive algorithm. The
recursive algorithm must have one or more base cases, and the general solution must
eventually be reduced to a base case.

A function that calls itself is called a recursive function. That is, the body of the
recursive function contains a statement that causes the same function to execute again
before completing the current call. Recursive algorithms are implemented using recursive
functions.

Recursion: Recursion is the process in which a function calls itself.

PROPERTIES:
There are two properties that a recursive function must have −

• Base criteria − There must be at least one base criteria or condition, such that, when this
condition is met the function stops calling itself recursively.

• Progressive approach − The recursive calls should progress in such a way that each time
a recursive call is made it comes closer to the base criteria.

• The general case must eventually be reduced to a base case.

• The base case stops the recursion.

IMPLEMENTATION:
Many programming languages implement recursion by means of stacks. Generally,
whenever a function (caller) calls another function (callee) or itself as callee, the caller function
transfers execution control to the callee. This transfer process may also involve some data to be
passed from the caller to the callee.

This implies, the caller function has to suspend its execution temporarily and resume later
when the execution control returns from the callee function. Here, the caller function needs to
start exactly from the point of execution where it puts itself on hold. It also needs the exact same
data values it was working on. For this purpose, an activation record (or stack frame) is created
for the caller function.

This activation record keeps the information about local variables, formal parameters,
return address and all information passed to the caller function.
 Example:

TYPES OF RECURSION:

There are two types of recursion.

a. Direct Recursion.
b. Indirect Recursion.

Direct Recursion: in Direct Recursion, a function calls itself directly. For Example, A
function fun is called direct recursive if it calls itself.
Indirect Recursion: in Indirect Recursion, a function calls another function and the
function calls back the previous function again. For Example, A function fun1 is called indirect
recursive if it calls another function say fun2 and fun2 calls fun1 directly or indirectly.
// An example of direct recursion
void directRecFun()
{
// Some code....
directRecFun();
// Some code...
}

// An example of indirect recursion

void indirectRecFun1()
{
// Some code...
indirectRecFun2();
// Some code...
}
void indirectRecFun2()
{
// Some code...
indirectRecFun1();
// Some code...
}
EXAMPLE-1:

Factorial of a number: Suppose we want to find the factorial of a number 6.

C++ Program (Without Recursion):

#include <iostream>
using namespace std;

int main()
{
int num = 6, factorial = 1;

for (int i=1 ; i<=num; i++)

{
factorial = factorial * i;
}
cout<<"Factorial of " << num << " is = " << factorial << endl;

return 0;
}

Mathematically, we can break down 6! In the form of simple sub cases as:

6! = 6.5! = n.(n-1)! , where n = 6 (general case) Top

5! = 5.4! = n.(n-1)! , where n = 5 // ↓
4! = 4.3! = n.(n-1)! , where n = 4 // ↓
3! = 3.2! = n.(n-1)! , where n = 3 // ↓
2! = 2.1! = n.(n-1)! , where n = 2 // ↓
1! = 1 = 1 , where n = 1 (Base Case) Bottom

Here, we have two different cases, the base case and the general cases. We can say that
we have divided our problem in a top-to-bottom (Divide and Conquer) approach. At the top
level, we have general cases and then moving down till the end which is our Base Case that ends
the division. So, we can simplify our program by writing a recursive function of the above stated
cases. Below is the recursive function:

int factorial(int num)

{
if (num == 1)
{
return 1;
}
else
{ // n * (n-1)!
return num * factorial(num-1);
}
}

C++ Program (Using Recursion):

#include <iostream>

using namespace std;

 int factorial(int num)
{
if (num == 1)
{
return 1;
}
else
{
return num * factorial(num-1);
}
}
int main()
{
int num = 6;
int fact = factorial(num);
cout<<"Factorial of " << num << " is = " << fact << endl;

return 0;
}

We can understand above code by using a diagram as:

Example-2:

Power of a number: Suppose we want to find the power of a number, let’s say 3 ^ 5.

C++ Program (Without Recursion):

#include <iostream>

using namespace std;

int main()
{
int num = 3, pow = 5, result = 1;

for(int i = 1 ; i<=pow ; i++)

{
result = result * num;
}
 cout << num << " ^ " << pow << " = " << result << endl;
return 0;
}

Mathematically, we can break down 3 ^ 5 in the form of simple sub cases as:

3^5 = 3.3^4 = n.(n^(pow-1)) , where n = 3, pow = 5 (general case) Top

3^4 = 3.3^3 = n.(n^(pow-1)) , where n = 3, pow = 4 // ↓
3^3 = 3.3^2 = n.(n^(pow-1)) , where n = 3, pow = 3 // ↓
3^2 = 3.3^1 = n.(n^(pow-1)) , where n = 3, pow = 2 // ↓
3^1 = 3.3^0 = n.(n^(pow-1)) , where n = 3, pow = 1 // ↓
3^0 = 1 = 1 , where n = 3, pow = 0 (Base Case) Bottom

Below is the recursive function:

int power(int base , int pow)

{
if (pow == 0)
{
return 1;
}
else
{ // n * n ^ (pow -1)
return (base * power(base , pow - 1));
}
}
C++ Program Using Recursion:

#include <iostream>
using namespace std;

int power(int base , int pow)

{
if (pow == 0)
{
return 1;
}
else
{
return (base * power(base , pow - 1));
}
}

int main()
{
int num = 3, pow = 5, result = 1;

result = power(num,pow);
cout << num << " ^ " << pow << " = " << result << endl;
return 0;
}
 SEARCHING AND SORTING:

SEARCHING ALGORITHMS:
1) LINEAR SEARCH:

Linear search is the simplest searching algorithm that searches for an element in a list
in sequential order. We start at one end and check every element until the desired element is
not found.

How Linear Search Works?

The following steps are followed to search for an element k = 1 in the list below.

1. Start from the first element, compare k with each element x.

2. If x == k, return the index.

3. Else, return not found.

PROGRAM: in code file.

2) BINARY SEARCH:

Binary Search is a searching algorithm for finding an element's position in a sorted array. In
this approach, the element is always searched in the middle of a portion of an array. Binary
search can be implemented only on a sorted list of items. If the elements are not sorted already,
we need to sort them first.

Binary Search Working:

Binary Search Algorithm can be implemented in two ways which are discussed below.
1. Iterative Method
2. Recursive Method
The recursive method follows the divide and conquer approach.

The general steps for both methods are discussed below.

1. The array in which searching is to be performed is:

Let x = 4 be the element to be searched.

2. Set two pointers low and high at the lowest and the highest positions respectively.

3. Find the middle element mid of the array ie. (arr[low + high]) / 2 = 6.
4. If x == mid, then return mid.
Else, compare the element to be searched with m.

5. If x > mid, compare x with the middle element of the elements on the right side of mid.
This is done by setting low to low = mid + 1.
6. Else, compare x with the middle element of the elements on the left side of mid.
This is done by setting high to high = mid - 1.

7. Repeat steps 3 to 6 until low meets high.

8. x = 4 is found.

PROGRAM FOR BOTH: in code file.

 SORTING ALGORITHMS:

DIVIDE AND CONQUER APPROACH:

A divide and conquer algorithm is a strategy of solving a large problem by

1. breaking the problem into smaller sub-problems

2. solving the sub-problems, and

3. combining them to get the desired output.

To use divide and conquer algorithms, recursion is used.

How Divide and Conquer Algorithms Work?

Here are the steps involved:

1. Divide: Divide the given problem into sub-problems using recursion.

2. Conquer: Solve the smaller sub-problems recursively. If the sub-problem is small enough,
then solve it directly.

3. Combine: Combine the solutions of the sub-problems which is part of the recursive
process to get the solution to the actual problem.

Let us understand this concept with the help of an example.

Here, we are going to sort an array using the divide and conquer approach (ie. merge sort).

1. Let the given array be:

2. Divide the array into two halves.

Again, divide each subpart recursively into two halves until you get individual elements.

3. Now, combine the individual elements in a sorted manner.

Here, conquer and combine steps go side by side.
1) SELECTION SORT:
Selection sort is an algorithm that selects the smallest element from an unsorted list in
each iteration and places that element at the beginning of the unsorted list.

How Selection Sort Works?

1. Set the first element as minimum.

2. Compare minimum with the second element. If the second element is smaller
than minimum, assign the second element as minimum.

Compare minimum with the third element. Again, if the third element is smaller, then
assign minimum to the third element otherwise do nothing. The process goes on until
the last element.

3. After each iteration, minimum is placed in the front of the unsorted list.
4. For each iteration, indexing starts from the first unsorted element. Step 1 to 3 are
repeated until all the elements are placed at their correct positions.
PROGRAM: in code file.
2) INSERTION SORT:

Insertion sort works similarly as we sort cards in our hand in a card game.

We assume that the first card is already sorted then, we select an unsorted card. If the
unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In
the same way, other unsorted cards are taken and put at their right place.
 A similar approach is used by insertion sort. Insertion sort is a sorting algorithm that places
an unsorted element at its suitable place in each iteration.

How Insertion Sort Works?

Suppose we need to sort the following array.

1. The first element in the array is assumed to be sorted. Take the second element and store it
separately in key.

Compare key with the first element. If the first element is greater than key, then key is placed
in front of the first element.

2. Now, the first two elements are sorted.

Take the third element and compare it with the elements on the left of it. Placed it just behind
the element smaller than it. If there is no element smaller than it, then place it at the
beginning of the array.
3. Similarly, place every unsorted element at its correct position.

4. Finally, we have:
PROGRAM: in code file.
3) BUBBLE SORT:

Bubble sort is an algorithm that compares the adjacent elements and swaps their positions
if they are not in the intended order. The order can be ascending or descending.

How Bubble Sort Works?

1. Starting from the first index, compare the first and the second elements. If the first element
is greater than the second element, they are swapped.

Now, compare the second and the third elements. Swap them if they are not in order.

The above process goes on until the last element.

2. The same process goes on for the remaining iterations. After each iteration, the largest
element among the unsorted elements is placed at the end.

In each iteration, the comparison takes place up to the last unsorted element.

The array is sorted when all the unsorted elements are placed at their correct positions.
PROGRAM: in code file.
4) QUICK SORT:

Quick sort is a highly efficient sorting algorithm based on divide and conquer approach and
is also based on partitioning of array of data into smaller arrays. A large array is partitioned into
two arrays one of which holds values smaller than the specified value, say pivot, based on which
the partition is made and another array holds values greater than the pivot value.
Quicksort partitions an array and then calls itself recursively twice to sort the two resulting
subarrays.
How QuickSort Works?
1. A pivot element is chosen from the array. You can choose any element from the array as the
pivot element.
Here, we have taken the rightmost (i.e. the last element) of the array as the pivot
element.
2. The elements smaller than the pivot element are put on the left and the elements greater
than the pivot element are put on the right.

The above arrangement is achieved by the following steps.

a. A pointer is fixed at the pivot element. The pivot element is compared with the elements
beginning from the low index using ‘j’ pointer. If the element greater than the pivot
element is reached, a second pointer ‘I’ pointer is set for that element.

b. Now, the pivot element is compared with the other elements (a third pointer). If an
element smaller than the pivot element is reached, the smaller element is swapped with
the greater element found earlier.
 c. The process goes on until the second last element is reached.
Finally, the pivot element is swapped with the second pointer.

3. Pivot elements are again chosen for the left and the right sub-parts separately. Within these
sub-parts, the pivot elements are placed at their right position. Then, step 2 is repeated.

4. The sub-parts are again divided into smaller sub-parts until each subpart is formed of a
single element.

5. At this point, the array is already sorted.

Quicksort uses recursion for sorting the sub-parts.
On the basis of Divide and conquer approach, quicksort algorithm can be explained as:

• Divide
The array is divided into subparts taking pivot as the partitioning point. The elements
smaller than the pivot are placed to the left of the pivot and the elements greater than
the pivot are placed to the right.

• Conquer
The left and the right subparts are again partitioned using the by selecting pivot elements
for them. This can be achieved by recursively passing the subparts into the algorithm.

• Combine
This step does not play a significant role in quicksort. The array is already sorted at the
end of the conquer step.

You can understand the working of quicksort with the help of the illustrations below.
PROGRAM: in code file.

5) MERGE SORT:
Merge Sort: Like Quick Sort, Merge Sort is also a Divide and Conquer algorithm. It is also
one of the most popular sorting algorithms.

Merge sort first divides the array into equal halves and then combines them in a sorted
manner.

The MergeSort Function:

The MergeSort function repeatedly divides the array into two halves until we reach a
stage where we try to perform MergeSort on a subarray of size 1 i.e. p == r.

After that, the merge function comes into play and combines the sorted arrays into
larger arrays until the whole array is merged.

MergeSort(A, low, high)

{
if low < high
{

mid = (low+high)/2

mergeSort(A, low, mid)

mergeSort(A, mid+1, high)

merge(A, low, mid, high)

}
}

The following diagram shows the complete merge sort process for an example array {38,
27, 43, 3, 9, 82, 10}. If we take a closer look at the diagram, we can see that the array is recursively
divided in two halves till the size becomes 1. Once the size becomes 1, the merge processes
comes into action and starts merging arrays back till the complete array is merged.
Merge Sort Diagram:

The Merge Function:

The merge step is the solution to the simple problem of merging two sorted lists(arrays)
to build one large sorted list(array).

The algorithm maintains three pointers, one for each of the two arrays and one for
maintaining the current index of the final sorted array.

Have we reached the end of any of the arrays?

No:

Compare current elements of both arrays

Copy smaller element into sorted array

Move pointer of element containing smaller element

Yes:

Copy all remaining elements of non-empty array

 A noticeable difference between the merging step we described above and the one we
use for merge sort is that we only perform the merge function on consecutive sub-arrays.

This is why we only need the array, the first position, the last index of the first subarray(we
can calculate the first index of the second subarray) and the last index of the second subarray.

Our task is to merge two subarrays A[p..q] and A[q+1..r] to create a sorted array A[p..r].
So the inputs to the function are A, p, q and r

The merge function works as follows:

1. Create copies of the subarrays L ← A[p..q] and M ← A[q+1..r].

2. Create three pointers i, j and k

a. i maintains current index of L, starting at 1

b. j maintains current index of M, starting at 1

c. k maintains the current index of A[p..q], starting at p.

3. Until we reach the end of either L or M, pick the larger among the elements
from L and M and place them in the correct position at A[p..q]

4. When we run out of elements in either L or M, pick up the remaining elements and put
in A[p..q]
Merge( ) Function Explained Step-By-Step

A lot is happening in this function, so let's take an example to see how this would work.

The array A[0..5] contains two sorted subarrays A[0..3] and A[4..5]. Let us see how the merge
function will merge the two arrays.

void merge(int arr[], int p, int q, int r) {

// Here, p = 0, q = 4, r = 5 (size of array)

Step 1: Create duplicate copies of sub-arrays to be sorted

// Create L ← A[p..q] and M ← A[q+1..r]

int n1 = q - p + 1 = 3 - 0 + 1 = 4;
int n2 = r - q = 5 - 3 = 2;

int L[4], M[2];

for (int i = 0; i < 4; i++)

L[i] = arr[p + i];
// L[0,1,2,3] = A[0,1,2,3] = [1,5,10,12]

for (int j = 0; j < 2; j++)

M[j] = arr[q + 1 + j];
// M[0,1,2,3] = A[4,5] = [6,9]

Step 2: Maintain current index of sub-arrays and main array

int i, j, k;
i = 0;
j = 0;
k = p;
Step 3: Until we reach the end of either L or M, pick larger among elements L and M and place
them in the correct position at A[p..r]

while (i < n1 && j < n2) {

if (L[i] <= M[j]) {
arr[k] = L[i]; i++;
}
else {
arr[k] = M[j];
j++;
}
k++;
}

Step 4: When we run out of elements in either L or M, pick up the remaining elements and put
in A[p..r]

// We exited the earlier loop because j < n2 doesn't hold

while (i < n1)
{
arr[k] = L[i];
i++;
 k++;
}

// We exited the earlier loop because i < n1 doesn't hold

while (j < n2)
{
arr[k] = M[j];
j++;
k++;
}
}

This step would have been needed if the size of M was greater than L. At the end of the
merge function, the subarray A[p..r] is sorted.

PROGRAM: in code file.

6) COUNTING SORT:
Counting Sort: Counting Sort is a sorting algorithm that does not use any sort of
comparison for sorting the elements. Because of this ability of this algorithm, it is even more
powerful and efficient than merge sort and quick sort in some situations.

For example, assume that we are asked to sort ‘n’ elements, but we are informed that
each element is in the range of (0—k), where ‘k’ is much smaller than ‘n’. Counting Sort
algorithm can take advantage of this situation and it can work better than quick sort and merge
sort algorithms. The algorithm was created by Harold H. Seward in 1954.

Counting sort is a sorting algorithm that sorts the elements of an array by counting the
number of occurrences of each unique element in the array. The count is stored in an auxiliary
array and the sorting is done by mapping the count as an index of the auxiliary array.

How Counting Sort Algorithm Works:

Counting sort algorithm uses three arrays for sorting values. These are:

1. A [1, n] is the initial input array.

2. B [1, n] is the sorted output array.
3. C [1, k] is a temporary array/count array that is used to perform very important
operations.

Where, n = total number of elements in input array and k = max value in input array.

EXPLANATION #1:

1. Let the initial array be, here k = 8:

2. Initialize count array of length ‘k’ with all elements 0. This array is used for storing the
count of the elements (i.e. how many times an element appears in the initial array) in
the array.

3. Store the count of each element at their respective index in count array.

For example: if the count of element 3 is 2 then, 2 is stored in the 3rd position
of count array. If element "5" is not present in the array, then 0 is stored in 5th position.

4. Store cumulative sum of the elements of the count array. It helps in placing the elements
into the correct index of the sorted array.
 5. Find the index of each element of the original array in the count array. This gives the
cumulative count. Place the element at the index calculated as shown in figure below.

6. After placing each element at its correct position, decrease its count by one.

EXPKLANATION #2:

Let us understand it with the help of another example.

For simplicity, consider the data in the range 0 to 9.
Input data: 1, 4, 1, 2, 7, 5, 2
1) Take a count array to store the count of each unique object.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 2 0 1 1 0 1 0 0

2) Modify the count array such that each element at each index
stores the sum of previous counts.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 4 4 5 6 6 7 7 7

The modified count array indicates the position of each object in

the output sequence.

3) Output each object from the input sequence followed by

decreasing its count by 1.
Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2.
Put data 1 at index 2 in output. Decrease count by 1 to place
next data 1 at an index 1 smaller than this index.
Counting Sort Algorithm

countingSort(array, size)

max <- find largest element in array

initialize count array with all zeros

for j <- 0 to size

find the total count of each unique element and

store the count at jth index in count array

for i <- 1 to max

find the cumulative sum and store it in count array itself

for j <- size down to 1

restore the elements to array

decrease count of each element restored by 1