UNIT - I

Introduction to linear Data Structures: definition and importance of linear

data structures, abstract data types (ADTs) and their implementation,
overview of time and space complexity analysis for linear data structures,
searching techniques: linear and binary search, sorting techniques: bubble
sort, selection sort, and insertion sort.
Introduction
Data Structure can be defined as the group of data elements which provides an
efficient way of storing and organizing data in the computer so that it can be
used efficiently. Some examples of Data Structures are arrays, Linked List, Stack,
Queue, etc. Data Structures are widely used in almost every aspect of Computer
Science i.e. Operating System, Compiler Design, Artificial intelligence, Graphics
and manymore.
Data Structures are the main part of many computer science algorithms as they
enablethe programmers to handle thedata in an efficient way. It plays a vital role
in enhancing the performance of a software or a program as the main function of
thesoftware is to store and retrieve theuser's data as fast as possible.
Basic Terminology
Data structures are thebuildingblocks ofany program or the software. Choosing
the appropriate data structure for a program is the most difficult task for a
programmer. Following terminology is used as far as data structures are
concerned.
Data: Data can be defined as an elementary value or the collection of values, for
example, student's name and its id are thedata about the student.
Group Items: Data items which have subordinate data items are called Group
item, for example,nameof a student can havefirstname andthe last name.
Record: Record can be defined as the collection of various data items, for
example, if we talk about the student entity, then its name, address, course and
marks can be grouped together to form therecordfor thestudent.
File: A File is a collection of various records of one type of entity, for example, if
there are 60 employees in the class, then there will be 20 records in the related
file where each record contains the data about each employee.
Attribute and Entity: An entity represents the class of certain objects. it
contains variousattributes. Each attribute represents the particular property of
that entity.
Field: Field is a single elementary unit of information representing the attribute of
an entity.
Need for Data Structure
 It gives different level of organization data.
 It tells how data can bestoredand accessed in its elementary level.
 Provide operation on group of data, such as adding an item, looking up highest
priority item.
 Provide a means to manage huge amount of data efficiently.
 Provide fast searching andsortingof data.

Some of the important advantages of Data structures:

[Link] storage and retrieval of data – Data structures allow you to store and
retrieve data in an efficient manner. For example, using a hash table data
structure, you can access an element in constant time, whereas searching for an
element in an unorderedlist would takelinear time.
[Link] performance – Data structures can help improve the performance
of your code by reducing the time and space complexity of algorithms. For
example, using a binary search tree instead of a linear search can significantly
reduce thetimeit takes to finda specific element in a largedataset.
[Link] problem solving – Data structures can help you solve complex
problems by breaking them down into smaller, more manageable parts. For
example, using a graph data structure can help you solve problems related to
network flow or finding the shortest path between two points.
[Link] – Data structures provide a way to abstract the underlying
complexityof a problem and simplify it, making it easier to understandand solve.
[Link] – Data structures can be used in many different algorithms and
applications,making them a useful tool in your programming toolbox.
In short, data structures are important because they provide a way to organize
and manage data in a way that is efficient, flexible, and scalable. Whether you are
working on a large-scale software project or a simple program, a solid
understanding of data structures is essential for success.
Classification of datastructures:

Linear Data Structures: A data structure is called linear if all of its elements are
arranged in thelinear order. In linear data structures, the elements are stored in
non-hierarchical way where eachelement has the successors and predecessors
except the first and last element or maintains a linear relationship among its
elements is calleda linear data structure
If a datastructure organizes the datain sequential order, then thatdata
structure is calledLinear Data Structure.
Example:
1. Arrays
2. List (Linked List)
3. Stack
4. Queue

Types of Linear Data Structures are givenbelow:

Arrays: An array is a collection of similar type of data items and each data item
is called an element of the array. The data type of the element may be any valid
data type like char,int,float or double.
The elements of array share the same variable name but each one carries a
different index number known as subscript. The array can be one dimensional,
two dimensional or multidimensional.
The individual elements of the array age are:
age[0],age[1], age[2], age[3],. age[98],age[99].

Linked List: Linkedlist is a linear data structure which is used to maintain a list in
the [Link] can be seen as the collection of nodes stored at non-contiguous
memory locations. Each nodeof thelistcontains a pointer to its adjacent node.
Arrays:
Array, in general, refers to an orderly arrangement of data elements. Array is a
type of data structure that stores data elements in adjacent locations. Array is
considered as lineardata structure that stores elements of same data types.
Hence,it is also called as a linear homogenous data structure.
When we declare an array, we can assign initial values to each of its
elements byenclosing the values in braces {}.
int Num [5] = { 26, 7,67,50,66 };
This declaration will createan arrayas shown below:
0 1 2 3 4

