SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

UNIT1

Data Structures:

Definition: Data Structure is a way to store and organize data so that it can be used efficiently.
(or) The data structure name indicates itself that organizing the data in memory.
What is Data Structure?
A data structure is a storage that is used to store and organize data. It is a way of arranging
data on a computer so that it can be accessed and updated efficiently.
A data structure is not only used for organizing the data. It is also used for processing,
retrieving, and storing data. There are different basic and advanced types of data structures that
are used in almost every program or software system that has been developed.
The data structure is not any programming language like C, C++, java, etc. It is a set of
algorithms that we can use in any programming language to structure the data in the memory.
To structure the data in memory, 'n' number of algorithms were proposed, and all these
algorithms are known as Abstract data types. These abstract data types are the set of rules.
AlgorithmsAbstract datatypes-Set of rules
Importance of Data Structures:
 Performance: Choosing the right data structure significantly impacts how quickly your
program can access and process information. For example, searching an unsorted list
takes much longer than searching a sorted array.
 Memory Management: Data structures help optimize memory usage, preventing wasted
space and improving program efficiency.
 Code Reusability: Well-defined data structures can be reused across different parts of
your program or even other programs, saving development time and promoting
consistency.
 Efficiency: Enhances performance by optimizing data operations, improving processing
speed, and reducing resource consumption.
 Abstraction: Allows users to focus on high-level concepts without worrying about
implementation details, enhancing ease of use and understanding.

Classification of Data Structures:

Types of Data Structures
There are two types of data structures:
o Primitive data structure
o Non Primitive Data structure
Primitive data structures:
o The primitive data structures are primitive data types. The int, char, float, double, and
pointer are the primitive data structures that can hold a single value.
Non Primitive Data structures:
The non-primitive data structure is divided into two types:
o 1.Linear data structure 2.Non-linear data structure

1
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

1.Linear Data Structures:

If a data structure organizes the data in sequential order, then that data structure is called a
Linear Data Structure. In these data structures, one element is connected to only one another
element in a linear form.
Example
1. Arrays
2. List (Linked List)
3. Stack
4. Queue

Linear Data structures can also be classified as:

o Static data structure: It is a type of data structure where the size is allocated at the
compile time. Therefore, the maximum size is fixed.
Ex: Arrays
o Dynamic data structure: It is a type of data structure where the size is allocated at the
run time. Therefore, the maximum size is flexible.
Ex: Stacks, Queues ,Lists

Non - Linear Data Structures

If a data structure organizes the data in random order, then that data structure is called as Non-
Linear Data Structure.

When one element is connected to the 'n' number of elements known as a non-linear data
structure.

Example
1. Tree
2. Graph
3. Dictionaries
4. Heaps
5. Tries, Etc.,

2
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Classification:

Array:
Array is a linear data structure that stores a collection of elements of the same data type.
Elements are allocated contiguous memory, allowing for constant-time access. Each element
has a unique index number.
Example: An array with each element represented by an index

Stack:
Stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Stacks play
an important role in managing function calls, memory, and are widely used in algorithms, web
development, and systems like compilers and browsers.

In a stack, operations can be perform only from one end (top here).

3
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Queue

Queue is a linear data structure that follows the First In, First Out (FIFO) principle. Queues
play an important role in managing tasks or data in order, scheduling and message handling
systems.

In a queue, addition and removal are performed from separate ends

Linked List

Linked list is a linear data structure that stores data in nodes, which are connected by pointers.
Unlike arrays, nodes of linked lists are not stored in contiguous memory locations and can only
be accessed sequentially, starting from the head of list.

Tree
Tree is a non-linear, hierarchical data structure consisting of nodes connected by edges, with a
top node called the root and nodes having child nodes. It is widely used in file
systems, databases, decision-making algorithms, etc.

Graph
Graph is a non-linear data structure consisting of a finite set of vertices(or nodes) and a set
of edges(or links)that connect a pair of nodes. Graphs are widely used to represent relationships
between entities.

4
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Abstract Data Types(ADTs) and their implementation

What is an Abstract Data Type (ADT) ?

An Abstract Data Type (ADT) is an abstraction of a data structure that defines the type of data it
can hold and the operations that can be performed on it without revealing the internal
implementation details.

In essence, ADTs define the “what” (the interface) without specifying the “how” (the
implementation). This separation of concerns is a fundamental concept in software engineering,
known as encapsulation.

ADTs are used to model and represent real-world entities and their behaviours within a
program. They provide a clean and organized way to structure data and operations, promoting
code reusability and maintainability. Examples of ADTs include lists, stacks, queues, trees, and
graphs.

The process of providing only the essentials and hiding the details is known as abstraction.

Abstract Data Type Model:

In the above figure, we can see the ADT model. There are two types of models in the ADT
model:

1. the public function

2. the private function
The ADT model also contains the data structures being used in a program. Here, at first,
encapsulation is performed, i.e., all the data is wrapped in a single unit, i.e., ADT. Afterwards,
abstraction is performed i.e. showing the operations that can be performed on the data structure
and also showcasing the data structures being used in a program.

5
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Types of Abstract Data Types (ADTs)

There are mainly three types of ADTs:

