DATA STRUCTURES -

COMPLETE STUDY NOTES

[Link] 3rd Semester (PCC-CSE-221-G)

UNIT-I: FUNDAMENTALS & ALGORITHM

ANALYSIS
1. BASIC CONCEPTS
Data Structure Definition

Organized collection of data with a set of operations

Comprises: Data values + Operations + Axioms
Examples: Arrays, Linked Lists, Stacks, Queues, Trees, Graphs

Why Study Data Structures?

Choose right structure for problem → Better performance

Reduces time complexity → Faster programs
Reduces space complexity → Efficient memory use
Key to writing scalable software

Algorithm Definition

Finite sequence of steps to solve a problem

Characteristics: Input, Process, Finiteness, Effectiveness, Output
Must be: Simple, Unambiguous, Effective, Finite, Efficient

2. BIG-O NOTATION & COMPLEXITY ANALYSIS

Big-O Definition

T(n) = O(g(n)) if ∃ constants c > 0, n₀ such that:

T(n) ≤ c × g(n) for all n ≥ n₀

 Measures upper bound on growth rate
Ignores constants and lower-order terms
Helps compare algorithms on large inputs

Complexity Classes (Best to Worst)

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

Common Big-O Classes

Class Name Example Use Case
O(1) Constant Array access arr[i] Hash tables, Direct access
O(log n) Logarithmic Binary search Searching sorted data
O(n) Linear Linear search, Traversal Simple loops
O(n log n) Linear log Merge sort, Quick sort Efficient sorting
O(n²) Quadratic Bubble sort, Nested loops Small datasets
O(n³) Cubic Matrix multiplication Avoid if possible
O(2ⁿ) Exponential Naive Fibonacci AVOID - exponential growth
O(n!) Factorial All permutations DEFINITELY AVOID

Calculating Big-O

Rule 1: Count loops

Single loop: O(n)

Nested loops: Multiply → O(n²), O(n³)
Sequential: Add → Take larger

Rule 2: Drop constants

O(2n) → O(n)
O(5n²) → O(n²)

Rule 3: Drop lower-order terms

O(n² + n) → O(n²)
O(n log n + n) → O(n log n)

Rule 4: Recursion

Use recursion tree or count function calls

Other Asymptotic Notations

Ω (Omega): Lower bound - at least this time

Θ (Theta): Tight bound - exactly this time
o (little-o): Strict upper bound - strictly faster
 3. TIME COMPLEXITY
Definition

Amount of time algorithm needs to run to completion

Why Study?

Know if program will respond in time (real-time systems)

Compare multiple solutions
Predict performance on large data

Measuring Time Complexity

Count key operations (operations taking max time)

Time complexity = f(number of key operations)

Cases

Best Case: Minimum time (rare, minimum input)

Average Case: Realistic scenario
Worst Case: Maximum time (what we use for Big-O)

Examples

Linear Search:
- Best: O(1) - found at first position
- Worst: O(n) - found at last position or not found
- Average: O(n/2) ≈ O(n)

Binary Search:
- All cases: O(log n)

4. SPACE COMPLEXITY
Definition

Amount of memory program needs to run to completion

Components

1. Instruction Space: Fixed - space for executable code

2. Data Space:
Constants & variables: Fixed
Arrays & structures: Fixed or variable
 Dynamic allocation: Variable
3. Stack Space: For function calls and recursion

Calculation

Total Space = Fixed Space + Variable Space

Examples

Array of size n:
Space = O(n) + O(1) = O(n)

2D Array n×n:
Space = O(n²)

Recursive function depth d:

Stack space = O(d)

Space vs Time Tradeoff

More time: Less memory needed

Less time: More memory needed
Choose based on constraints

5. CHOOSING THE RIGHT DATA STRUCTURE

Criteria

1. Problem requirements - What operations needed?