The number of values inside braces { } should be equal to the number of

elements that we declare for the array inside the square brackets [ ]. In the
example of array Paul,we have declared 5 elements and in thelist of initial values
within braces { } we have specified 5 values, one for each element. After this
declaration, array Paul will have five integers, as we have provided 5 initialization
values.
Arrays can be classified as one-dimensional array, two-dimensional array or
multidimensional array.
One-dimensional Array: It has only one row of elements. It is stored in
ascendingstoragelocation.
Two-dimensional Array: It consists of multiple rows and columns of data
elements. It isalso calledas a matrix.
Multidimensional arrays can be defined as array of
arrays. Multidimensional arrays are not bounded to two indices or two
dimensions. Theycan include as many indices as required.
Limitations:
Arrays are of fixedsize.

 Data elements are stored in contiguous memory locations which may not
bealways available.
 Insertion and deletion of elements can be problematic because of shifting
ofelements fromtheir positions.
However,theselimitations can be solved byusinglinked lists.
Applications:
Storing list of data elements belongingto samedata type

Auxiliarystorage for other data structures

Storage of binarytree elements of fixedcount

Storage of matrices


1. Linked List:
A linked list is a data structure in which each data element contains a pointeror
link to the next element in the list. Through linked list, insertion anddeletion
of the data element is possible at all places of a linear list. Also in linked list, it is
not necessary to have the data elements stored in consecutive locations. It
allocates space for each data item in its own block of memory. Thus, a linked list is
considered as a chain of data elements or records called nodes. Each node in the
list contains information field and a pointer field. The information field contains the
actual data and the pointer field contains addressof the subsequent nodes in the
list.
 Figure represents a linkedlist with 4 nodes. Each node has two parts. The left
part in the node represents the information part which contains an entire
record of data items andthe right part represents the pointer to the next
node. The pointer of the last nodecontainsa null pointer.
: Easier to insert or deletedata elements
: Slow search operation and requires more memoryspace
Applications:
 Implementingstacks,queues, binarytrees and graphs ofpredefinedsize.
 Implement dynamic memorymanagement functions of operatingsystem.
 Polynomial implementation for mathematical operations
 Circularlinked listis used to implement OSor application functions that require
roundrobin execution of tasks.
 Circular linkedlist is usedin a slideshow where a user wants to go back to the
first slideafter last slide is displayed.
 Doublylinked list is used in the implementation of forwardand backward
buttonsin a browser to move backwards and forward in the opened pages of a
website.
 Circular queue is usedto maintain the playing sequence of multiple players in a
game.
2. Stacks
A stack is a linear data structure in which insertion and deletion of elements are done
at only one end, which is known as the top of the stack. Stack is called a last-in,
first-out (LIFO) structure because the last element which is added to the stack is the
first element which is deleted from the stack.
In the computer’ s memory, stacks can be implemented using arrays or linked lists.
Figure is a schematic diagram of a stack. Here, element FF is the top of the stack and
element AA is the bottom of the stack. Elements are added to the stack from the top.
Since it follows LIFO pattern, EE cannot be deleted before FF is deleted, and similarly
DDcannotbe deleted beforeEE is deleted and so on.
Applications:
 Temporarystorage structure for recursiveoperations
 Auxiliarystorage structure for nested operations, function calls,
deferred/postponedfunctions
 Managefunction calls
 Evaluation of arithmetic expressions in various programminglanguages
 Conversion of infix expressions into postfix expressions
 Checkingsyntax of expressions in a programmingenvironment
 Matchingof parenthesis
 String reversal
 In all theproblems solutions based on backtracking.
 Usedin depth first search in graph andtree traversal.
 OperatingSystem functions
 UNDO and REDO functions in an editor.

[Link]:
A queue is a first-in, first-out (FIFO) data structure in which the element that is
inserted first is the first one to be taken out. The elements in a queue are added
at one end called the rear and removed from the other end called the front.
Like stacks,queues can be implemented byusingeitherarrays orlinked lists.
Figure shows a queue with 4 elements, where 55 is the front element and 65 is
the rear element. Elements can be added from the rear and deleted from the
front.
Applications:
 It is usedin breadth search operation in graphs.
 Jobscheduler operations of OS like a print buffer queue, keyboard buffer
queuetostorethe keys pressed byusers
 Jobscheduling, CPU scheduling, Disk Scheduling
 Priority queues areusedin file downloadingoperations in a browser
 Data transfer between peripheral devices and CPU.
 Interrupts generatedbytheuser applications for CPU
 Calls handled bythe customers in BPO

Non Linear Data Structures:

This data structure does not form a sequence i.e. each item or element is
connected with two or more other items in a non-linear arrangement. The data
elements are not arranged in sequential structure.
If a data structure organizes the data in random order, then that data
structure is called as Non-Linear Data
Example
1. Tree
[Link]
[Link]
[Link]
[Link],Etc.,

Types of Non Linear Data Structures are givenbelow:

Trees: Trees aremultilevel data structures with a hierarchical relationshipamong
its elements known as nodes. The bottommost nodes in the herierchy are called
leaf node while the topmost node is called root node. Each node contains
pointers to point adjacent nodes.
Tree data structure is based on the parent-child relationship among the nodes.
Each node in the tree can have more than one children except the leaf nodes
whereas each node can have atmost one parent except the root node. Trees
can beclassfied into many categories which will be discussedlater in this tutorial.
Graphs: Graphs can be defined as the pictorial representation of the set of
elements (representedby vertices) connected by the links known as edges. A
graph is different from tree in the sense that a graph can have cycle while the
tree can not have the one.
Trees
A tree is a non-linear data structure in which data is organized in branches. The
data elements in tree are arranged in a sorted order. It imposes a hierarchical
structure on the data elements.
Figure represents a tree which consists of 8 nodes. The root of the tree is the
node 60 at the top. Node 29 and 44 are the successors of the node 60. The
nodes 6, 4, 12 and 67 are the terminal nodes as they do not have any
successors.

Applications:
 Implementingthe hierarchical structures in computer systems like
directory andfile system.
 Implementingthe navigation structure of a website.
 Code generation likeHuffman’ s code.
 Decision making in gaming applications.
 Implementation of priorityqueues for priority-based OS scheduling
functions
 Parsingof expressions and statements in programminglanguage
compilers
 For storingdata keys for DBMS forindexing
  Spanning trees for routingdecisions in computer andcommunications
networks
 Hash trees
 Path-finding algorithm to im plement in AI, robotics andvideo games
applications
Graphs:
A graph is also a non-linear data structure. In a tree data structure, all data
elements are stored in definite hierarchical structure. In other words, each node
has only one parent node. While in graphs, each data element is called a vertex
and is connected to many other vertexes through connections callededges.
Thus, a graph is considered as a mathematical structure, which is composed ofa
set of vertexes and a set of edges. Figure shows a graph with six nodes A, B, C,
D,E,F and seven edges [A, B], [A,C], [A, D], [B, C],[C, F], [D, F] and [D, E].

 Representingnetworks and routes in communication,transportation and

travelapplications
 Routes in GPS
 Interconnections in social networks and other network-based applications
 Mapping applications
 Ecommerceapplications to presentuserpreferences
 Utilitynetworks to identifythe problems posed to municipal or local
corporations
 Resource utilization andavailabilityin an organization
 Document link map ofa websiteto displayconnectivitybetween pages
throughhyperlinks
 Robotic motion and neural networks
StaticDatastructure VsDynamic Datastructure
Data structure is a way of storing and organizing data efficiently such that the
requiredoperations on them can be performed be efficient with respect to time
as well as memory. Simply, Data Structure are used to reduce complexity
(mostly the time complexity) of the code.
Data structures can be two types:
1. Static Data Structure
2. Dynamic Data Structure
In Static data structure the size of the structure is fixed. The content of the data
structure can be modified but without changing the memory space allocated to
it.

Example of Static Data Structures: Array

In Dynamic data structure the size of the structure in not fixed and can be
modified during the operations performed on it. Dynamic data structures are
designed to facilitatechange of data structures in the run time.

Example of Dynamic Data Structures: Linked List