List ADT
Queue ADT
Stack ADT
1. List ADT

Lists are linear data structures stored in a non-continuous manner. The list is made up of a series
of connected nodes that are randomly stored in the memory. Here, each node consists of two
parts, the first part is the data and the second part contains the pointer to the address of the next
node.

The first node of a linked list is called the Head, and it acts as an access point. The head pointer
points to the first element of the linked list. The last node is called the Tail, and it marks the end
of a linked list by pointing to a NULL value.

 The data is generally stored in key sequence in a list which has a head structure
consisting of count, pointers and address of compare function needed to compare the data
in the list.
 The data node contains the pointer to a data structure and a self-referential pointer which
points to the next node in the list.
 The List ADT Functions is given below:
 get() – Return an element from the list at any given position.
 insert() – Insert an element at any position of the list.
 remove() – Remove the first occurrence of any element from a non-empty list.
 removeAt() – Remove the element at a specified location from a non-empty list.
 replace() – Replace an element at any position by another element.
 size() – Return the number of elements in the list.
 isEmpty() – Return true if the list is empty, otherwise return false.
 isFull() – Return true if the list is full, otherwise return false.
2.Stack ADT:
 In Stack ADT Implementation instead of data being stored in each node, the pointer to
data is stored.
 The program allocates memory for the data and address is passed to the stack ADT.
 The head node and the data nodes are encapsulated in the ADT. The calling function can
only see the pointer to the stack.
 The stack head structure also contains a pointer to top and count of number of entries
currently in stack.
6
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

 The Stack ADT Functions is given below:

 push() – Insert an element at one end of the stack called top.
 pop() – Remove and return the element at the top of the stack, if it is not empty.
 peek() – Return the element at the top of the stack without removing it, if the stack is not
empty.
 size() – Return the number of elements in the stack.
 isEmpty() – Return true if the stack is empty, otherwise return false.
 isFull() – Return true if the stack is full, otherwise return false.
3.Queue ADT:

 The queue abstract data type (ADT) follows the basic design of the stack abstract data
type.
 Each node contains a void pointer to the data and the link pointer to the next element in
the queue. The program’s responsibility is to allocate memory for storing the data.

 The Queue ADT Functions is given below:

 enqueue() – Insert an element at the end of the queue.
 dequeue() – Remove and return the first element of the queue, if the queue is not empty.
 peek() – Return the element of the queue without removing it, if the queue is not empty.
7
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

 size() – Return the number of elements in the queue.

 isEmpty() – Return true if the queue is empty, otherwise return false.
 isFull() – Return true if the queue is full, otherwise return false.

Advantages of ADT
 Encapsulation: ADTs help encapsulate data and operations into a single unit, making
managing and modifying the data structure easier.
 Abstraction: You can work with ADTs without knowing the implementation details,
which can simplify programming and reduce errors.
 Data Structure Independence: ADTs can be implemented using different data
structures, to make it easier to adapt to changing needs and requirements.
 Information Hiding: ADTs protect data integrity by controlling access and preventing
unauthorized modifications.
 Modularity: ADTs can be combined with other ADTs to form more complex data
structures increasing flexibility and modularity in programming.
 Robust: The program is robust and has the ability to catch errors.
Disadvantages of ADT
 Overhead: Implementing ADTs can lead to overhead in terms of memory and
processing resulting in reduced performance.
 Complexity: ADTs can be complex to implement, especially for large and complex data
structures.
 Learning Curve: To learn to implement ADTs takes a good amount of time and effort.
 Limited Flexibility: Some ADTs may be limited in their functionality or may not be
suitable for all types of data structures.
 Cost: Implementing ADTs may require additional resources and investment increasing
the cost of development.
Applications and Use Cases of ADT
 Data Structures: ADTs are used to implement fundamental data structures
like arrays, linked lists, stacks, queues, trees, graphs, hash tables, and heaps.
 Database Management Systems (DBMS): Concepts like tables, rows, columns, and
relationships can be represented using ADTs.
 Operating Systems: ADTs are employed in the design and implementation of operating
system components such as file systems, process management, memory management,
and synchronization mechanisms.
 Compiler Design: ADTs represent and manipulate various components of a compiler
like abstract syntax trees, symbol tables, and intermediate code representations.
 Networking: ADTs like queues and buffers are used for storing and managing packets in
network switches and routers.

8
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Implementation of STACK ADT Using Arrays:

Program:
#include <stdio.h>
#include<conio.h>
#include<stdlib.h>
#define SIZE 10
void push(int);
void pop();
void display();
int stack[SIZE],top=-1;
int main()
{
int value,choice;
while(1)
{
printf("\nmenu\n");
printf("1.push\t2.pop\t3.display\t4.exit\t");
printf("\nenter choice\t");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\nenter a value to be inserted\t");
scanf("%d",&value);
push(value);
break;
case 2:pop();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("wrong selection");
}
}
return 0;
}
void push(int value)
{
if (top== SIZE-1)
{
printf("stack is full insertion not possible");
}
else
{
top++;
stack[top]=value;
printf("insertion success");
}
}
void pop()
{
if(top==-1)
9
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

{
printf("Stack is empty,deletion not possible");
}
else
{
printf("deleted is %d",stack[top]);
top--;
}
}