2. Frequency of operations - Which are most common?
3. Size of data - Fixed or dynamic?
4. Time constraints - How fast must it be?
5. Space constraints - How much memory available?

Comparison Example - Student Records

Poor Choice - Parallel Arrays:

char nameList[60][15]; // 60 students, 15 char names
int roll[60];
int marks[60];
float percent[60];
char grade[60];
// Swapping 2 students needs 15 separate statements

Good Choice - Array of Structures:

struct student {
char name[15];
int roll;
int marks;
float percent;
char grade;
};
struct student studList[60];
// Swapping only 3 statements

6. ARRAY vs LINKED LIST

Memory Layout

Array: Contiguous memory locations [sequential]

Linked List: Scattered memory with pointers

Access Time

Array: O(1) - direct access arr[5]

Linked List: O(n) - must traverse from start

Insertion/Deletion

Array: O(n) - need to shift elements

Linked List: O(1) - only change pointers

Memory Efficiency

Array: No extra memory

Linked List: Extra memory for pointers

When to Use

Array: Frequent access, fixed size

 Linked List: Frequent insertion/deletion, dynamic size

7. SEARCHING TECHNIQUES
Linear Search - O(n)

int linear_search(int arr[], int n, int target) {

for (int i = 0; i < n; i++) {
if (arr[i] == target) return i;
}
return -1;
}

Works on unsorted data

Simple but slow
Worst case: Check all elements

Binary Search - O(log n)

int binary_search(int arr[], int n, int target) {

int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}

Requires sorted array

Divide and conquer
50,000x faster than linear for 1M elements!

8. ALGORITHM DESIGN STEPS

Step 1: Understand Problem

What are inputs and outputs?

What constraints exist?
What is acceptable performance?
 Step 2: Identify Inputs & Outputs

Input data type and size

Output format required

Step 3: Choose Data Structure

Which structure suits problem?

Trade-offs between options?

Step 4: Design Logic

Write algorithm in simple English

Pseudocode or flowchart
Verify correctness

Step 5: Test Algorithm

Test with various inputs

Check edge cases
Verify correctness

Step 6: Refine Until Perfect

Optimize if needed
Improve readability
Add comments

UNIT-II: STACKS & QUEUES

1. STACK - LIFO (Last In First Out)
Definition

Linear data structure where insertion & deletion happen at same end (top)

Operations

PUSH: Insert element on top - O(1)

POP: Remove element from top - O(1)
PEEK/TOP: View top element - O(1)
isEmpty: Check if empty - O(1)

Stack Implementation
#define MAX 100
struct stack {
int data[MAX];
int top;
};

void push(struct stack *s, int x) {

if (s->top == MAX - 1) { printf("Overflow\n"); }
else { s->data[++s->top] = x; }
}

int pop(struct stack *s) {

if (s->top == -1) { printf("Underflow\n"); return -1; }
return s->data[s->top--];
}

Applications of Stack

1. Function Calls & Recursion

Save return address

Store local variables
Stack frames for each call

2. Expression Evaluation

Infix to postfix conversion

Evaluate postfix expressions
Operator precedence handling

3. String Reversal

Push characters, pop to reverse

4. Backtracking

Maze solving
Puzzle solving
DFS traversal

5. Undo/Redo

Text editors store operations

6. Parentheses Matching

Compiler syntax checking

7. Memory Management

Call stack for function execution

Key Points

LIFO order: Last pushed is first popped

Used in compilers and OS
Elegant solution for recursive problems
Limited size (fixed array) or dynamic (linked list)

2. QUEUE - FIFO (First In First Out)

Definition

Linear data structure where insertion at rear, deletion at front

Operations

ENQUEUE: Insert at rear - O(1)

DEQUEUE: Remove from front - O(1)
PEEK: View front element - O(1)
isEmpty: Check if empty - O(1)

Simple Queue
struct queue {
int data[MAX];
int front, rear;
};

