Data Structure

Unit 1
Array
Dattatray G. Takale
[Link]@[Link]
Department of Computer Engineering

BRACT’S, Vishwakarma Institute of Technology, Pune-37

(An Autonomous Institute affiliated to Savitribai Phule Pune University)
(NBA and NAAC accredited, ISO 9001:2015 certified)
 Syllabus of this Subject
Unit 1:Arrays Unit 2: Linked Lists

Algorithms: Asymptotic Notations, Time and Space Complexity Dynamic memory allocation, Singly Linked Lists, Doubly linked Lists,
Arrays: Introduction, Memory Representation and application of Single Circular linked lists and Generalized linked lists, Applications of Linked
and Multidimensional arrays, Sparse Matrix. list, introduction to Vectors and Application.
Searching and sorting techniques: Linear Search, Binary search with
Analysis.
Sorting Techniques: Bubble Sort, Insertion Sort, Merge Sort, Quick
Sort with Analysis and passes.

Unit 3: Stacks and Queues Unit 4: Trees

Stack: Stack representation and Implementation using arrays and Linked Basic terminology, representation using array and linked lists. Tree
lists. Applications of stack in Recursion, Expression conversions and Traversals: Recursive and Non recursive, Operations on binary tree.
evaluations. Binary Search trees (BST).
Queues: Representation and implementation using array and Linked
lists, Types of queue. Applications of Queues: Job Scheduling, Josephus
problem etc.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 2

 Syllabus of this Subject
Unit 5: Graphs Unit 6: Hashing

Terminology and representation using Adjacency Matrix and Adjacency Hashing techniques, Hash table, Hash functions. Collision handling and
Lists, Graph Traversals and Application: BFS and DFS, Connected Collision resolution techniques.
graph, Bipartite Graph, Detecting Cycle in graph. Minimum Spanning
tree: Prims and Kruskal’s Algorithm, Shortest Path Algorithms, Union
Find.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 3

 Objective/s of this session

1. Understand Basic Concept of Programming

2. To Understand Concept of Data Structure and its types .

Learning Outcome/Course Outcome

1. Differentiate Data structure and analyze and synthesize time and space
complexity of algorithm.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 4

 Session Content

1. Algorithms (Logic Building)

2. Asymptotic Notation
3. Data Structure
4. Types of Data Structure
5. Linear vs. Non- Linear, Static vs. Dynamic, Persistent vs. Ephemeral

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 5

 What is Data Structure

DSA is defined as a combination of two separate yet interrelated topics: Data Structure and Algorithms.

Data Structure:
Way to arrange Data in main Memory for efficient way A data structure is defined as a particular way of storing
and organizing data in our devices to use the data efficiently and effectively. The main idea behind using data
structures is to minimize the time and space complexities. An efficient data structure takes minimum memory space
and requires minimum time to execute the data.

Algorithms
Algorithm is defined as a process or set of well-defined instructions that are typically used to solve a particular
group of problems or perform a specific type of calculation. To explain in simpler terms, it is a set of operations
performed in a step-by-step manner to execute a task.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 6

 What is Data Structure
Algorithms
An algorithm is a step-by-step procedure or set of rules to solve a specific problem in a finite amount of time

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 7

 Algorithm Design Tools: Flowcharts and
Pseudocode
A flowchart is a visual representation of an algorithm using symbols and shapes to illustrate the steps and logical
flow of a process.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 8

Algorithm Design Tools: Flowcharts and
Pseudocode

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 9

 Algorithm Design Tools: Flowcharts and
Pseudocode
Advantages of Flowchart:

Visual Representation: Easy to understand and follow.

Structured Design: Facilitates systematic problem-solving.
Documentation: Useful for explaining and recording algorithms.

Disadvantages of Flowcharts

Limited Detail: May not capture complex programming logic fully.

Space Constraints: Large algorithms may require significant space and become cluttered.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 10

Algorithm Design Tools: Flowcharts and
Pseudocode

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 11

 Algorithm Design Tools: Flowcharts and
Pseudocode
Pseudocode is a simple way to write the steps of a program or algorithm using plain English mixed with
programming ideas. It is not an actual programming language, but it helps you plan your code before writing
it.

Key Elements:
Variables: Used to represent data.
Operations: Basic operations like assignments, arithmetic, and comparisons.
Control Structures: If-else statements, loops, and conditional constructs.
Functions/Procedures: Representing modular parts of the algorithm.

Examples: Calculate the sum of numbers in a list.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 12

 Homework on Algorithms Desing Tool

1. Design a flowchart and write pseudocode to sum of two number

2. Design a flowchart and write pseudocode for area of Square

3. Design a flowchart and write pseudocode Min and Max from 2 Number

4. Design a flowchart and write pseudocode to check whether a given number is even or odd

5. Design a flowchart and write pseudocode to Calculate Sum of N Natural Numbers