void display()
{
if (top==-1)
printf("stack is empty");
else
{
int i;
printf("stack elements are \t");
for (i=top;i>=0;i--)
printf("%d\t",stack[i]);
}
}

Output:
Menu
1.push 2.pop 3.display 4.exit
enter choice 1

enter a value to be inserted 20

insertion success
Menu
1.push 2.pop 3.display 4.exit
enter choice 1

enter a value to be inserted 25

insertion success
Menu
1.push 2.pop 3.display 4.exit
enter choice 1

enter a value to be inserted 30

insertion success
Menu
1.push 2.pop 3.display 4.exit
enter choice 3
stack elements are 30 25 20
menu
1.push 2.pop 3.display 4.exit
10
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

enter choice 2
deleted is 30
Menu
1.push 2.pop 3.display 4.exit
enter choice 3
stack elements are 25 20
Menu
1.push 2.pop 3.display 4.exit
enter choice 4

Overview of time and space complexity analysis for linear data

structures:
Performance analysis of an algorithm:
An algorithm is considered efficient and fast if it takes less time to execute and consumes less memory
space.
Analyzing an algorithm means determining the amount of resources (such as time and memory) needed
to execute it. Algorithms are generally designed to work with an arbitrary number of inputs, so the
efficiency or complexity of an algorithm is stated in terms of time and space complexity.
The efficiency of an algorithm depends on following two parameters:
1.Time complexity
2.Space complexity

1.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.,
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
11
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

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 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 requires 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 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,
12
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Cost is the amount of computer time required for a single operation in each line.
Repeatation is the amount of computer time required by each operation for all its repeatations.
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 Notation:

Asymptotic notation of an algorithm is a mathematical representation of its complexity.

Asymptotic Notation is a tool for analyzing algorithms and comparing their performance.
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.

Notation is O (n2)

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.
Notation is Ω(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.
Notation is Θ(n log n)
2.Space complexity:

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.

13
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Fixed part:
It varies from problem to problem. It includes the space needed for storing instructions, constants,
variables, and structured variables (like arrays and structures).

Variable part:
It varies from program to program. It includes the space needed for recursion stack, and for
structured variables that are allocated space dynamically during the runtime of a program.
The space requirement s(p) of any algorithm p may therefore be written as,
S(P) = c+ Sp(Instance characteristics)
Where ‘c’ is a constant.
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 data
type values (according to the compiler). For example, the C Programming Language compiler
requires the following...

1. 2 bytes to store Integer value.

2. 4 bytes to store Floating Point value.
3. 1 byte to store Character value.
4. 6 (OR) 8 bytes to store double value.

Consider the following code...

Example 1:
int square(int a)
{
return a*a;
}
In the above piece of code, it requires 2 bytes of memory to store variable 'a' and another 2 bytes of
memory is used for return value.That means, totally it requires 4 bytes of memory to complete its
execution. And this 4 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];
14
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

return sum;
}
In the above piece of code it requires
'n*2' bytes of memory to store array variable 'a[ ]'

2 bytes of memory for integer parameter 'n'

4 bytes of memory for local integer variables 'sum' and 'i' (2 bytes each)

2 bytes of memory for return value.

That means, totally it requires '2n+8' 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.

**Complexity Analysis for Linear Data Structures:

Linear Data structure are those data structures in which data is stored sequentially, and each
element is connected to the previous or next element so that they can be accessed in a single run.
Some examples of linear data structures are arrays, stacks, queues, lists etc.
Time Complexity
Time complexity can be understood as a concept that constitutes the quantification of time taken
by an algorithm to execute. The time complexity is also a measure of the efficiency, such that
the lesser the time is taken by the algorithm, the more its efficiency will be.
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.

Space Complexity
Space Complexity can be understood as the amount of memory space occupied by a code
snippet or algorithm. It is one of the two measures of the efficiency of an algorithm. The lesser
the space it takes, the more efficient it is.
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.

Time complexity of linear Data Structures:

Array
A Data Structure in which a similar type of data is stored at contiguous memory locations is
called an array. Array is the most frequently used linear data structure in computer science and
due to its connectivity with the previous and next element, it became the inspiration for data
structures like linked lists, queues, etc.
15
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Time Complexity in arrays of size ‘N’:

 In an array, ‘ARR’ where the address of the first element is ‘A’ and the size of each
element is ‘S’, ‘i’th element can be defined as
ARR[i] = A + (i - 1) * S
Thus accessing an element at a specific memory address takes O(1) time, as its relative
address can be calculated in constant time.
 Similarly editing any element of the array takes O(1) time.
 Inserting a new element at a particular index in arrays is only possible when we skip all
the elements before that index, which takes O(N) time.
 Similarly, deletion operation also takes O(N) time.
 Searching operation in arrays takes O(N) time without any specific algorithm as we need
to iterate and check every element in the array.

Queue
A queue can be defined as a linear data structure, which is simply a collection of entries that are
tracked in order, such that the addition of entries happens at one end of the queue, while the
removal of entries takes place from the other end. Its order is also known as First In First Out
(FIFO).

