Unit 3: Sorting & Graphs

Introduction to Sorting

Sorting is the process of arranging data elements in a specific order, usually ascending or descending.
Sorting improves:

Searching efficiency
Data presentation
Duplicate detection
Database operations

Insertion Sort

Insertion Sort works the same way we arrange playing cards in our hand.
It builds the sorted list one element at a time by inserting each element at its correct position.

Algorithm (Steps)

Assume the first element is sorted.
Pick the next element.
Compare it with elements on the left.
Shift larger elements one position right.
Insert the element at the correct position.
Repeat until the list is sorted.

Example

Input: 8 3 5 2
Passes:

8 | 3 → 3 8
3 8 | 5 → 3 5 8
3 5 8 | 2 → 2 3 5 8

Time Complexity

Case	Complexity
Best	O(n)
Average	O(n²)
Worst	O(n²)

Space Complexity

O(1) (In-place)

Advantages

Simple and easy to implement
Efficient for small data sets
Stable sorting algorithm

Disadvantages

Very slow for large datasets

Applications

Small lists
Nearly sorted data

Selection Sort

Selection Sort repeatedly selects the smallest element from the unsorted part and places it at the beginning.

Algorithm

Find the minimum element.
Swap it with the first position.
Repeat for remaining elements.

Example

Input: 64 25 12 22 11

Passes:

Select 11 → 11 25 12 22 64
Select 12 → 11 12 25 22 64
Select 22 → 11 12 22 25 64

Time Complexity

Case	Complexity
Best	O(n²)
Average	O(n²)
Worst	O(n²)

Space Complexity

O(1)

Advantages

Simple algorithm
Minimum number of swaps

Disadvantages

Always slow (O(n²))
Not stable

Applications

Useful when memory writes are costly

Bubble Sort

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.

Algorithm

Compare adjacent elements.
Swap if needed.
Largest element “bubbles” to the end.
Repeat until no swaps are needed.

Example

Input: 5 1 4 2 8

Passes:

1 4 2 5 8
1 2 4 5 8

Time Complexity

Case	Complexity
Best	O(n)
Average	O(n²)
Worst	O(n²)

Space Complexity

O(1)

Advantages

Very easy to understand
Stable algorithm

Disadvantages

Extremely inefficient for large lists

Applications

Educational purposes only

Heap Sort

Heap Sort uses a Binary Heap data structure to sort elements.

Working Principle

Build a Max Heap.
Remove the root (largest element).
Place it at the end.
Repeat for remaining elements.

Example

Input: 4 10 3 5 1

Build Max Heap
Extract max repeatedly → Sorted array

Time Complexity

Case	Complexity
Best	O(n log n)
Average	O(n log n)
Worst	O(n log n)

Space Complexity

O(1)

Advantages

Fast and efficient
No extra memory required

Disadvantages

Not stable
Complex implementation

Applications

Priority queues
Large datasets

Comparison of Sorting Algorithms

Algorithm	Best	Average	Worst	Stable	In-Place
Bubble	O(n)	O(n²)	O(n²)	Yes	Yes
Selection	O(n²)	O(n²)	O(n²)	No	Yes
Insertion	O(n)	O(n²)	O(n²)	Yes	Yes
Heap	O(n log n)	O(n log n)	O(n log n)	No	Yes

Sorting in Linear Time

Counting Sort

Counting Sort works by counting occurrences of elements instead of comparisons.

Algorithm

Find the maximum value.
Create a count array.
Store frequency of each element.
Compute cumulative sum.
Place elements in sorted order.

Time Complexity

O(n + k)

Space Complexity

O(k)

Advantages

Very fast for small range values
Stable

Disadvantages

Not suitable for large values

Applications

Sorting marks, ages, IDs

Bucket Sort

Bucket Sort divides elements into multiple buckets, sorts them individually, and merges them.

Algorithm

Create empty buckets.
Distribute elements into buckets.
Sort each bucket.
Merge all buckets.

Time Complexity

Average: O(n)
Worst: O(n²)

Space Complexity

O(n)

Advantages

Very fast for uniformly distributed data

Disadvantages

Requires extra memory
Not suitable for non-uniform data

Applications

Floating-point numbers
Large datasets with uniform distribution

Conclusion (Exam Ready)

Insertion, Bubble, Selection → Simple but slow
Heap Sort → Efficient and widely used
Counting & Bucket Sort → Linear time but data-specific