void enqueue(struct queue *q, int x) {

if (q->rear == MAX - 1) { printf("Overflow\n"); }
else {
if (q->front == -1) q->front = 0;
q->data[++q->rear] = x;
}
}

int dequeue(struct queue *q) {

if (q->front == -1) { printf("Underflow\n"); return -1; }
int x = q->data[q->front];
if (q->front == q->rear) q->front = q->rear = -1;
else q->front++;
return x;
}

Problem: Linear Queue Wastes Space

After dequeuing, front positions become unused

Can't reuse even if space available

3. CIRCULAR QUEUE - O(1) Operations

Definition

Queue where rear wraps around to front, forming circle

Advantages

1. Memory Reuse - Deleted positions used by new elements

2. No Wastage - Uses all allocated space
3. Efficient - O(1) for all operations
4. Solves rebuffering problem - No shifting needed

Difference from Linear Queue

Linear: Rear at end → can't insert even if front vacant

Circular: Rear wraps around → can insert if space available
 Circular Queue Operations

Insert (Enqueue):

1. Check if full: (rear + 1) mod n == front

2. If empty: front = 0, rear = 0
3. Else: rear = (rear + 1) mod n
4. Insert at position rear

Delete (Dequeue):

1. Check if empty: front == rear

2. Delete element at front
3. If queue now empty: front = 0, rear = 0
4. Else: front = (front + 1) mod n

Circular Queue Array Layout

Position: 0 1 2 3 4 5 6 7
Before: 5 6 . . . 1 2 3
└──────rear front────┘

After insert 7:
5 6 7 . . 1 2 3 (wraps around!)

4. PRIORITY QUEUE
Definition

Ordered collection where service based on priority, not FIFO

Difference from Normal Queue

Queue: First come, first served (FIFO)

Priority Queue: Higher priority served first

Real-World Example

Hospital emergency room:

Critical patient → Served immediately

Minor injury → Served later
 Implementation Methods

Method 1: Sorted List

Insertion: Complex O(n) - find correct position

Deletion: Simple O(1) - remove from front

Method 2: FIFO List + Priority Check

Insertion: Simple O(1) - add at rear

Deletion: Complex O(n) - search for highest priority

Applications

1. Operating Systems

CPU scheduling
Process priority
Interrupt handling

2. Networking

Packet routing
QoS (Quality of Service)

3. Algorithms

Dijkstra's shortest path

A* search (AI)

4. Data Compression

Huffman coding

5. Event Simulation

Customer service simulation

6. Game Development

Task scheduling

5. DEQUE (Double Ended Queue)

Definition

Queue with insertion & deletion at both ends

Types
 1. Input Restricted: Insert at one end, delete from both
2. Output Restricted: Delete from one end, insert from both

Properties

More flexible than queue or stack

Can be used as both stack and queue
Applications: Palindrome checking, sliding window

Time Complexity

Insert at front/rear: O(1)

Delete from front/rear: O(1)

6. EXPRESSION CONVERSION & EVALUATION

Notations

Infix: A + B (human readable)

Prefix: + A B (operator before operands)
Postfix: A B + (operator after operands)

Why Conversion?

Postfix eliminates need for parentheses

Easier for computers to evaluate
No operator precedence issues

Postfix Evaluation (Stack-based)

Algorithm:
1. Scan postfix expression left to right
2. If operand: push to stack
3. If operator: pop 2 operands, apply operation, push result
4. Final result in stack

**Example: 5 3 + 2 ***

Step 1: Push 5 → Stack: [5]

Step 2: Push 3 → Stack: [5, 3]
Step 3: See + → Pop 3, 5 → Compute 5+3=8 → Push 8 → Stack: [8]
Step 4: Push 2 → Stack: [8, 2]
Step 5: See * → Pop 2, 8 → Compute 8*2=16 → Push 16 → Stack: [16]
Result: 16
 UNIT-III: LINKED LISTS & TREES