6. Design a flowchart and write pseudocode to Calculate Factorial of a Number

7. Design a flowchart and write pseudocode to Is number is Prime or not

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 13

 Asymptotic Notation

Asymptotic notation is used to describe the running time or space requirement of an algorithm in terms of
input size (n), particularly when n becomes very large.
It gives a mathematical way to compare algorithm efficiency, ignoring machine-dependent constants and
lower order terms.
Why do we need it?
We want to know which algorithm is faster when data is huge.
We ignore small differences and focus only on growth rate.
There are mainly three asymptotic notations:

• Big-O notation

• Omega notation

• Theta notation

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 14

 Asymptotic Notation

The efficiency of an algorithm depends on the amount of time, storage and other resources required to execute the
algorithm. The efficiency is measured with the help of asymptotic notations.

Big-O Notation (O-notation): Big-O notation represents the upper bound of the running time of an algorithm.
Thus, it gives the worst-case complexity of an algorithm.

O(g(n)) = { f(n): there exist positive constants c and n0

such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 15

 Asymptotic Notation

Omega Notation (Ω-notation): Omega notation represents the lower bound of the running time of an algorithm.
Thus, it provides the best case complexity of an algorithm.

Ω(g(n)) = { f(n): there exist positive constants c and n0 such

that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 16

 Asymptotic Notation

Theta Notation (Θ-notation): Theta notation encloses the function from above and below. Since it represents the
upper and the lower bound of the running time of an algorithm, it is used for analyzing the average-case
complexity of an algorithm.

Θ(g(n)) = { f(n): there exist positive constants c , c 1 2

and n such that 0 ≤ c g(n) ≤ f(n) ≤ c g(n) for all n ≥ n }

0 1 2 0

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 17

 Asymptotic Notation

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 18

 What is Data Structure

A data structure is a way of storing and organizing data in computer memory so that it can be used efficiently.
• To organise data systematically
• To perform operations like searching, sorting, and updating quickly
• To save memory and time, making programs efficient
• For better problem solving in programming and real-life applications

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 19

 Real Time Application of Data Structure

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037 20

 Classification Of Data Structures
Data Structures

Primitive Data Structures Non-Primitive Data Structure

Integer Float Character Pointer

Linear Data Structure Non-Linear Data
Structure

Array Linked List Stack Queue Tree Graph Files

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

Primitive Data Structure:

These are basic data types provided by programming languages as building blocks.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

Non- Primitive Data Type:
These are complex data structures built using primitive types, used to organize and manage
large data efficiently.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

Sr. No. Key Linear Data Structures Non-linear Data Structures
Basic built-in data types provided by Complex data structures derived from primitive
1 Definition
programming languages. types to store large and connected data efficiently.
Arrays, Linked Lists, Stacks, Queues, Trees,
2 Examples int, char, float, double, bool
Graphs, Hash Tables

Can be linear (array, linked list) or non-linear (tree,

3 Nature Simple, atomic data items
graph)

Requires user-defined operations and

4 Operations Directly operated by machine instructions
implementation logic

Size can be fixed (array) or dynamic (linked list,

5 Memory Size Fixed size depending on data type
tree)

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

Sr. No. Key Linear Data Structures Non-linear Data Structures
Linear data structures are not very
Non-linear data structures uses
6 Memory utilization memory friendly and are not utilizing
memory very efficiently.
memory efficiently.
Time complexity of non-linear data
Time complexity of linear data structure
7 Time Complexity structure often remain with increase in
often increases with increase in size.
size.
Tree
Array

8 Examples Graph
Linked List

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

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.
• provides more easier access to elements with respect to dynamic data structure
• Example of Static Data Structures: Array( int a[5] )
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 facilitate change of data structures in the run time.
• flexible
• Example of Dynamic Data Structures: Linked List

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

Persistent data structure
• data structure that always preserves the previous version of itself when it is modified.
• immutable, as their operations do not (visibly) update the structure in-place, but
instead always yield a new updated structure.
• A data structure is partially persistent if all versions can be accessed but only the
newest version can be modified.
• The data structure is fully persistent if every version can be both accessed and
modified.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

Ephemeral data structure
• An ephemeral data structure is one for which only one version is available at a time:
after an update operation, the structure as it existed before the update is lost.
• mutable, as their operations update the structure in-place, so new updated structure can
be accessed and modified .

• In imperative languages, most data structures are ephemeral. a=5,15

Persistent structure
• multiple versions are simultaneously accessible: after an update, both old and new
versions can be used.
• immutable, as their operations do not (visibly) update the structure in-place, but instead
always yield a new updated structure. So old and new updated structure can be
accessed and modified .
• In functional languages, data structures are persistent

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Types of Array
A one-dimensional array is a data structure that stores elements of the same
type in a linear sequence. It's a fundamental concept in computer
programming and is widely used in various algorithms and applications.
In a one-dimensional array:
[Link]: Elements are stored sequentially in memory.
[Link]: Each element is accessed using its index, which represents its
position in the array. The index typically starts from 0 or 1, depending on
the programming language.
[Link]: The size of the array is fixed at the time of declaration in most
programming languages, although dynamic arrays are available in some
languages like C++.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 1D Array

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Array implementation of a List

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Storage representation of 1D Array

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Address Calculation in 1D Array

• Address of an element of an array say “A[ I ]” is calculated using the

following formula:
Address of A [ I ] = B + W * ( I – LB )
Where,
B = Base address
W = Storage Size of one element stored in the array (in byte)
I = Index of element whose address is to be found
LB = Lower limit / Lower Bound of subscript, if not specified assume
0 (zero) This specifies the starting index of the array. If not specified,
it's assumed to be 0 (zero).

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Contd…Address Calculation in 1D Array
Example
Given the base address of an array B[1300…..1900] as 1020 and size of
each element is 2 bytes in the memory. Find the address of B[1700].
Solution:
• The given values are: B = 1020, LB = 1300, W = 2, I = 1700
• Address of A [ I ] = B + W * ( I – LB )
• = 1020 + 2 * (1700 – 1300)
= 1020 + 2 * 400
= 1020 + 800
= 1820 [Ans]

Dr. Dattatray G. Takale,

Dr. Takale Department
D.G, Department of of Computer
Computer engineering,
Engineering, VIT,Pune-48
VIIT, Pune- 411037
 Two-Dimensional Array
A two-dimensional array, also known as a 2D array, is a data structure that stores elements in a grid format with
rows and columns. Each element in a 2D array is identified by two indices - typically representing the row index
and the column index.
Here's a general overview of a two-dimensional array:
[Link] and Columns: The array is organized into rows and columns. Each row has a fixed number of elements,
and all rows have the same number of elements. Similarly, each column has a fixed number of elements, and all
columns have the same number of elements.
[Link]: To access an element in a 2D array, you need to specify the row index and the column index. The
indices usually start from 0 and go up to the size of the array minus one.
[Link] Structure: Two-dimensional arrays have a rectangular structure, meaning they form a grid with
equal-sized rows and columns.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Two-Dimensional Array

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Two-Dimensional Array

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Storage Representation of 2D Array

➢ While storing the elements of a 2-D array in

memory, these are allocated contiguous memory
locations.

➢2-D array must be linearized so as to enable their

storage.

➢There are two alternatives to achieve

linearization: Row-Major and Column-Major.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Row Major Representation

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Column Major Representation

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Address Calculation in 2D Array

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Contd.. Address Calculation in 2D Array
Example
• Assuming base address(B) to be 100 and W = 1 byte calculate the
address of A[2][1] in row major arrangement

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Contd.. Address Calculation in 2D Array
Example
• Assuming base address(B) to be 100 and W = 1 byte calculate the
address of A[2][1] in column major arrangement

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Note

• Usually number of rows and columns of a matrix are given ( like

A[20][30] or A[40][60] )
• If it is given as A[Lr- – – – – Ur, Lc- – – – – Uc], in this case number
of rows and columns are calculated using the following methods:
Number of rows (M) will be calculated as = (Ur – Lr) + 1
Number of columns (N) will be calculated as = (Uc – Lc) + 1
• Rest of the process will remain same as per requirement (Row Major
Wise or Column Major Wise).

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Exercise
Q 1. An array X [-15……….10] [15……………40] requires one byte
of storage. If beginning location is 1500 determine the location of X
[15][20].
Solution:
• As you see here the number of rows and columns are not given in the
question. So they are calculated as:
• Number or rows say M = (Ur – Lr) + 1 = [10 – (- 15)] +1 = 26
Number or columns say N = (Uc – Lc) + 1 = [40 – 15)] +1 = 26

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Exercise Solution
(i) Column Major Wise Calculation of above equation
The given values are: B = 1500, W = 1 byte, I = 15, J = 20, Lr = -15, Lc = 15, M = 26
Address of A [ I ][ J ] = B + W * [ ( I – Lr ) + M * ( J – Lc ) ]
= 1500 + 1 * [(15 – (-15)) + 26 * (20 – 15)]
= 1500 + 1 * [30 + 26 * 5] = 1500 + 1 * [160]
= 1660 [Ans]

(ii) Row Major Wise Calculation of above equation

The given values are: B = 1500, W = 1 byte, I = 15, J = 20, Lr = -15, Lc = 15, N = 26
Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]
= 1500 + 1* [26 * (15 – (-15))) + (20 – 15)]
= 1500 + 1 * [26 * 30 + 5] = 1500 + 1 * [780 + 5] = 1500 + 785
= 2285 [Ans]

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Sparse Matrices using Array
What is Sparse Matrix?
Sparse matrix is a matrix which contains very few non-zero elements.
• Sparse Matrix Representations
• A sparse matrix can be represented by using TWO representations, those are
as follows...
• Triplet Representation (Array Representation)
• Linked Representation

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Matrix Addition