GRAPHS

A graph is a non-linear data structure used to represent relationships between objects.

A graph G is defined as:

G = (V, E)

Where:

V = Set of vertices (nodes)
E = Set of edges (connections)

Terminology Used with Graph

Term	Description
Vertex (Node)	Basic unit of graph
Edge	Connection between two vertices
Directed Graph	Edges have direction
Undirected Graph	Edges have no direction
Weighted Graph	Edges have weights
Degree	Number of edges connected to a vertex
In-Degree	Number of incoming edges
Out-Degree	Number of outgoing edges
Path	Sequence of vertices connected by edges
Cycle	Path that starts and ends at same vertex
Connected Graph	Every vertex is reachable
Disconnected Graph	Some vertices are not connected
Self Loop	Edge from a vertex to itself
Parallel Edges	Multiple edges between same vertices

Data Structure for Graph Representation

Adjacency Matrix

An Adjacency Matrix is a 2D array of size V × V, where:

1 indicates edge exists
0 indicates no edge

Example

Graph with vertices A, B, C

	A	B	C
A	0	1	1
B	1	0	0
C	1	0	0

Characteristics

Matrix is symmetric for undirected graphs
Diagonal elements represent self loops

Time & Space Complexity

Space: O(V²)
Edge check: O(1)

Advantages

Simple representation
Fast edge lookup

Disadvantages

Wastes memory for sparse graphs

Adjacency List

An Adjacency List stores a list of adjacent vertices for each vertex.

Example


A → B → C  
B → A  
C → A

Time & Space Complexity

Space: O(V + E)
Edge check: O(deg(V))

Advantages

Memory efficient
Best for sparse graphs

Disadvantages

Edge lookup slower than matrix

Comparison: Adjacency Matrix vs Adjacency List

Feature	Adjacency Matrix	Adjacency List
Memory	O(V²)	O(V+E)
Edge Check	Fast	Slower
Sparse Graph	Inefficient	Efficient
Dense Graph	Efficient	Less Efficient

Graph Traversal

Graph traversal means visiting all vertices of a graph systematically.

Depth First Search (DFS)

DFS explores as far as possible along a branch before backtracking.

Technique Used

Stack
Recursion

Algorithm (Steps)

Start from a vertex
Mark it as visited
Visit adjacent unvisited vertex
Repeat recursively
Backtrack when no adjacent vertex is left

Pseudocode


DFS(v):
  mark v visited
  for each adjacent u of v:
    if u not visited:
        DFS(u)

Time Complexity

O(V + E)

Applications

Detecting cycles
Topological sorting
Path finding

Breadth First Search (BFS)

BFS explores all neighboring vertices first, then moves to next level.

Technique Used

Queue

Algorithm (Steps)

Start from a vertex
Mark it visited and enqueue
Dequeue vertex and visit neighbors
Enqueue unvisited neighbors
Repeat until queue is empty

Pseudocode


BFS(v):
  mark v visited
  enqueue(v)
  while queue not empty:
     x = dequeue
     for each adjacent u of x:
        if u not visited:
            mark visited
            enqueue(u)

Time Complexity

O(V + E)

Applications

Shortest path (unweighted graph)
Level order traversal
Network broadcasting

DFS vs BFS Comparison

Feature	DFS	BFS
Data Structure	Stack	Queue
Approach	Depth wise	Level wise
Memory	Less	More
Shortest Path	No	Yes
Implementation	Recursive	Iterative

Connected Component

A Connected Component is a subgraph where:

All vertices are connected
No vertex is connected to vertices outside the component

Example

If a graph has:

Component 1: A, B, C
Component 2: D, E → Total 2 connected components

Finding Connected Components

Use DFS or BFS
Count number of times traversal starts from unvisited node

Algorithm

Initialize visited array

For each vertex:

If not visited, run DFS/BFS
Increment component count

Time Complexity

O(V + E)

Applications

Social network analysis
Network connectivity
Clustering problems

Important Exam Points (MCA)

Graph is non-linear
BFS uses Queue
DFS uses Stack/Recursion
Adjacency list is best for sparse graphs
Connected components show independent subgraphs

Conclusion

Graphs are widely used in:

Computer networks
Maps & GPS
Social media
Operating systems

Understanding representation + traversal is very important for MCA exams and interviews.