1. LINKED LIST FUNDAMENTALS
Definition

Dynamic data structure with nodes containing data and pointers

Node Structure

struct node {
int data; // Data element
struct node *next; // Pointer to next node
};

Advantages over Array

Dynamic size
Easy insertion/deletion: O(1)
No wastage of memory

Disadvantages

Sequential access: O(n)

Extra memory for pointers
Cache performance worse

2. SINGLY LINKED LIST

Structure

head → [data|next] → [data|next] → [data|next] → NULL

Key Operations

Traversal - O(n):
void traverse(struct node *head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
}

Insertion at Beginning - O(1):

struct node* insert_begin(struct node *head, int data) {

struct node *new = (struct node*)malloc(sizeof(struct node));
new->data = data;
new->next = head;
return new; // New node is new head
}

Insertion at Position - O(n):

void insert_pos(struct node *head, int data, int pos) {

struct node *new = (struct node*)malloc(sizeof(struct node));
new->data = data;

struct node *curr = head;

for (int i = 1; i < pos - 1; i++) {
curr = curr->next;
}
new->next = curr->next;
curr->next = new;
}

Deletion - O(n):
struct node* delete_node(struct node *head, int data) {
if (head->data == data) {
struct node *temp = head;
head = head->next;
free(temp);
return head;
}

struct node *curr = head;

while (curr->next != NULL) {
if (curr->next->data == data) {
struct node *temp = curr->next;
curr->next = temp->next;
free(temp);
break;
}
curr = curr->next;
}
return head;
}

Searching - O(n):

struct node* search(struct node *head, int target) {

while (head != NULL) {
if (head->data == target) return head;
head = head->next;
}
return NULL;
}

3. DOUBLY LINKED LIST

Structure

struct node {
int data;
struct node *prev; // Pointer to previous
struct node *next; // Pointer to next
};
 Graphical Layout

NULL ← [data|prev|next] ↔ [data|prev|next] ↔ [data|prev|next] → NULL

Advantages

Can traverse both directions

Easier deletion (have prev pointer)
Better for certain operations

Disadvantages

Extra memory for prev pointer

More complex implementation

Key Difference from Singly

Singly: Can only go forward

Doubly: Can go forward AND backward

4. CIRCULAR LINKED LIST

Definition

Last node points back to first node instead of NULL

Structure

start → [data|next] → [data|next] → [data|next] ↓

↑_______________________________________↑
(wraps around to form circle)

Advantages

1. Each node accessible from any node

2. No special handling for first node
3. Can traverse from any starting point
4. Every node has predecessor

Disadvantages

1. Risk of infinite loop if not careful

2. No NULL pointer to detect end
3. More complex than singly linked list
 Characteristic Feature

last_node->next == first_node; // Not NULL!

5. BINARY TREE
Definition

Finite set of nodes which is either empty OR

Consists of root and two disjoint binary subtrees (left & right)
Each node has degree ≤ 2

Node Structure

struct node {
int data;
struct node *left; // Left subtree pointer
struct node *right; // Right subtree pointer
};

Tree Terminology

Root: Top node with no parent

Parent: Node with children
Child: Node with parent
Leaf: Node with no children
Height: Longest path from root to leaf
Depth: Distance from root
Siblings: Nodes with same parent
Subtree: Tree formed by node and descendants

Example Tree

1 (Root, Height=2)
/ \
2 3
/ \
4 5 (Leaf nodes: 4, 5, 3)

Types of Binary Trees

1. Full Binary Tree: Every node has 0 or 2 children

2. Complete Binary Tree: All levels full except possibly last
 3. Perfect Binary Tree: All leaves at same level
4. Balanced Binary Tree: Height difference ≤ 1
5. Skewed Tree: Linear structure (worst case)

6. BINARY SEARCH TREE (BST)

Definition

Binary tree with ordering property:

Left subtree values < Root value