Time Complexity of the queue containing ‘N’ elements:

 To access or edit any element stored in a queue, the time taken is O(N) as to reach any
specific element, all the elements after it has to be removed.
 The searching operation also takes a total time of O(N), as reaching any specific element
isn’t possible without popping the elements stored after it.
 Operations like insertion or deletion in a queue take constant time i.e., O(1). Only the
front element can be removed at a time and insertion can only take place at the back.
‘
Stack
A stack is a linear data structure, following a particular order in which operations can be
performed. Its order is also known as LIFO(Last In First Out). Stacks are implemented using
arrays and linked lists. Let us discuss its efficiency in terms of time and space complexity.

16
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Time Complexity of a Stack storing ‘N’ elements

 To access or edit any element stored in a stack, the time taken is O(N) as to reach any
specific element, all the elements before it has to be removed.
 The searching operation also takes a total time of O(N), as reaching any specific element
isn’t possible without popping the elements stored before it.
 Operations like insertion or deletion in a stack take constant time i.e. O(1).

Linked List
A linked list can be understood as a data structure that consists of nodes to store data. Each node
consists of a data field and a pointer to the next node. The various elements in a linked list are
linked together using pointers. In Linked List, unlike arrays, elements are not stored at
contiguous memory locations but rather at different memory locations.
Its efficiency can be understood with the below complexity analysis.

Time Complexity of linked list storing ‘N’ elements

For insertion in the linked list, the time complexity is O(1) if done on the head, O(N) if done at
any other location, as we need to reach that location by traversing the linked list.
For deletion, the time complexity is O(1), if done on the head, O(N), if done at any other
location, as we need to reach that location by traversing the linked list.
For searching and accessing any elements, the involved time complexity is O(N).

17
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Space complexity analysis of linear data Structures:

Space complexity measures the amount of memory or space an algorithm o data structure uses
as a function of the input size.For linear data structures ,such as arrays, linked lists, stacks and
queues, the space complexity influenced by the number of elements stored and the additional
space required for data structure management.
Arrays:
Arrays have constant space complexity O(n), meaning that the amount of memory space
required to store an array grows linearly with the size of the array.
Space complexity : O(N)
Array=[1,2,3,4,5]
In above example of array, each element is of standard data type like an integer, the space
complexity can be calculated as follows,
Elements in array=five
Size of each element in array=4 bytes
Total Space Complexity=Number of elements*size of each element
=5*4=20 bytes

Linked Lists: Linked lists have a linear space complexity of O(n),meaning that the amount of
memory space required to store a linked list grows linearly with the size of the list.
Space complexity : O(N)

Stacks: Stacks are often implemented using arrays or linked lists. The number of elements in
the stack determines the space complexity.
Space complexity : O(N)

Queues: Like Stacks,Queues can be implemented using arrays or linked lists and the space
complexity is determined by the number of elements in the queue.
Space complexity : O(N)

18
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

**Searching Techniques: Linear Search and Binary Search

Searching:
Searching is a process of finding a particular record, which can be a single element or a small
chunk, within a huge amount of data. The data can be in various forms: arrays, linked lists, trees,
heaps, and graphs etc. With the increasing amount of data nowadays, there are multiple
techniques to perform the searching operation.

Linear Search:

Linear search is a type of sequential searching algorithm. In this method, every element within
the input array is traversed and compared with the key element to be found. If a match is found
in the array the search is said to be successful; if there is no match found the search is said to be
unsuccessful and gives the worst-case time complexity.
For instance, in the given diagram, we are searching for an element 33. Therefore, the linear
search method searches for it sequentially from the very first element until it finds a match. This
returns a successful search.

In the same diagram, if we have to search for an element 46, then it returns an unsuccessful
search since 46 is not present in the input.

Linear Search Algorithm

The algorithm for linear search is relatively simple. The procedure starts at the very first index
of the input array to be searched.

Step 1 − Start from the 0th index of the input array, compare the key value with the value
present in the 0th index.

Step 2 − If the value matches with the key, return the position at which the value was found.

Step 3 − If the value does not match with the key, compare the next element in the array.

Step 4 − Repeat Step 3 until there is a match found. Return the position at which the match was
found.

Step 5 − If it is an unsuccessful search, print that the element is not present in the array and exit
the program.

19
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Pseudo code

procedure linear_search (list, value)

for each item in the list
if match item == value
return the item's location
end if
end for
end procedure

Analysis:
Linear search traverses through every element sequentially therefore, the best case is when the element
is found in the very first iteration. The best-case time complexity would be O(1).
However, the worst case of the linear search method would be an unsuccessful search that does not find
the key value in the array, it performs n iterations. Therefore, the worst-case time complexity of the
linear search algorithm would be O(n).

Example
Let us look at the step-by-step searching of the key element (say 47) in an array using the linear
search method.

Step 1 : The linear search starts from the 0th index. Compare the key element with the value in
the 0th index, 34.

However, 47 ‚ 34. So it moves to the next element.

Step 2 : Now, the key is compared with value in the 1st index of the array.

Still, 47 ‚ 10, making the algorithm move for another iteration.

Step 3 : The next element 66 is compared with 47. They are both not a match so the algorithm
compares the further elements.