1 2 3 1 2 3 1 2 3
1 3 0 2 1 0 13 10 1 3 13 12
2 0 5 0 + =
2 0 0 0 2 0 5 0
3 1 0 0 3 8 0 4 3 9 0 4

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Sparse Matrix Addition

0 3 3 4 0 3 3 4 0 3 3 7
1 1 1 3 1 1 2 13 1 1 1 3
2 1 3 2
+ =
2 1 3 10 2 1 2 13
3 2 2 5 3 3 1 8 3 1 3 12
4 3 1 1 4 3 3 4 4 2 2 5

5 3 1 9

6 3 3 4

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Matrix Transpose

1 2 3 1 2 3
1 0 5 0 1 0 8 0
➔
2 8 0 1 2 5 0 0
3 0 0 2 3 0 1 2

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Sparse Matrix Simple Transpose

0 3 3 4 0 3 3 4

1 1 2 5 1 1 2 8

2 2 1 8 2 2 1 5
➔
3 2 3 1 3 3 2 1

4 3 3 2 4 3 3 2

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Running Time Analysis of Simple Transpose

• If there are n columns in m x n matrix and the number of non zero values
are ‘t’, the total running time using simple transpose method is O(nt)

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Sparse Matrix Fast Transpose

Number of elements in each column of A Starting index of each row in T

