Bubble Sort in C is a simplest sorting algorithm where we repeatedly iterate through the array and

swap adjacent elements that are unordered

It is the slowest algorithm with time complixities listed below:

1.worst case||avg case=o(n^2);

2.best case:o(n)

Space complexity:o(1)

implementing Bubble Sort Algorithm

Following are the steps involved in bubble sort(for sorting a given array in ascending order):

1. Starting with the first element(index = 0), compare the current element with the next
element of the array.
2. If the current element is greater than the next element of the array, swap them.
3. If the current element is less than the next element, move to the next element. Repeat
Step 1.

Example:

Selection sort:
Selection sort is an algorithm that selects the smallest element from an unsorted list in each
iteration and places that element at the beginning of the unsorted list.

It is called selection sort because it repeatedly selects the next-smallest element and swaps it into
the right place.

Time complexities:

Avg case=best case=worst=o(n^2)

Space complexity:o(1)

Following are the steps involved in selection sort(for sorting a given array in ascending
order):

1. Starting from the first element, we search the smallest element in the array, and
replace it with the element in the first position.
2. We then move on to the second position, and look for smallest element present in the
subarray, starting from index 1, till the last index.
3. We replace the element at the second position in the original array, or we can say at
the first position in the subarray, with the second smallest element.
4. This is repeated, until the array is completely sorted.

Insertion Sort is basically insertion of an element from a random set of numbers, to its
correct position where it should actually be, by shifting the other elements if required.
How Insertion Sort Works?
Following are the steps involved in insertion sort:

1. We start by making the second element of the given array, i.e. element at index 1, the
key. The key element here is the new card that we need to add to our existing sorted
set of cards(remember the example with cards above).
2. We compare the key element with the element(s) before it, in this case, element at
index 0:
o If the key element is less than the first element, we insert the key element
before the first element.
o If the key element is greater than the first element, then we insert it after the
first element.
3. Then, we make the third element of the array as key and will compare it with
elements to it's left and insert it at the right position.
4. And we go on repeating this, until the array is sorted.

Time comp and space comp same as buble sort

Merge sort:
Merge sort is a sorting technique basd on divide and conquer strategy

Divide and Conquer Strategy

Using the Divide and Conquer technique, we divide a problem into subproblems. When the
solution to each subproblem is ready, we 'combine' the results from the subproblems to solve
the main problem.

Suppose we had to sort an array A whose mid is q,low is p and high is r

Divide:

In this step we divide A[p..r] into 2 sub parts A[p,q] and A[q+1,r]

Conquer:

In this step we try to ssort out the sub arrays A[p,q] and A[q+1,r]

Combine:

In this step we get two sorted arrays A[p,q] and A[q+1,r] and combine them into A[p,r]

The MergeSort Algorithm

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

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

Code of merge sort fun write

Heap sort
Heap sort works by visualizing the elements of the array as a special kind of complete binary tree
called heap.

Heap Sort is a popular and efficient sorting algorithm in computer programming.

Min-Heap − Where the value of the root node is less than or equal to either of its children.

Max-Heap − Where the value of the root node is greater than or equal to either of its children.

A Graph is a non-linear data structure consisting of nodes and edges. The nodes are
sometimes also referred to as vertices and the edges are lines or arcs that connect any two
nodes in the graph. More formally a Graph can be defined as,

A Graph consists of a finite set of vertices or set of edges which connect a pair of nodes

Graphs are used to solve many real-life problems. Graphs are used to represent networks. The
networks may include paths in a city or telephone network or circuit network. Graphs are also used
in social networks like linkedIn, Facebook. For example, in Facebook, each person is represented
with a vertex(or node). Each node is a structure and contains information like person id, name,
gender, locale etc.

a graph is said to be connected if there exist atleast one path between each and every pair of
vertices in graph G, otherwise it is disconnected.

Breadth First Search

BFS stands for Breadth First Search is a vertex based technique for finding a shortest path
in graph. It uses a Queue data structure which follows first in first out. In BFS, one vertex is
selected at a time when it is visited and marked then its adjacent are visited and stored in the
queue. It is slower than DFS.

Depth First Search

DFS stands for Depth First Search is a edge based technique. It uses the Stack data
structure, performs two stages, first visited vertices are pushed into stack and second if there
is no vertices then visited vertices are popped.
Ex-

BFS vs DFS
S.NO BFS DFS

1. BFS stands for Breadth First Search. DFS stands for Depth First Search.

BFS(Breadth First Search) uses Queue data DFS(Depth First Search) uses Stack data
2.
structure for finding the shortest path. structure.

BFS can be used to find single source shortest

path in an unweighted graph, because in BFS, In DFS, we might traverse through more edges
3.
we reach a vertex with minimum number of to reach a destination vertex from a source.
edges from a source vertex.

BFS is more suitable for searching verteces DFS is more suitable when there are solutions
3.
which are closer to the given source. away from source.

DFS is more suitable for game or puzzle

BFS considers all neighbors first and therefore
problems. We make a decision, then explore
4. not suitable for decision making trees used in
all paths through this decision. And if this
games or puzzles.
decision leads to win situation, we stop.

The Time complexity of DFS is also O(V + E),

The Time complexity of BFS is O(V + E), where
5. where V stands for vertices and E stands for
V stands for vertices and E stands for edges.
edges.

BST :
It is an ordered binary tree in which the nodes are arranged in particular order

In bst,the value of all nodes in the left subtree is less than the value of root

The valure of all nodes in the right subtree is greator than the value of root

It will be recursively applied to right and left sub trees of the root

TYPES:
Full Binary Tree A Binary Tree is full if every node has 0 or 2 children. Following are examples of a
full binary tree. We can also say a full binary tree is a binary tree in which all nodes except leaves
have two children.

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except
possibly the last level and the last level has all keys as left as possible

Perfect Binary Tree A Binary tree is Perfect Binary Tree in which all internal nodes have two children
and all leaves are at the same level.

Graph vs Tree
No. Graph Tree

Graph is a non-linear data

1 Tree is a non-linear data structure.
structure.

It is a collection of vertices/nodes
2 It is a collection of nodes and edges.
and edges.

General trees consist of the nodes having any number of

Each node can have any number
3 child nodes. But in case of binary trees every node can have
of edges.
at the most two child nodes.

There is no unique node called

4 There is a unique node called root in trees.
root in graph.

5 A cycle can be formed. There will not be any cycle.

Applications: For finding shortest

6 Applications: For game trees, decision trees, the tree is used.
path in networking graph is used.

Applications of Trees
Trees and their variants are an extremely useful data structure with lots of practical
applications.

 Binary Search Trees(BSTs) are used to quickly check whether an element is present
in a set or not.
 Heap is a kind of tree that is used for heap sort.
 A modified version of tree called Tries is used in modern routers to store routing
information.
 Most popular databases use B-Trees and T-Trees, which are variants of the tree
structure we learned above to store their data
 Compilers use a syntax tree to validate the syntax of every program you write.