20
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Step 4 : Now the element in 3rd index, 27, is compared with the key value, 47.
They are not equal so the algorithm is pushed forward to check the next element.

Step 5 : Comparing the element in the 4th index of the array, 47, to the key 47. It is figured that
both the elements match. Now, the position in which 47 is present, i.e., 4 is returned.

The output achieved is “Element found at 4th index”.

Time complexity of Linear Search is O(n)

Space complexity of Linear Search is O(1)

Implementation
The Linear Search program can be seen implemented in four programming languages. The
function compares the elements of input with the key value and returns the position of the key in
the array or an unsuccessful search prompt if the key is not present in the array.

Program for Linear Search:

#include <stdio.h>
void linear_search(int a[], int n, int key)
{
int i, count = 0;

for(i = 0; i < n; i++)

{
if(a[i] == key)
{
// compares each element of the array
printf("The element is found at %d position\n", i+1);
count = count + 1;
}
}
if(count == 0) // for unsuccessful search
{

21
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

printf("The element is not present in the array\n");

}
}
int main()
{
int i, n, key;
n = 6;
int a[10] = {12, 44, 32, 18, 4, 10};
key = 18;
linear_search(a, n, key);
key = 23;
linear_search(a, n, key);
return 0;
}

Output:

The element is found at 4 position

The element is not present in the array

BINARY SEARCH:
Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search
algorithm works on the principle of divide and conquer, since it divides the array into half
before searching.
For this algorithm to work properly, the data collection should be in the sorted form.
Binary search looks for a particular key value by comparing the middle most item of the
collection. If a match occurs, then the index of item is returned. But if the middle item has a
value greater than the key value, the right sub-array of the middle item is searched.
Otherwise, the left sub-array is searched. This process continues recursively until the size of
a sub array reduces to zero.

Binary Search Process steps and algorithm:

1. Check whether the list is sorted or not, because binary search only works for sorted list.
2. Set lower bound and and upper bound of the list, where Lower bound is the index of the
first element , and upper bound is the index of the last element.
3. Find the middle element index, by using middle=(lower bound+upper bound)/2
1. Compare the middle element of the search space with the key.
If the key is found at middle element, the process is terminated. ( that is search is found)
1. If the key is not found at middle element, choose which half will be used as the next
search space.
1. If the key is smaller than the middle element, then the left side (lower bound search
space) is used for next search. (i.e; eliminated upper search space, set upper bound=mid-
1)

22
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

1. If the key is larger than the middle element, then the right side (upper bound search
space) is used for next search. ( i.e; eliminated lower search space, set lower
bound=mid+1)
1. This process is continued until the key is found or the total search space is exhausted. If
the total space is exhausted, search element is not found.

ALGORITHM:
BINARY SEARCH[A,N,KEY]
Step 1: begin
Step 2: [Initilization]
Lb=1; ub=n;
Step 3: [Search for the ITEM]
Repeat through step 4,while Lower bound is less than Upper Bound.
Step 4: [Obtain the index of middle value]
MID=(lb+ub)/2
Step 5: [Compare to search for ITEM]
If Key<A[MID] then
Ub=MID-1
Other wise if Key >A[MID] then
Lb=MID+1
Otherwise write “Match Found”
Return Middle.
Step 6: [Unsuccessful Search]
write “Match Not Found”
Step 7: Stop.

Example:

Ex: consider a list of sorted elements stored in an Array A is

Let the key element which is to be searched is 35.

Key=35
The number of elements in the list n=9.

Step 1:
MID= [lb+ub]/2
=(1+9)/2
=5
23
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Key<A[MID]
i.e. 35<46.
So search continues at lower half of the array.
Ub=MID-1
=5-1 = 4.
Step 2:

MID= [lb+ub]/2
=(1+4)/2
=2.

Key>A[MID]
i.e. 35>12.
So search continues at Upper Half of the array.
Lb=MID+1
=2+1
= 3. 50

Step 3:
MID= [lb+ub]/2
=(3+4)/2
=3.

Key>A[MID]
i.e. 35>30.
So search continues at Upper Half of the array.
Lb=MID+1
=3+1
= 4.

24
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Step 4: MID= [lb+ub]/2

=(4+4)/2
=4.

Advantages: When the number of elements in the list is large, Binary Search executed faster than linear
search. Hence this method is efficient when number of elements is large.
Disadvantages: To implement Binary Search method the elements in the list must be in sorted order,
otherwise it fails.

Time Complexity
Case Time Complexity

Best Case Ω (1)

Average Case Θ (logn)

Worst Case O (logn)

o Best Case Complexity - In Binary search, best case occurs when the element to search is found
in first comparison, i.e., when the first middle element itself is the element to be searched. The
best-case time complexity of Binary search is O(1).
o Average Case Complexity - The average case time complexity of Binary search is O(logn).
o Worst Case Complexity - In Binary search, the worst case occurs, when we have to keep
reducing the search space till it has only one element. The worst-case time complexity of Binary
search is O(logn).
2. Space Complexity
Space Complexity O(1)
o The space complexity of binary search is O(1).

Implementation:
Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search
algorithm works on the principle of divide and conquer. For this algorithm to work
properly, the data collection should be in a sorted form.