1 2 3 1 2 3
1 2 1 1 2 4

0 3 3 4 0 3 3 4
1 1 2 5 1 1 2 8
2 2 1 8 ➔ 2 2 1 5
3 3 2 1 3 2 3 1
4 3 3 2 4 3 3 2

A T
Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037
 Fast Transpose Algorithm

• Find the number of elements in column of A

• This gives elements in each row of T
• Using it, calculate starting position (index) of each row in T
• Move each element of A one by one to its correct position in T

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Fast Transpose –Pseudo Code
int i, j ,m, n, pos[3]={0,0,0},count[3]={0,0,0}
for i=1 to B[0][3]
m = B[i][2]
count[m]++
pos[0] = 1;
for i=1 to B[0][2]
pos[i] = pos [i-1] + count[i-1];

for i=1 to B[0][3]

m = B[i][2];
n= pos[m];
pos[m]++;
C[n][1] = B[i][2];
C[n][2] = B[i][1];
C[n][3] = B[i][3];
C[0][0] = B[0][0];
C[0][1] = B[0][1];
C[0][2] = B[0][2] ;
Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037
 Running Time Analysis of Fast Transpose
• Steps taken to find number of elements in each column of A = n (assuming m
x n matrix)

• Steps taken to compute starting positions of each row in transposed matrix T =

n

• Elements of original matrix are copied into T in t steps

• Total steps = n+n+t = O(2n+t) = O(n+t)

• If t is of order of nm, then running time for simple transpose becomes O(nm)

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Polynomial representation using Array
• Array representation assumes that the exponents of the given
expression are arranged from 0 to the highest value (degree), which is
represented by the subscript of the array beginning with 0.
• The coefficients of the respective exponent are placed at an
appropriate index in the array.
• The array representation for the below polynomial expression P(x)
= x2 − 4x + 7 is
0 1 2
7 -4 1

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Polynomial Addition using Array