Right subtree values > Root value
Both subtrees are also BSTs

Example

20
/ \
10 30
/ \ / \
5 15 25 35

Properties

In-order traversal gives sorted sequence

Average search: O(log n)
Worst case search: O(n) if unbalanced
Insertion/Deletion: O(log n) average

Operations

Search - O(log n) average:

struct node* search(struct node *root, int target) {

if (root == NULL) return NULL;
if (root->data == target) return root;
if (target < root->data) return search(root->left, target);
else return search(root->right, target);
}

Insertion - O(log n) average:

struct node* insert(struct node *root, int data) {
if (root == NULL) {
struct node *new = malloc(sizeof(struct node));
new->data = data;
new->left = new->right = NULL;
return new;
}
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}

Applications

Database indexing
Symbol table in compilers
File system directories
Autocomplete/Spell checking
Range searching

Worst Case - Unbalanced BST

If input: 1, 2, 3, 4, 5 (sorted)
Results in:
1
\
2
\
3 (Like a linked list!)
\
4
\
5
Search becomes O(n) - AVOID!
Solution: Use AVL Trees or Red-Black Trees

7. TREE TRAVERSALS
Why Traverse?

Visit every node in tree in systematic order

 Types

1. Inorder (Left-Root-Right):

Algorithm:
1. Traverse left subtree
2. Process root
3. Traverse right subtree

For BST → Gives SORTED order!

2. Preorder (Root-Left-Right):

Algorithm:
1. Process root
2. Traverse left subtree
3. Traverse right subtree

Use: Create copy of tree, Prefix notation

3. Postorder (Left-Right-Root):

Algorithm:
1. Traverse left subtree
2. Traverse right subtree
3. Process root

Use: Delete tree, Postfix notation

Example - Tree Traversals

Tree: 1
/ \
2 3
/ \
4 5

Inorder: 4 2 5 1 3
Preorder: 1 2 4 5 3
Postorder: 4 5 2 3 1

Level-Order (Breadth-First)
Process nodes level by level:
Level 0: 1
Level 1: 2, 3
Level 2: 4, 5

Output: 1 2 3 4 5

8. AVL TREE (Balanced BST)

Definition

Binary search tree that maintains balance to ensure O(log n) operations

Balance Property

|Height(left) - Height(right)| ≤ 1

Why AVL?

BST worst case: O(n) if unbalanced

AVL guarantees: O(log n) always
Uses rotations to maintain balance

Balance Factor

BF = Height(left) - Height(right)
BF must be -1, 0, or +1

Self-Balancing Property

When BF becomes ±2, rotations performed:

Single rotation (LL or RR case)

Double rotation (LR or RL case)

Applications

Database indexing
File systems
Memory allocation

9. APPLICATIONS OF BINARY TREES

 1. Expression Trees - Mathematical expressions in compilers
2. Huffman Coding - Data compression algorithm
3. Heaps - Priority queues, heap sort
4. Binary Search Trees - Searching, indexing
5. Trie Trees - Autocomplete, spell checking
6. Game Trees - Minimax algorithm, game AI
7. Segment Trees - Range queries
8. Merkle Trees - Blockchain, verification
9. Spreadsheets - Microsoft Excel data structure
10. Memory Allocation - OS memory management
11. Syntax Trees - Compiler parsing
12. Network Routing - Binary trees for routing decisions

UNIT-IV: SORTING ALGORITHMS

1. SORTING FUNDAMENTALS
Definition

Arranging elements in increasing or decreasing order

Types

Internal Sorting: In primary memory (RAM)

External Sorting: From secondary memory (Files)

Properties of Good Sorting Algorithm

1. Adaptive: O(n) when data nearly sorted

2. Stable: Equal elements maintain relative order
3. In-place: O(1) extra space needed
4. Online: Can sort while receiving data
5. Efficient: Minimizes comparisons and swaps