25
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Program for binary search:

#include<stdio.h>
void binary_search(int a[ ], int low, int high, int key)
{
int mid;
mid = (low + high) / 2;
if (low <= high)
{
if (a[mid] == key)
printf("Element found at index: %d\n", mid);
else if(key < a[mid])
binary_search(a, low, mid-1, key);
else if (a[mid] < key)
binary_search(a, mid+1, high, key);
}
else if (low > high)
printf("Unsuccessful Search\n");
}
int main()
{
int i, n, low, high, key;
n = 5;
low = 0;
high = n-1;
int a[10] = {12, 14, 18, 22, 39};
key = 22;
binary_search(a, low, high, key);
key = 23;
binary_search(a, low, high, key);
return 0;
}
Output
Element found at index: 3
Unsuccessful Search

26
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

**SORTING TECHNIQUES: Bubble Sort, Selection Sort, Insertion Sort

INTRODUCTION
Sorting is a technique of organizing the data. It is a process of arranging the records, either in
ascending or descending order i.e. bringing some order lines in the data. Sort methods are very
important in Data structures.
Sorting can be performed on any one or combination of one or more attributes present in each
record. It is very easy and efficient to perform searching, if data is stored in sorting order. The
sorting is performed according to the key value of each record. Depending up on the makeup of key,
records can be stored either numerically or alphanumerically. In numerical sorting, the records
arranged in ascending or descending order according to the numeric value of the key.

BUBBLE SORT
Bubble Sort: This sorting technique is also known as exchange sort, which arranges values by
iterating over the list several times and in each iteration the larger value gets bubble up to the end of
the list.

Working of bubble sort:

1. The bubble sort starts with the very first index and makes it a bubble element. Then it
compares the bubble element, which is currently our first index element, with the next
element. If the bubble element is greater and the second element is smaller, then both of
them will swap.
After swapping, the second element will become the bubble element. Now we will compare
the second element with the third as we did in the earlier step and swap them if required.
otherwise no change in their order.The same process is followed until the last element.
2. We will follow the same process for the rest of the iterations. After each of the iteration, we
will notice that the largest element present in the unsorted array has reached the last index.

Example
We take an unsorted array for our example. Bubble sort takes Ο(n2) time so we're keeping it short
and precise.

Bubble sort starts with very first two elements, comparing them to check which one is greater.

27
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33
with 27.

We find that 27 is smaller than 33 and these two values must be swapped.

Next we compare 33 and 35. We find that both are in already sorted positions.

Then we move to the next two values, 35 and 10.

We know then that 10 is smaller 35. Hence they are not sorted. We swap these values. We find that
we have reached the end of the array.

After one iteration, the array should look like this −

To be precise, we are now showing how an array should look like after each iteration. After the
second iteration, it should look like this −

28
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Notice that after each iteration, at least one value moves at the end. After the third iteration ,it
should look like this,

After the fourth iteration ,it should look like this,

And when there's no swap required, bubble sort learns that an array is completely sorted.

29
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Bubble Sort Algorithm:

Step 1: Repeat Steps 2 and 3 for i=1 to 10
Step 2: Set j=1
Step 3: Repeat while j<=n
if a[i] < a[j] Then
interchange a[i] and a[j]
[End of if]
Set j = j+1
[End of Inner Loop]
[End of Step 1 Outer Loop]
Step 4: Exit

Advantages :
Simple and easy to implement
In this sort, elements are swapped in place without using additional temporary
storage, so the space requirement is at a minimum.
Disadvantages :
It is slowest method . O(n2)
Inefficient for large sorting lists.
Time Complexity: O(n2)
Auxiliary Space: O(1)

Example 2:
To discuss bubble sort in detail, let us consider an arrayA[ ] that has the Following elements:
A[ ] = {30, 52, 29, 87, 63, 27, 19, 54}
Pass 1:
Compare 30 and 52. Since 30 < 52, no swapping is done.
Compare 52 and 29. Since 52 > 29, swapping is
done. 30, 29, 52, 87, 63, 27, 19, 54
Compare 52 and 87. Since 52 < 87, no swapping is done.
Compare 87 and 63. Since 87 > 63, swapping is
done. 30, 29, 52, 63, 87, 27, 19, 54
Compare 87 and 27. Since 87 > 27, swapping is
done. 30, 29, 52, 63, 27, 87, 19, 54
Compare 87 and 19. Since 87 > 19, swapping is
done. 30, 29, 52, 63, 27, 19, 87, 54
Compare 87 and 54. Since 87 > 54, swapping is
done. 30, 29, 52, 63, 27, 19, 54, 87
Observe that after the end of the first pass, the largest element is placed at the
highest index of the array. All the other elements are still unsorted.
Pass 2:
Compare 30 and 29. Since 30 > 29, swapping is
done. 29, 30, 52, 63, 27, 19, 54, 87
Compare 30 and 52. Since 30 < 52, no swapping is done.
Compare 52 and 63. Since 52 < 63, no swapping is done.
Compare 63 and 27. Since 63 > 27, swapping is

30
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

done. 29, 30, 52, 27, 63, 19, 54, 87