add(A[0..m-1], B[0..n01])
1) Create a sum array sum[] of size equal to maximum of 'm' and 'n‘
2) Copy A[] to sum[].
3) Traverse array B[] and do following for every element B[i]
sum[i] = sum[i] + B[i]
4) Return sum[].

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Searching
• Searching is a fundamental operation in computer science and data
structures.
• It involves finding a particular element within a collection of data. This
could be locating a specific value in an array, a key in a dictionary, or an
entry in a database.
• In the context of data structures, there are various algorithms and
techniques designed to efficiently perform searches, depending on the
structure of the data.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Searching Examples
• Problem: Suppose you have a sorted array of integers and you want to
find the index of a particular number within the array.
• Example Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Number to Search for: 23

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Important of Searching
Searching is important for various reasons:
1. Data Retrieval: Searching allows us to retrieve specific information or elements from a large collection
of data efficiently. Whether it's finding a contact in an address book, a book in a library, or a record in a
database, searching enables us to access the desired information quickly.
2. Information Retrieval Systems: In information retrieval systems such as search engines, searching
plays a critical role in retrieving relevant documents or web pages based on user queries. Efficient
searching algorithms are essential for providing timely and accurate search results, which is crucial for
user satisfaction.
3. Algorithm Design and Optimization: Searching algorithms are fundamental components of many
other algorithms and data structures. Understanding and implementing efficient searching techniques are
essential for designing optimized algorithms and systems across various domains, including computer
science, engineering, and data analysis.
4. Database Operations: In databases, searching is essential for querying and retrieving data based on
specific criteria. Efficient indexing and searching algorithms improve the performance of database
operations, enabling faster data retrieval and processing.
5. Problem Solving: Searching algorithms are commonly encountered in problem-solving scenarios, such
as pathfinding in graphs, scheduling tasks, and optimizing resource allocation. Efficient searching
techniques contribute to solving complex problems effectively and finding optimal solutions.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Application of Searching
1. Web Search Engines: Search engines like Google, Bing, and Yahoo use sophisticated algorithms to retrieve relevant web pages in
response to user queries These systems crawl the web, index web pages, and use complex ranking algorithms to present search
results based on relevance, authority, and user preferences.
2. E-commerce Platforms: E-commerce websites like Amazon, eBay, and Alibaba rely heavily on searching to enable users to find
products quickly Users can search for products by entering keywords, and the platform returns relevant results from a vast catalog
of items. Advanced filtering and recommendation systems further enhance the searching experience by suggesting relevant
products based on user preferences and browsing history.
3. Social Media Platforms: Social media platforms such as Facebook, Twitter, and LinkedIn use searching to help users find other
users, posts, or topics of interest. Users can search for specific profiles, posts, hashtags, or topics, and the platform retrieves
relevant content based on the search query.
4. Navigation and Maps: Navigation applications like Google Maps, Waze, and Apple Maps utilize searching to help users find
locations, addresses, points of interest, and directions. Users can search for specific destinations, landmarks, businesses, or
services, and the application provides navigation instructions and route suggestions.
5. Healthcare Systems: Healthcare systems and electronic health records (EHRs) use searching to retrieve patient records, medical
histories, diagnostic reports, and treatment plans. Healthcare providers can search for specific patient information, lab results,
medications, or medical images to aid diagnosis and treatment decisions.
6. Enterprise Search: Large organizations use enterprise search solutions to index and search internal documents, emails,
presentations, and other digital assets. Employees can search for documents, files, or information stored across various systems
and repositories, improving productivity and knowledge management.
7. Legal and Research Databases: Legal professionals and researchers use specialized search platforms to search for case law,
statutes, regulations, scholarly articles, and other legal or academic documents. These platforms provide advanced search
capabilities, including boolean operators, filters, and citation indexing, to facilitate precise and comprehensive searching.
8. Customer Support Systems: Customer support platforms use searching to help agents quickly find relevant information, FAQs,
knowledge base articles, or previous support tickets related to customer inquiries. Searching enables efficient resolution of
customer issues, reduces response times, and improves customer satisfaction.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 How to Find Out
There are several techniques for searching data efficiently, each suited for
different scenarios based on factors like data structure, size of the dataset,
and the nature of the search. Here are some commonly used searching
techniques
1. Linear Search
2. Binary Search

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Linear Search
• Linear search is a straightforward searching algorithm that iterates through
each element of a collection (such as an array or a list) sequentially until
the desired element is found or the end of the collection is reached. It is
the simplest searching algorithm and is suitable for small datasets or
unsorted collections.
• Problem: Given an array of integers and a target element , If such a
element exists, return their indices; otherwise, return -1.
Example:
• Array: [5, 8, 12, 6, 3, 7]
• Target Sum: 13
• Expected Output: -1

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Linear Search Algorithms
• Algorithm:
[Link] from the first element of the collection.
[Link] each element with the target element.
[Link] the element matches the target, return its index.
[Link] the element does not match, move to the next element.
[Link] steps 2-4 until the target is found or the end of the collection is
reached.
[Link] the target is not found after iterating through all elements, return -1 or
an indication that the target is not present.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Linear Search Code

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Time Complexity Linear Search

• The time complexity of linear search is O(n), where n is the number of