Static Data structure has fixed memory size whereas in Dynamic Data
Structure, the size can be randomly updated during run time which may be
considered efficient with respect to memory complexity of the code. Static Data
Structure provides more easier access to elements with respect to dynamic
data structure. Unlike static data structures,dynamic data structures are flexible.
Operationsondatastructure
Traversing: Every data structure contains the set of data elements. Traversing
the data structure means visiting each element of the data structure in order to
perform some specific operation like searching or sorting.
Example: If we need to calculate theaverage of themarks obtained by a student
in 6 different subject, we need to traverse the complete array of marks and
calculate the total sum, then we will devide that sum by the number of subjects
i.e. 6,in order to findtheaverage.
Insertion: Insertion can be defined as the process of adding the elements to the
data structure at any location.
If thesize of data structure is n then wecan only insert n-1 data elements into it.
Deletion: The process of removing an element from the data structure is called
Deletion. We can delete an element from the data structure at any random
location.
If we try to delete an element from an empty data structure then
underflow occurs.
Searching: The process of finding the location of an element within the data
structure is called Searching. There are two algorithms to perform searching,
Linear Search and Binary Search. We will discuss each one of them later in this
tutorial.
Sorting: The process of arranging the data structure in a specific order is known
as Sorting. There are many algorithms that can be used to perform sorting, for
example, insertion sort, selection sort, bubblesort, etc.
Merging: When two lists List A and List B of size M and N respectively, of similar
type of elements, clubbed or joined to produce the third list, List C of size (M+N),
then this process is called merging
Importance of Linear Data structures :
Linear data structures are important because they allow for the efficient
organization and manipulation of data in a sequential manner. They are
necessary for a variety of reasons:
[Link] Access: Linear data structures, such as arrays and linked lists, allow for
efficient access to individual elements by theirposition or index.
[Link] to Implement: Linear data structures are relatively simple to implement
and understand, making them ideal for a wide rangeof applications.
[Link] Efficiency: Linear data structures can be memory efficient, as they
require contiguous memory allocation in the case of arrays, or minimal overhead
in thecaseof linked lists.
[Link]: Linear data structures can be used to implement more complex
data structures and algorithms, such as stacks, queues, and trees, which are
fundamental in computer scienceand software development.
[Link] Processing: In many real-world scenarios, data needs to be
processed in a sequential manner, and linear data structures provide a natural
wayto represent andprocess such data.
Overall, the importance of linear data structures lies in their fundamental role in
organizing and manipulating data in a way that is efficient, easy to implement,
and versatile for a wide range of applications.
Abstract DataType:
When basic programming is started no ADT concept is available. If we want to
read a file, we wrote the code to read the file. It didn’ t take long to realise that
we were writing the same code over and over again. So we created what is
known today as ADT. We wrote the code to read a file and placed it in a library
for all programmers to use.
The same concept in modern languages today, the code to read the keyboard is
an ADT. It has a datastructure, a character, and a set of operations that can be
used to read that datastructure. With ADTs user are not concered with how the
task is done but rather with what itcan do.
ADTs consists of a set of definitions that allow programmer to use the functions
while hiding theimplementation. This generalization of operation with unspecified
implementation is known as abstraction. We abstract theessence of the process
and leavethe implementation details hidden
We know what datatype can do
But its implementation is hidden
Ex. 1. If weplace a list as ADT, List can be used for linear list, matrix,trees, graphs
[Link] as ADT, can be used in banking to servethe customers efficiently.
ADT- an abstract datatype is a data declaration package with operations called
encapsulation then hide from user.
Implementation:
Two basic structures to implement ADT,1. Arrays and 2. Linkedlists
Array implementation: the sequentiality of a list is maintained by the order
structure of elements in the array (indexes). Search is efficient, addition, deletion
are complex and this increase with frequent change in the list and nonlinear list
liketrees,graphs (space is more wasted and searchingalso increased)
Linkedlist
A linked list is an ordered collection of data in which each element contains the
location of thenext element/s. linkedlist contains two parts 1. Data and 2. Link.
Data is the value of the application to be processed and link the address/pointer
theidentifythe next element in the list, to chain the data together.
We can use the linked list to create the linear and nonlinear list, in linear list the
element has only zero or one successor, in nonlinear each element can have
zero,one or more successor.
It is easy to insert, delete when compared to array, no need to shift elements. No
longer physically sequenced
Overview of space and time complexity
By the performance of a program,wemean theamount of computer memory
and timeneededto run a program.
The space complexity of a program is the amount of memory it needs to run to
completion. Someof thereasons why we must know the space complexity,
1. To know whether thesufficient memory is available to run the program
2. In multi user system, to specify the amount of memory to beallocatedto
theprogram.
The time complexityof a program is the amount of computer time it needs to run
to completion. Some of thereasons whywemust know the timecomplexity,
1. The programweare developing might needto provide satisfactory
real-timeresponse.
2. If we have alternative ways to solvea problem, then the decision on which
to use will be based on primarily on heexpected performance difference
among these solutions.

Space complexity: space needed by a programhas thefollowingcomponents

1. Instruction space: it is the space needed to store the compiled version of
theprogram instructions
[Link] space: it is the space needed to store all constants variable values, it
has two components
a. Spaced needed byconstants andsimple variables
 [Link] needed by dynamically allocated objects such as arrays and other