Compare 63 and 19. Since 63 > 19, swapping is done.
29, 30, 52, 27, 19, 63, 54, 87
Compare 63 and 54. Since 63 > 54, swapping
is done. 29, 30, 52, 27, 19, 54, 63, 87
Observe that after the end of the second pass, the second largest element is
placed at the second highest index of the array. All the other elements are still unsorted.
Pass 3:
Compare 29 and 30. Since 29 < 30, no swapping is done.
Compare 30 and 52. Since 30 < 52, no swapping is done.
Compare 52 and 27. Since 52 > 27, swapping
is done. 29, 30, 27, 52, 19, 54, 63, 87
Compare 52 and 19. Since 52 > 19, swapping
is done. 29, 30, 27, 19, 52, 54, 63, 87
Compare 52 and 54. Since 52 < 54, no swapping is done.
Observe that after the end of the third pass, the third largest element is placed at
the third highest index of the array. All the other elements are still unsorted.
Pass 4:
Compare 29 and 30. Since 29 < 30, no swapping is done.
Compare 30 and 27. Since 30 > 27, swapping
is done. 29, 27, 30, 19, 52, 54, 63, 87
Compare 30 and 19. Since 30 > 19, swapping
is done. 29, 27, 19, 30, 52, 54, 63, 87
Compare 30 and 52. Since 30 < 52, no swapping is done.
Observe that after the end of the fourth pass, the fourth largest element is placed at
the fourth highest index of the array. All the other elements are still unsorted.
Pass 5:
Compare 29 and 27. Since 29 > 27, swapping
is done. 27, 29, 19, 30, 52, 54, 63, 87
Compare 29 and 19. Since 29 > 19, swapping
is done. 27, 19, 29, 30, 52, 54, 63, 87
Compare 29 and 30. Since 29 < 30, no swapping is done.
Observe that after the end of the fifth pass, the fifth largest element is placed at
the fifth highest index of the array. All the other elements are still unsorted.
Pass 6:
Compare 27 and 19. Since 27 > 19, swapping
is done. 19, 27, 29, 30, 52, 54, 63, 87
Compare 27 and 29. Since 27 < 29, no swapping is done.
Observe that after the end of the sixth pass, the sixth largest element is placed at
the sixth largest index of the array. All the other elements are still unsorted.
Pass 7:
(a) Compare 19 and 27. Since 19 < 27, no swapping is done.
Observe that the entire list is sorted now.

31
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Program : Sort the element of array by using Bubble sort