elements in the array.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Disadvantages of Linear Search
1. Time Complexity: The time complexity of linear search is O(n), where n is the number of elements in
the array. This means that as the size of the array increases, the time taken by linear search also increases
linearly. For large datasets, linear search may not be efficient compared to algorithms with better time
complexities like binary search O(logn)).
2. Performance: Linear search may be slow for large datasets or when the target element is located
towards the end of the array. This is because linear search needs to traverse the entire array sequentially,
making n comparisons in the worst-case scenario.
3. Not Suitable for Sorted Data: Linear search does not require the data to be sorted beforehand. While
this can be an advantage in some cases, it also means that linear search cannot take advantage of sorted
data to improve efficiency. Algorithms like binary search are more suitable for sorted arrays due to their
logarithmic time complexity.
4. Inefficient for Unsorted Data: Even though linear search can work on unsorted arrays, its performance
is not optimized for such data. In scenarios where the data is unsorted, other searching algorithms may
provide better performance.
5. No Early Termination: Linear search always needs to iterate through all elements of the array, even if
the target element is found early in the search process. This lack of early termination can result in
unnecessary comparisons, especially when the target element is located near the beginning of the array.
6. Not Suitable for Large Datasets: In applications where efficiency is critical, such as searching in large
databases or real-time systems, linear search may not scale well due to its O(n) time complexity. More
efficient searching algorithms are preferred in such cases.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Binary Search Algorithms
Binary Search is defined as a searching algorithm used in a sorted array
by repeatedly dividing the search interval in half. The idea of binary
search is to use the information that the array is sorted and reduce the time
complexity to O(log N).

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Steps of Binary Search
1. Sort the Array: Ensure that the array is sorted in ascending order. Binary search only works on sorted
arrays
2. Initialize Pointers: Set two pointers, low and high, initially pointing to the start and end of the array,
respectively.
3. Find the Midpoint: Calculate the midpoint of the array by averaging the low and high indices (using
integer division).
4. Compare with the Target: Compare the value at the midpoint with the target value.
o If the value at the midpoint is equal to the target, the search is successful. Return the index of the
midpoint.
o If the value at the midpoint is greater than the target, update the high pointer to just before the midpoint
and repeat step 3
o If the value at the midpoint is less than the target, update the low pointer to just after the midpoint and
repeat step 3
5. Repeat: Continue steps 3 and 4 until the target value is found or the low pointer exceeds the high pointer.
6. Termination: If the pointers cross without finding the target value, the search terminates, and the target
value is not in the array.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Algorithms for Binary Search

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Code using C++

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Importance Binary Search Algorithms
[Link]: Binary search has a time complexity of O(log n), where n is the number of
elements in the array. This makes it significantly faster than linear search, especially for
large datasets. It's particularly useful when dealing with large collections of data where
efficiency is critical.
[Link] Space Complexity: Binary search operates on the original array without
requiring additional data structures, resulting in optimal space complexity. This makes it
memory-efficient compared to other search algorithms that might need additional storage.
[Link]: Binary search is not limited to just arrays; it can also be adapted for use on
other data structures like trees and graphs, provided they are sorted appropriately. This
versatility allows its application in various contexts beyond simple array searching.
[Link]: While binary search might seem complex at first, its underlying principles are
relatively straightforward. Once understood, it's a concept that can be applied in various
programming scenarios.
[Link]: Binary search is extensively used in fields such as computer science, data
analysis, database management, and more. It's employed in tasks ranging from searching for
items in databases to locating elements in sorted collections.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Time Complexity Binary Search Algorithms
The time complexity of the binary search algorithm is O(log n), where n is
the number of elements in the sorted array being searched.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Difference Between Linear and Binary Search

Feature Linear Search Binary Search

Divides the search space
Sequentially scans each
Approach by comparing with the
element in the array
middle element
Time Complexity O(n) O(log n)
Space Complexity O(1) O(1)
Sorted Data Not required Required
Suitable for small datasets Suitable for large datasets
Applicability
or unsorted data or sorted data
Slower, especially for Faster, especially for large
Performance
large datasets datasets
Simple and easy to More complex due to the
Implementation
implement need for sorted data

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Sorting

Sorting is the process of arranging elements in a specific order, typically in ascending

or descending order, based on some criteria such as numerical value, alphabetical
order, or any other defined key. It is a fundamental operation in computer science and
finds applications in various fields, including data processing, searching, and
information retrieval.

The primary goal of sorting is to make data easier to search, analyze, and process
efficiently. Efficient sorting algorithms are essential for optimizing various
computational tasks and improving the performance of algorithms that rely on sorted
data.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Types of Sorting
Types of Sorting Algorithms
Sorting algorithms can be categorized based on various criteria, including their complexity, memory usage,
stability, and adaptability. Here are some common types of sorting algorithms:
[Link] Sorting: Internal sorting algorithms are used to sort data stored in memory (RAM). These algorithms
operate entirely within the main memory and do not require external storage devices.
1. Comparison-based Sorting Algorithms: These algorithms compare elements pairwise to determine
their relative order.
1. Examples: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort.
2. Non-comparison-based Sorting Algorithms: These algorithms do not rely on pairwise comparisons
between elements.
1. Examples: Counting Sort, Radix Sort, Bucket Sort.
[Link] Sorting: External sorting algorithms are used to sort data that is too large to fit entirely into the main
memory. They involve reading and writing data to external storage devices such as hard disks.
1. Merge Sort with External Storage: Merge Sort is commonly used for external sorting due to its
ability to efficiently merge sorted sublists from external storage.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent
elements if they are in the wrong order. This algorithm is not suitable for large data sets as
its average and worst-case time complexity is quite high.
Bubble Sort Algorithm
In Bubble Sort algorithm,
1. Traverse from left and compare adjacent elements and the higher one is placed at right
side.
2. In this way, the largest element is moved to the rightmost end at first.
3. This process is then continued to find the second largest and place it and so on until the
data is sorted.
Let us understand the working of bubble sort with the help of the following illustration:
Input: arr[] = {6, 3, 0, 5}
First Pass:
The largest element is placed in its correct position, i.e., the end of the array.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Bubble Sort

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Advantages Bubble Sort