Comparison Complexity

For any comparison-based sort:

Minimum: Ω(n log n)

Cannot do better than O(n log n)

2. BUBBLE SORT - O(n²)

Algorithm
flag = false
while flag == false:
flag = true
for j = 0 to n-2:
if list[j] > list[j+1]:
swap(list[j], list[j+1])
flag = false

How It Works

Compares adjacent elements

Swaps if in wrong order
Largest element "bubbles up" to end
Repeats until sorted

Example Trace

Initial: 5 3 8 4 2
Pass 1: 3 5 4 2 8 (8 in position)
Pass 2: 3 4 2 5 8 (5 in position)
Pass 3: 2 3 4 5 8 (sorted)

Complexity

Best: O(n) - already sorted

Average: O(n²)
Worst: O(n²) - reverse sorted
Space: O(1)
Stable: Yes
Adaptive: Yes

Code
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

3. INSERTION SORT - O(n²)

Algorithm

for i = 1 to n-1:
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j = j - 1
arr[j+1] = key

How It Works

Builds sorted array one element at a time

Takes each element and inserts in correct position
Like sorting playing cards

Example Trace

Initial: 5 3 8 4 2
Pass 1: 3 5 8 4 2
Pass 2: 3 5 8 4 2
Pass 3: 3 4 5 8 2
Pass 4: 2 3 4 5 8

Complexity

Best: O(n) - already sorted

Average: O(n²)
 Worst: O(n²)
Space: O(1)
Stable: Yes
Adaptive: Yes

Advantages

Simple to implement
Efficient for small datasets
Efficient for nearly sorted data
Online sorting (sort while receiving data)

4. QUICK SORT - O(n log n) average

Algorithm

partition(low, high):
Choose pivot
Arrange pivot in correct position
Elements < pivot on left
Elements > pivot on right
Return partition index

quicksort(low, high):
if low < high:
pi = partition(low, high)
quicksort(low, pi-1)
quicksort(pi+1, high)

How It Works

Divide and conquer

Partition around pivot
Recursively sort sublists

Pivot Selection Strategies

1. First element - Simple but risky

2. Last element - Better
3. Middle element - Good
4. Median-of-three - Best for random data
5. Random - Avoids worst case

Example
Original: 8 5 9 2 1 7 6

Choose pivot = 7:
Left < 7: 5 2 1 6
Pivot: 7
Right > 7: 8 9

Recursively sort:
Left: 1 2 5 6
Right: 8 9

Result: 1 2 5 6 7 8 9

Complexity

Best: O(n log n) - balanced partitions

Average: O(n log n)
Worst: O(n²) - pivot always smallest/largest
Space: O(log n) - recursion stack
Stable: No
Adaptive: No

Advantages

Very fast average case

In-place sorting
Cache efficient
Most commonly used

Disadvantages

Worst case O(n²)

Not stable
Requires careful pivot selection

5. MERGE SORT - O(n log n) guaranteed

Algorithm
mergesort(left, right):
if left < right:
mid = (left + right) / 2
mergesort(left, mid)
mergesort(mid+1, right)
merge(left, mid, right)

merge(left, mid, right):

Compare elements from two halves
Place smaller in temporary array
Copy remaining elements

How It Works

Divide array into two halves

Recursively sort each half
Merge two sorted halves

Example

Original: 8 5 9 2 1 7 6 4

Divide: [8 5 9 2] [1 7 6 4]
[8 5][9 2] [1 7][6 4]
[8][5][9][2] [1][7][6][4]

Merge: [5 8][2 9] [1 7][4 6]

[2 5 8 9] [1 4 6 7]
[1 2 4 5 6 7 8 9]

Complexity

All cases: O(n log n) - GUARANTEED!

Space: O(n) - needs temporary array
Stable: Yes
Adaptive: No

Advantages

Guaranteed O(n log n)

Stable sorting
Good for linked lists
Predictable performance
 Disadvantages