instances.
[Link] Stack space: it is used to save information needed to resume
execution of partially completed functions and methods. For ex. If
function foo invokes function goo, then we must at least save a pointer
to the instruction of foo to beexecutedwhen goo terminates.
Time complexity
The time taken for compile time +run time
Compile time doesn’ t depend on the instance characteristics, similarly ones
compiled will run several times with out recompilation. So, we are concern with
run time tpwith instance characteristics.
If we knew the compiler time taken for add, sub, mul, division , load, store when
code performed for P on instance with characteristic n.
Further, int, float, etc., in addition, with modern computer memory hierarchy m
additions isn’ t necessarily m times to perform.
Approaches considered are, 1. Identify one or more key operations abd
determine the number of times these are performed and 2. Determine the total
number of steps executed bythe program.
Methods:
[Link] count: identify the operations and determine hominy of each is
done.
Ex. Selection sort,bubble sort
[Link] worst and averageoperation count:
Since the operation may not be same for every instance characteristics, we can
computebest, worst and averagecounts.(operation counts)
Linear search: best is 1 and the worst is n average is N+1/2
3. Step count
The operation-count method of estimating time complexity omits accounting for
the time spent on all but the chosen operations. In the step-count method, we
attempt to account for the time spent in all parts of the algorithm. As was the
case for operation counts,thestepcount is a function of the problem size.
A step is any computation unit that is independent of the problem size. Thus 10
additions can be one step; 100 multiplications can also be one step; but n
additions, where n is the problem size, cannot be one step. The amount of
computing represented by one step may be different from that represented by
another. For example, the entire statement
return a+b+b*c+(a+b-c)/(a+b)+4;
can be regarded as a single step if its execution time is independent of the
 problem size. We may also count a statement such as
x=y;
as a single step.
To determine the step count of an algorithm, we first determine the number of
steps per execution (s/e) of each statement and the total number of times (i.e.,
frequency) each statement is executed. Combining these two quantities gives us
the total contribution of each statement to the total step count. We then add the
contributions of all statements to obtain the step count for the entire algorithm
called profiling.
The s/e(steps for execution) of a statement is the amount by which stepcount
changes as a result of the execution of that statement. Difference between step
count ands/e can beseen in the example.

Ex. Sum of arrayvalues

intsum()
{
intsum=0;
for(inti=0;i<n;i++)
sum+=a[i];
returnsum;
}
Statement s/e frequency Total steps
intsum() 0 0 0
{ 0 0 0
Int sum=0; 1 1 1
for(i=0;i<n ;i++) 1 n+1 n+1
Sum+=a[i]; 1 N n
return sum; 1 1 1
} 0 0 0
Total 2n+3

Ex2. transpose
Voidtranspose()
{
For(int i=0; i<rows; i++)
For(int j=i+1; j<rows; j++)
Swap(a[i][j],a[j][i]);
 }
𝑟𝑜𝑤𝑠 − 1 𝑟𝑜𝑤𝑠

(𝑟𝑜𝑤𝑠 − 𝑖) = 𝑞 = 𝑟𝑜𝑤𝑠(𝑟
𝑟𝑜𝑤𝑠 + 1)/2
𝑖=0 𝑞=1

Statement s/e frequency Total steps

Void transpose() 0 0 0
{ 0 0 0
For(int i=0;i<rows;i++) 1 rows+1 rows+1
For(int j=i+1;j<rows;j++) 1 rows(rows+1)/2 rows(rows+1)/2
Swap(a[i][j],a[j][i]); 1 rows(rows-1)/2 rows(rows-1)/2
} 0 0 0
Total rows2+rows+1

Searching techniques:
It is a process of finding the location of a given elementin a set of elements. Or
It is designed to check for an element or retrieve an element from any data
structure where it is stored.
Or Searching is the process of fetching a specific element in a collection of
elements
The search is saidto be successful if thegiven element is found,i., the element
does exist in the collection (such as an array); otherwise,it is unsuccessful.
Two prominent search strategies are extensively used to find a specific item on a
list are as follows:
1. Linear or Sequential search
[Link] Interval search: designed for searching in sorted
data-structures, target the center of the search structure and divide
the search space in half.
Linear search: It is the technique for searching a given element/ item in the list
of elements by comparing each and every element in the list sequentially.
Algorithm:
 Linear Search ( ) //n is sizeof thearray,Arr is thenameof thearray, and
key is the searchedelement.
Step 1: start
Step 2: read n, Arr,key
Step 3: Set i to 0 // i is theindex of an array which starts from 0
Step 4: if i > n then go to step 9 // n is thenumber of elements in array
Step 5: if Arr[i] == key then go to step 8
Step 6: Set i = i + 1
Step 7: Goto step2
Step 8: Print elementa foundat index i and go to step 10
Step 9: Print element not found
Step 10: Exit
Program:
#include<stdio.h>
voidmain()
{
int n,array[n],key, c;
printf("Enter number of elements in array\n");
scanf("%d",&n);
printf("Enter %d integer(s)\n",n);
for (c = 0; c < n; c++)
scanf("%d",&array[c]);
printf("Enter a number to search\n");
scanf("%d",&key);
for (c = 0; c < n; c++)
{
if (array[c] == key) /* If required element is found */
{
printf("%d is present at location %d.\n",key, c+1);
break;
}
}
if (c == n)
printf("%disn't present in the array.\n", key);
 }