Advantages of Bubble Sort:

❑ Bubble sort is easy to understand and implement.
❑ It does not require any additional memory space.
❑ It is a stable sorting algorithm, meaning that elements with the same key value maintain their relative
order in the sorted output.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Algorithms Bubble Sort

[Link] with an unsorted array of elements.

[Link]: Compare adjacent elements in the array.
[Link]: If the elements are in the wrong order (e.g., the first element is greater than the second), swap
them.
[Link]: Move through the array and repeat steps 2 and 3 until the end of the array is reached.
[Link]: Repeat the traversal process multiple times (n-1 times for an array of size n) until the array is
sorted.
[Link]: The array is now sorted.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Bubble Sort

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Disadvantages Bubble Sort

[Link] Time Complexity:

[Link] with Large Datasets:
[Link] with Nearly Sorted Arrays:
4. Not Suitable for Real-world Applications:

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Selection Sort
• Selection sort is a simple and efficient sorting algorithm that works by
repeatedly selecting the smallest (or largest) element from the unsorted
portion of the list and moving it to the sorted portion of the list.

• 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.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Selection Sort
How does Selection Sort Algorithm work?
Lets consider the following array as an example: arr[] = {64, 25, 12, 22, 11}
First pass:
❑For the first position in the sorted array, the whole array is traversed from index 0 to 4
sequentially. The first position where 64 is stored presently, after traversing whole array it is clear
that 11 is the lowest value.
❑Thus, replace 64 with 11. After one iteration 11, which happens to be the least value in the
array, tends to appear in the first position of the sorted list.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Selection Sort
Second Pass:
• For the second position, where 25 is present, again traverse the rest of
the array in a sequential manner.
• After traversing, we found that 12 is the second lowest value in the array
and it should appear at the second place in the array, thus swap these
values.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Selection Sort
Third Pass:
Now, for third place, where 25 is present again traverse the rest of the array
and find the third least value present in the array.
While traversing, 22 came out to be the third least value and it should
appear at the third place in the array, thus swap 22 with element present at
third position.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Selection Sort
Fourth pass:
Similarly, for fourth position traverse the rest of the array and find the fourth
least element in the array
As 25 is the 4th lowest value hence, it will place at the fourth position.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Selection Sort
Fifth Pass:
At last the largest value present in the array automatically get placed at the
last position in the array
The resulted array is the sorted array.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Selection Sort
Advantages of Selection Sort Algorithm
❑Simple and easy to understand.
❑Works well with small datasets.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Selection Sort

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Insertion Sort
To sort an array of size N in ascending order iterate over the array and compare the current element (key) to its
predecessor, if the key element is smaller than its predecessor, compare it to the elements before. Move the
greater elements one position up to make space for the swapped element.
Working of Insertion Sort algorithm
Consider an example: arr[]: {12, 11, 13, 5, 6}
12 11 13 5 6

First Pass:
Initially, the first two elements of the array are compared in insertion sort.
12 11 13 5 6

Here, 12 is greater than 11 hence they are not in the ascending order and 12 is not at its correct position. Thus,
swap 11 and 12.
So, for now 11 is stored in a sorted sub-array.

11 12 13 5 6

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

Second Pass:
Now, move to the next two elements and compare them
11 12 13 5 6

Here, 13 is greater than 12, thus both elements seems to be in ascending order, hence, no swapping will occur. 12 also stored in a sorted sub-array
along with 11

Third Pass:
Now, two elements are present in the sorted sub-array which are 11 and 12 Moving forward to the next two elements which are 13 and 5

11 12 13 5 6

Both 5 and 13 are not present at their correct place so swap them

11 12 5 13 6

After swapping, elements 12 and 5 are not sorted, thus swap again

11 5 12 13 6
Here, again 11 and 5 are not sorted, hence swap again
5 11 12 13 6

Here, 5 is at its correct position

Fourth Pass:
•Now, the elements which are present in the sorted sub-array are 5, 11 and 12
•Moving to the next two elements 13 and 6

5 11 12 13 6

•Clearly, they are not sorted, thus perform swap between both

5 11 12 6 13

•Now, 6 is smaller than 12, hence, swap again

5 11 6 12 13

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

Here, also swapping makes 11 and 6 unsorted hence, swap again
5 6 11 12 13

•Finally, the array is completely sorted.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

Characteristics of Insertion Sort
❑This algorithm is one of the simplest algorithms with a simple
implementation
❑Basically, Insertion sort is efficient for small data values
❑Insertion sort is adaptive in nature, i.e. it is appropriate for data sets that
are already partially sorted.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037
 Merge Sort

Merge sort is defined as a sorting algorithm that works by dividing an array into
smaller subarrays, sorting each subarray, and then merging the sorted subarrays
back together to form the final sorted array.