Requires extra O(n) space

Slower than quick sort on average (more data movement)
Not in-place

6. HEAP SORT - O(n log n)

Algorithm

heapsort(arr, n):
Build max heap from array
for i = n-1 to 0:
Swap arr[0] with arr[i] (move largest to end)
Heapify root with heap size i-1

How It Works

Build max heap (largest at top)

Extract max element (place at end)
Reorganize remaining heap
Repeat until heap empty

Heap Properties

Parent at index i
Left child at 2i+1
Right child at 2i+2
Parent >= children (max heap)

Example
 Original: [25, 13, 17, 5, 8, 3]

Build heap: 25
/ \
13 17
/ \ /
5 8 3

Heap array: [25, 13, 17, 5, 8, 3]

Extract 25: [3, 13, 17, 5, 8] | 25

Heapify: [17, 13, 3, 5, 8] | 25

Extract 17: [8, 13, 3, 5] | 17, 25

...continue...

Final: [3, 5, 8, 13, 17, 25]

Complexity

All cases: O(n log n)

Space: O(1) - in-place
Stable: No
Adaptive: No

Advantages

Guaranteed O(n log n)

In-place (no extra space)
Good for memory-constrained systems

Disadvantages

Slower than quick sort on average

Not stable
More complex to implement

7. SORTING ALGORITHMS COMPARISON TABLE

Algorithm Best Average Worst Space Stable In-Place Adaptive
Bubble O(n) O(n²) O(n²) O(1) Yes Yes Yes
Selection O(n²) O(n²) O(n²) O(1) No Yes No
Insertion O(n) O(n²) O(n²) O(1) Yes Yes Yes
Merge O(n lg n) O(n lg n) O(n lg n) O(n) Yes No No
Algorithm Best Average Worst Space Stable In-Place Adaptive
Quick O(n lg n) O(n lg n) O(n²) O(lg n) No Yes No
Heap O(n lg n) O(n lg n) O(n lg n) O(1) No Yes No

8. CHOOSING THE RIGHT SORTING ALGORITHM

Guidelines

Use Bubble Sort:

Educational purposes
Nearly sorted small data
Not for production code

Use Insertion Sort:

Small datasets (n < 50)

Nearly sorted data
Online sorting
Practical implementation of theory

Use Merge Sort:

When O(n log n) guarantee required

Large datasets
External sorting (files)
Linked lists
When stability important

Use Quick Sort:

General-purpose sorting
Large datasets
When average O(n log n) acceptable
Cache-friendly operations
Most used in practice

Use Heap Sort:

When O(n log n) and O(1) space required

Real-time systems
Memory-constrained environments

Use Counting/Radix Sort:

When data is integers with limited range

O(n) time possible
For non-comparative sorting
 EXAM PREPARATION TIPS
Important Topics to Focus
1. Big-O Analysis - Asked every exam
2. Stack Applications - Especially recursion
3. Circular Queue - Algorithm and advantages
4. Linked List Operations - Insertion, deletion
5. Binary Tree Traversals - All three types
6. Sorting Algorithms - Comparison and complexity
7. BST Properties - Definition and applications

Study Strategy
Understand concepts - Not just memorize
Trace algorithms - Work examples by hand
Implement code - Write actual C programs
Solve previous papers - Multiple times
Compare algorithms - Know trade-offs
Visual learning - Draw trees, trace sorts

Exam Pattern
Q.1 Compulsory (6 parts, 2.5 marks each)
Choose 1 from each Unit II, III, IV
Total: 75 marks exam + 25 marks classwork

Time Management (3 Hours)

Q.1: 30 minutes
Unit II: 45 minutes
Unit III: 45 minutes
Unit IV: 45 minutes
Review: 15 minutes

Study Material Created: December 29, 2025 For: [Link] 3rd Semester Data Structures Status: Complete & Ready for
Exam