The Complexity of linear search : You havethree differentcomplexities faced
while performingLinear Search Algorithm,they are mentionedas follows.
1. Best Case
[Link] Case
[Link] Case
Best case complexity
 The element being searched couldbe found in the first position.
 In this case, the search ends with a single successful comparison.
 Thus,in the best-case scenario,thelinear search algorithm performs O(1)
operations.
Worst case complexity
 The element being searched may be at thelastposition in the arrayor not
at all.
 In the first case, the search succeeds in ‘n’ comparisons.
 In the next case, thesearch fails after ‘n’ comparisons.
 Thus,in the worst-casescenario, the linear search algorithmperforms
O(n) operations.
Average casecomplexity:
When the element to be searchedis in the middleof the array,the
average case of the Linear Search Algorithm is O(n).
Next,you will learn about the SpaceComplexity of Linear Search
Algorithm.
Space complexity: The linear search algorithm takes upno extra space;
its space is O(n) for an array of n elements.
Applications: The linearsearch algorithm has the followingapplications:
 Linear search can be appliedto both single-dimensional and
multi-dimensional arrays.
 Linear search is easyto implement and effective when the array contains
only a few elements.
 Linear Search is also efficient when thesearch is performed to fetch a
single search in an unordered-List.
Binarysearch
Binary searches are efficient algorithms based on the concept of
“divide and conquer” , The data structure must be sorted. It improves
the search by recursively dividing the array in half until you either find the
 element or the list gets narrowed down to one piece that doesn’ t
match theneeded element.
Let us consideran array arr= {1,5,7, 8, 13, 19, 20, 23,29}. Find the
location of theitem23 in the array.
In 1st step :
1. BEG = 0
[Link] =8
[Link]= 4
4.a[mid] =a[4] = 13 < 23, therefore
In 2nd step:
5. Beg= mid +1 = 5
[Link]= 8
7. mid = 13/2 = 6
8. a[mid] = a[6] = 20 < 23,therefore;
In 3rd step:
[Link]= mid + 1 = 7
[Link]= 8
10. mid = 15/2 = 7
11. a[mid] = a[7]
12. a[7] = 23 = item;
13. therefore,set location = mid;
14. The location of the item will be 7.
Algorithm: Binary search()
step 1: start
step 2: read sorted array, n , key,
step 3: assign first=0,last= n-1
step 4: repeat until first <= last
step 5: compute mid = (first+last)/2 (the mid position in an array)
step 6: if key == array[mid] else goto step6
step 7: write key found go to step 14.
Step 8: If the key < middle element else goto step 10
Step 9: assign last= mid-1
Step 10: go to step4 in left half.
Step 11: assign first=mid+1
Step 12: go to step 4 in right half
Step 13: write key not found
Step 14: stop
Binary searches work under the principle of using the sorted information in the
array to reduce thetime complexityto zero (Log n). Here are the binary search
approach’ s basic steps:
 Begin with an interval that covers theentire array
 If the search key value is less than the middle-interval item, narrow the
interval to that lower half. Otherwise, narrow the interval to the upper
half.
 Keep checking the chosen interval until eit her the value is found or the
interval’ s empty
Time Complexity:
 Best Case: O(1)
 Average Case: O(log N)
 Worst Case: O(log N)
Auxiliary Space: O(1), If the recursive call stack is considered then the auxiliary
space will be O(logN).
Advantages of Binary Search:
Binary search is faster than linear search, especially for large arrays.
 More efficient than other searching algorithms with a similar time
complexity, such as interpolation search or exponential search.
 Binary search is well-suited for searching large datasets that are stored
in external memory, such as on a hard drive or in the cloud.
Drawbacks of Binary Search:
 The array should be sorted.
 Binary search requires that the data structure being searched be stored
in contiguous memory locations.
 Binary search requires that the elements of the array be comparable,
meaning that they must be able to be ordered.
Applications of Binary search:
Binary search can be used as a building block for more complex algorithms
used in machine learning, such as algorithms for training neural networks or
finding the optimal hyperparameters for a model.
 It can be used for searching in computer graphics such as algorithms for
ray tracing or texture mapping.
 It can be used for searching a database.