In simple terms, we can say that the process of merge sort is to divide the array into
two splits, sort each half, and then merge the sorted splits back together. This
process is repeated until the entire array is sorted.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Merge Sort

How does Merge Sort work?

Merge sort is a recursive algorithm that continuously splits the array in half until it
cannot be further divided i.e., the array has only one element left (an array with
one element is always sorted). Then the sorted subarrays are merged into one
sorted array.

Lets consider an array arr[] = {38, 27, 43, 10}

Initially divide the array into two equal splits:

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Merge Sort

Step 2: These subarrays are further divided into two halves. Now they become array of unit
length that can no longer be divided and array of unit length are always sorted.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Merge Sort

Step 3: These sorted subarrays are merged together, and we get bigger sorted subarrays.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Merge Sort

The following diagram shows the complete merge sort process for an example array {38, 27, 43, 10}.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Merge Sort

Merge Sort is a classic sorting algorithm that follows the divide-and-conquer approach. Here's a step-
by-step explanation of how the algorithm works:
1. Divide: The unsorted list is divided into two halves recursively until each sub list contains only
one element.
2. Conquer: Once the lists are divided into individual elements, they are merged back together in a
sorted manner.
3. Merge: During the merge step, the two smaller sorted lists are merged into a single larger sorted
list. This process continues recursively until there is only one sorted list remaining, which is the
sorted version of the original list.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Bucket Sort

Bucket Sort is a sorting algorithm that divides the unsorted array elements into several groups called
buckets. Each bucket is then sorted by using any of the suitable sorting algorithms or recursively applying
the same bucket algorithm.
Finally, the sorted buckets are combined to form a final sorted array.
Scatter Gather Approach
The process of bucket sort can be understood as a scatter-gather approach. Here, elements are first
scattered into buckets then the elements in each bucket are sorted. Finally, the elements are gathered in
order.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Working of Bucket Sort
•
Suppose, the input array is:

Create an array of size 10. Each slot of this array is used as a bucket for storing elements.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Working of Bucket Sort
•
Insert elements into the buckets from the array. The elements are inserted according to the range of the bucket.

In our example code, we have buckets each of ranges from 0 to 1, 1 to 2, 2 to 3,...... (n-1) to n.

Suppose, an input element is .23 is taken. It is multiplied by size = 10 (ie. .23*10=2.3). Then, it is converted into an
integer (ie. 2.3≈2). Finally, .23 is inserted into bucket-2

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Working of Bucket Sort
•

• Similarly, .25 is also inserted into the same bucket. Every time, the floor value of the floating point number is taken. If we take
integer numbers as input, we have to divide it by the interval (10 here) to get the floor value. Similarly, other elements are
inserted into their respective buckets.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Working of Bucket Sort
•
The elements of each bucket are sorted using any of the stable sorting algorithms. Here, we have used quicksort
(inbuilt function).

The elements from each bucket are gathered. It is done by iterating through the bucket and inserting an
individual element into the original array in each cycle. The element from the bucket is erased once it is
copied into the original array.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Algorithms of Bucket Sort
•

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Quick Sort

Quicksort is a sorting algorithm based on the divide and conquer approach where

1. An array is divided into subarrays by selecting a pivot element (element selected from the array). While dividing
the array, the pivot element should be positioned in such a way that elements less than pivot are kept on the left
side and elements greater than pivot are on the right side of the pivot.
2. The left and right subarrays are also divided using the same approach. This process continues until each subarray
contains a single element.
3. At this point, elements are already sorted. Finally, elements are combined to form a sorted array.

Pick the middle as the pivot.

1. Always pick the last element as a pivot.
2. There are many different choices for picking pivots.
3. Always pick the first element as a pivot.
4. Pick a random element as a pivot.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Working of Quick Sort
•
1. Select the Pivot Element
There are different variations of quicksort where the pivot element is selected from different positions. Here, we
will be selecting the rightmost element of the array as the pivot element.

Rearrange the Array

Now the elements of the array are rearranged so that elements that are smaller than the pivot are put on the left
and the elements greater than the pivot are put on the right.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Working of Quick Sort
•
Now, pivot is compared with other elements. If an element smaller than the pivot element is reached, the smaller element is
swapped with the greater element found earlier.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Working of Quick Sort
•
Again, the process is repeated to set the next greater element as the second pointer. And, swap it with another
smaller element.

The process goes on until the second last element is reached.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Working of Quick Sort
•
Finally, the pivot element is swapped with the second pointer.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Working of Quick Sort
•
3. Divide Subarrays
Pivot elements are again chosen for the left and the right sub-parts separately. And, step 2 is repeated

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Working of Quick Sort
•

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

 Comparison of Complexities of all sorting techniques.

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037

•

Thank You

Dr. Dattatray G. Takale, Department of Computer engineering, VIT, Pune- 411037