#include<stdio.h>
void main ()
{
int i, j,temp;
int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34};
for(i = 0; i<10; i++)
{
for(j = i+1; j<10; j++)
{
if(a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
printf("Printing Sorted Element List ...\n");
for(i = 0; i<10; i++)
{
printf("%d\n",a[i]);
}
}

Output:
Printing Sorted Element List . . .
7
9
10
12
23
34
44
78
101

32
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

SELECTION SORT
Selection Sort algorithm is used to arrange a list of elements in a particular order (Ascending or
Descending).
In selection sort, the first element in the list is selected and it is compared repeatedly with all the
remaining elements in the list. If any element is smaller than the selected element (for Ascending order),
then both are swapped so that first position is filled with the smallest element in the sorted order. Next,
we select the element at a second position in the list and it is compared with all the remaining elements
in the list. If any element is smaller than the selected element, then both are swapped. This procedure is
repeated until the entire list is sorted.

Step by Step Process

The selection sort algorithm is performed using the following steps...
 Step 1 - Select the first element of the list (i.e., Element at first position in the list).
 Step 2: Compare the selected element with all the other elements in the list.
 Step 3: In every comparision, if any element is found smaller than the selected element (for
Ascending order), then both are swapped.
 Step 4: Repeat the same procedure with element in the next position in the list till the entire list
is sorted.
Following is the sample code for selection sort...

Example

33
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

34
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Advantages:
It is simple and easy to implement.
It can be used for small data sets.
It is 60 per cent more efficient than bubble sort.
Disadvantages:
Running time of Selection sort algorithm is very poor of 0 (n2).
However, in case of large data sets, the efficiency of selection sort drops as compared to insertion sort.
Complexity of the Selection Sort Algorithm
To sort an unsorted list with 'n' number of elements, we need to make ((n-1)+(n-2)+(n-3)+......+1) = (n (n-1))/2
number of comparisions in the worst case. If the list is already sorted then it requires 'n' number of comparisions.
Worst Case : O(n2)
Best Case : Ω(n2)
Average Case : Θ(n2)

Example 2: 3, 6, 1, 8, 4, 5

Example 3 :
35
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Example: Consider the following array with 6 elements. Sort the elements of the array by using selection
sort.
A = {10, 2, 3, 90, 43, 56}.
Pass A[0] A[1] A[2] A[3] A[4] A[5]
1 2 10 3 90 43 56
2 2 3 10 90 43 56
3 2 3 10 90 43 56
4 2 3 10 43 90 56
5 2 3 10 43 56 90

Sorted A = {2, 3, 10, 43, 56, 90}

Program : Sort the elements of an array using Selection sort

#include<stdio.h>
int smallest(int[ ],int,int);
void main ()
{
int a[10] = {10, 9, 7, 101, 23, 44, 12, 78, 34};
int i,j,k,pos,temp;
for(i=0;i<10;i++)
{
pos = smallest(a,10,i);
temp = a[i];
a[i]=a[pos];
a[pos] = temp;
}
printf("\nprinting sorted elements...\n");
for(i=0;i<10;i++)
{
printf("%d\t",a[i]);
}
}

int smallest(int a[ ], int n, int i)

{
int small,pos,j;
small = a[i];
pos = i;
for(j=i+1;j<10;j++)
{
if(a[j]<small)
{
small = a[j];
pos=j;
}
}
return pos;
}
Output:
printing sorted elements...
7 9 10 12 23 34 44 78 101
INSERTION SORT
36
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Sorting is the process of arranging a list of elements in a particular order (Ascending or Descending).
Insertion sort algorithm arranges a list of elements in a particular order. In insertion sort algorithm,
every iteration moves an element from unsorted portion to sorted portion until all the elements are sorted
in the list.
Insertion sort is one of the best sorting techniques. It is twice as fast as Bubble sort. In Insertion
sort the elements comparisons are as less as compared to bubble sort. In this comparison the
value until all prior elements are less than the compared values is not found. This means that all
the previous values are lesser than compared value. Insertion sort is good choice for small
values and for nearly sorted values.

The Insertion sort algorithm selects each element and inserts it at its proper position in a sub list
sorted earlier. In a first pass the elements A1 is compared with A0 and if A[1] and A[0] are not
sorted they are swapped.
In the second pass the element[2] is compared with A[0] and A[1]. And it is inserted at its
proper position in the sorted sub list containing the elements A[0] and A[1]. Similarly doing ith
iteration the element A[i] is placed at its proper position in the sorted sub list, containing the
elements A[0],A[1],A[2],…………A[i-1].

Step by Step Process

The insertion sort algorithm is performed using the following steps...

 Step 1 - Assume that first element in the list is in sorted portion and all the remaining elements
are in unsorted portion.

 Step 2: Take first element from the unsorted portion and insert that element into the sorted
portion in the order specified.

 Step 3: Repeat the above process until all the elements from the unsorted portion are moved into
the sorted portion.

Example:

37
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Complexity of the Insertion Sort Algorithm

38
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

To sort an unsorted list with 'n' number of elements, we need to make (1+2+3+......+n-1) = (n (n-1))/2
number of comparisions in the worst case. If the list is already sorted then it requires 'n' number of
comparisions.

Worst Case : O(n2)

Best Case : Ω(n)
Average Case : Θ(n2)

Time Complexity: O(N2)

Auxiliary Space: O(1)

Advantages of Insertion Sort:

 It is simple sorting algorithm, in which the elements are sorted by considering one item at a
time. The implementation is simple.
 It is efficient for smaller data set and for data set that has been substantially sorted before.
 It does not change the relative order of elements with equal keys
 It reduces unnecessary travels through the array
 It requires constant amount of extra memory space.
Disadvantages:-
 It is less efficient on list containing more number of elements.
 As the number of elements increases the performance of program would be slow .

Example2:
The steps to sort the values stored in the array in ascending order using Insertion sort are
given below:

Step 1: The first value i.e; 7 is trivially sorted by itself.

Step 2: the second value 33 is compared with the first value 7. Since 33 is greater than 7, so no
changes are made.
Step 3: Next the third element 20 is compared with its previous element (towards left).Here 20
is less than 33.but 20 is greater than 7. So it is inserted at second position. For this 33 is shifted
towards right and 20 is placed at its appropriate position.

Step 4: Then the fourth element 11 is compared with its previous elements. Since 11 is less than
33 and 20 ; and greater than 7. So it is placed in between 7 and 20. For this the elements 20 and
33 are shifted one position towards the right.

39
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

Step5: Finally the last element 6 is compared with all the elements preceding it. Since it is
smaller than all other elements, so they are shifted one position towards right and 6 is inserted at
the first position in the array. After this pass, the Array is sorted.

Step 6: Finally the sorted Array is as follows:

Program: To implement Insertion Sort

#include <stdio.h>
void insertionSort(int arr[ ], int N)
{
// Starting from the second element
for (int i = 1; i < N; i++)
{
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1], that are //
greater than key, to one position to
// the right of their current position

while (j >= 0 && arr[j] > key)

{
arr[j + 1] = arr[j];
j = j - 1;
}
// Move the key to its correct position
arr[j + 1] = key;
}
}

int main()
{
int arr[] = { 12, 11, 13, 5, 6 };
printf("Unsorted array: ");
for (int i = 0; i < 5; i++)
{
printf("%d ", arr[i]);
}
40
NDP
SIR CRRCOE-DEPARTMENT OF INFORMATION TECHNOLOGY DATA STRUCTURES-CR24

printf("\n");

// Calling insertion sort on array arr

insertionSort(arr, 5);

printf("Sorted array: ");

for (int i = 0; i < 5; i++)
{
printf("%d ", arr[i]);
}
printf("\n");

return 0;
}

Output:
Unsorted array: 12 11 13 5 6
Sorted array: 5 6 11 12 13

41
NDP