Program:
#include<stdio.h>
voidmain()
{
int i, low, high,mid, n, key,array[100];
printf("Enternumber of elements");
scanf("%d",&n);
printf("Enter%dintegers", n);
for(i = 0; i < n; i++)
scanf("%d",&array[i]);
printf("Entervalue to find");
scanf("%d",&key);
low = 0;
high = n - 1;
mid = (low+high)/2;
while (low<= high) {
if(array[mid]<key)
low = mid+ 1;
elseif (array[mid] == key) {
printf("%dfound atlocation %d", key,mid+1);
break;
}
else
high = mid - 1;
mid = (low + high)/2;
}
if(low>high)
printf("Not found! %disn't present in the list",key);
}
 Sequential Search Binary Search
Finds thekey present at firstposition Finds the keypresent at centre
in constant time position in constant time
Sequenceof elements in the container The elements mustbe sorted in the
doesnotaffect. container
Arrays andlinked lists can be usedto It cannotbe implemented directly into
implementthis thelinked list. We need to changethe
basic rules ofthe list to implement
this
Algorithm is iterativein nature Algorithm technique is Divideand
Conquer.
Algorithm is easyto implement, and Algorithm is slightly complex. It takes more
requires less amount of code. amount of codeto implement.
N number of comparisons are Log n number of comparisons are
requiredforworst case. sufficientin worst case.
Time complexityis O(n) Timecomplexityis O(logn)

Sorting:
Sorting is a process in which items arearrangedsystematically
(or)
Sorting is the process of arranging data into meaningful order so that
you can analyze it more effectively
Types of sorting: bubble sort, selection sort, insertion sort, merge sort, Quick sort
etc.
Bubble sort: Bubble Sort is the simplest sorting algorithm that works by
repeatedly swapping the adjacent elements if they are in the wrong order.
It is also known as sinking sort.
 traverse from left and compare adjacent elements and the higher
one is placed at right side.
 In this way, the largest element is moved to the rightmost end at
first.
 This process is then continued to find the second largest and place
it and so on until the data is sorted.
Algorithm:
Step 1: Start
Step 2: Read array,n,temp=0
Step 3: Repeat steps 4 until i<n else go to step 9
Step 4: Repeat steps 5 to 8 until j<n-i-1 else go to step 3
Step 5; If array[j]>array[j+1] else go to step 4
Step 6: Temp=array[j]
Step 7: Array[j]=array[j+1]
Step 8: Array[j+1]=temp
Step 9: write array is sorted.
Step 10: stop

 Total no. of passes: n-1, n-2, … .2,1, This is an arithmetic series, and the
equation for the total number of times is (n - 1)*n / 2.
 Total no. of comparisons: n*(n-1)/2

Time Complexity:
 Worst Case Complexity: If the array elements are in descending order and
we want to make it in ascending order, it is the worst case. The time
complexityforthe worst case is O(n²).
 Best Case Complexity: The best case is when all the elements are already
sorted, and no swapping is required. The time complexity in this scenario
is O(n).
 Average Case Complexity: This is the case when the elements are
jumbled. The timecomplexity for theaverage case in bubble sort is O(n²).
 Space Complexity
 Space complexit yfor the standard bubble sort algorithm is O(1) as thereis
one additional variable required to hold the swapped elements
temporarily.
 Space complexity for optim ized implementation of the bubble sort
algorithm is O(2). This is because two additional variables are required.

Selection sort
The algorithm repeatedly selects the smallest (or largest) element from the
unsorted portion of the list and swaps it with the first element of the unsorted
part. This process is repeated for the remaining unsorted portion until the entire
list is sorted.
In selection sort, the smallest value among the unsorted elements of the array is
selected in every pass and inserted to its appropriate position into the array. It is
also the simplest algorithm. It is an in-place comparison sorting algorithm. In this
algorithm, the array is divided into two parts, first is sorted part, and another one
is the unsorted part. Initially, the sorted part of the array is empty, and unsorted
part is the given array. Sorted part is placed at the left, while the unsorted part is
placed at theright.
Ex.

In selection sort, the first smallest element is selected from the unsorted array
and placed at the first position. After that second smallest element is selected
and placed in the second position. The process continues until the array is
entirely sorted.
Algorithm:
SELECTIONSORT(arr, n)
Step 1: start
Step 2: read array, n, pos, temp
Step 3: Repeat Steps 4 to 9 until i < n
Step 4: assign pos=i, j=i+1
Step 5: repeat steps 6 to 7 until j<n else goto step 8
Step 6: if array[pos]>array[j] else go to step8
Step 7: pos=j
Step 8: if pos!= i else go to step3
Step 9: SWAP arr[i] with arr[pos] use temp variable, go to step3
Step 10: write sorted array values
Step 11: stop
Program:
#include<stdio.h>
void main() {
int n, arr[n];
int i, j, position,swap;
printf("Enter thesizeof thearray: ");
 scanf("%d",&n);
printf("Enter %d elements: ", n);
for(i= 0; i < n; i++)
{
scanf("%d",&arr[i]);
}
for (i= 0; i < (n - 1); i++){
position = i;
for (j = i + 1; j < n; j++) {
if (arr[position] > arr[j])
position = j;
}
if (position != i) {
swap = arr[i];
arr[i] = arr[position];
arr[position] = swap;
}
}
for (i= 0; i < n; i++)
printf("%d\t",arr[i]);
}
Complexity Analysis of Selection sort
Time Complexity: The time complexity of Selection Sort is O(N2) as there are
two nested loops:
 One loop to select an element of Array one by one = O(N)
 Another loop to compare that element with every other Array element =
O(N)
 Therefore overall complexity = O(N) * O(N) = O(N*N) = O(N2)

Auxiliary Space: O(1) as the only extra memory used is for temporary variables
while swapping two values in Array. The selection sort never makes more than
O(N) swaps and can be useful when memory writing is costly.
Advantages:
 Simple and easy to understand.
 Works well with small datasets.
Disadvantages:
 Selection sort has a time complexity of O(n^2) in the worst and average
case.
 Does not work well on large datasets.
 Does not preserve the relative order of items with equal keys which
means it is not stable.

Insertion Sort Program:

#include<stdio.h>
voidmain()
{
int n, a[n],temp,i, j;
printf("Enter number of elements\n");
scanf("%d",&n);
printf("Enter %d integers\n", n);
for (i = 0; i < n; i++)
scanf("%d",&a[i]);
for (i = 1; i < n; i++) {
temp = a[i];
j = i - 1;
while(j>=0 && temp <= a[j]) /* Move the elements greater than
temp to one position ahead from their current position*/
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
for (i = 0; i < n; i++)
printf("%d", a[i]);
}

Time Complexity
Case Time Complexity
Best Case O(n)
 Average Case O(n2)
Worst Case O(n2)
o Best Case Complexity - It occurs when there is no sorting required, i.e.
the array is already sorted. The best-case time complexity of insertion
sort is O(n).
o Average Case Complexity -It occurs when the array elements are in
jumbled order that is not properly ascending and not properly
descending. The average case time complexity of insertion sort is O(n2).
o Worst Case Complexity - It occurs when thearrayelements are required
to be sorted in reverse order. That means suppose you have to sort the
array elements in ascending order, but its elements are in descending
order. The worst-casetime complexity of insertion sort is O(n2).
2. Space Complexity
Space Complexity O(1)
Stable YES
o The space complexity of insertion sort is O(1). It is because, in insertion
sort, an extra variable is required for swapping.
Note check space and time complexities of linear, binary, bubble,
insertion,selection.
Insertion Sort Algorithm
Now we havea bigger picture of how this sorting techniqueworks,so we
can derive simple steps by which we can achieve insertion sort.
Step 1 − If it is thefirst element, it is alreadysorted. return 1;
Step 2 − Pick next element
Step 3− Compare with all elements in thesorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than
thevalue to be sorted
Step 5 − Insert thevalue
Step 6 − Repeat until list is sorted
Pseudocode
Algorithm: Insertion-Sort(A)
for j = 2 to [Link]
key = A[j]
i=j– 1
 whilei > 0 and A[i]>key
A[i + 1] = A[i]
i = i -1
A[i + 1] = key
Analysis
Run timeof this algorithm is verymuch dependent on the given input.
If the given numbers are sorted, this algorithm runs in O(n) time. If the
given numbers are in reverse order, the algorithm runs in O(n2) time.
Example
We take an unsortedarrayforour example.

Insertion sort compares the first two elements.

It finds that both 14 and 33 are already in ascending order. For now, 14 is
in sorted sub-list.

Insertion sort moves ahead andcompares 33 with 27.

And finds that 33 is not in the correct position. It swaps 33 with 27. It
also checks with all the elements of sorted sub-list. Here we see that the
sorted sub-list has only one element 14, and 27 is greater than 14.
Hence,thesortedsub-list remains sorted after swapping.
By now we have 14 and 27 in the sorted sub-list. Next, it compares 33
with 10. Thesevalues are not in a sortedorder.

So they are swapped.

However,swapping makes 27 and10 unsorted.

Hence,we swapthem too.

Again we find 14 and 10 in an unsorted order.

We swap them again.

By the end of third iteration, wehave a sorted sub-list of 4 items.

This process goes on until all the unsorted values arecovered in a sorted
sub-list. Now weshall seesome programming aspects of insertion sort.