Introduction to Data Structures

A Data Structure is a way to organize and store data efficiently so that operations like access,
insertion, and deletion can be performed easily. It is essential for writing efficient algorithms.

1. Data Type and Data Structure

Data Type
A Data Type defines the type of data a variable can store. It determines the size and operations that
can be performed on the data.

Types of Data Types

1. Primitive Data Types: Integer, Float, Char, Boolean
2. Derived Data Types: Arrays, Pointers, Functions
3. Abstract Data Types (ADT): Stack, Queue, List, Graph, Tree

Data Structure and Its Classification

A Data Structure is a way of organizing and storing data efficiently. It is mainly classified into two
types:

1. Linear Data Structure

• Elements are stored in a sequential manner (one after another).
• Examples:
• Array
• Linked List
• Stack
• Queue

2. Non-Linear Data Structure

• Elements are connected in a hierarchical or graph-based structure.
• Examples:
• Tree
• Graph

2. Concept of Array
An array is a collection of elements of the same data type stored in contiguous memory
locations. It allows random access using an index.

Types of Arrays
1. One-Dimensional Array (1D Array): A list of elements stored in a single row.
 2. Two-Dimensional Array (2D Array): A matrix (table) with rows and columns.

3. One-Dimensional Array (1D Array)

A 1D array is a list of elements stored in a single row.
Example:
int arr[5] = {10, 20, 30, 40, 50}; // 1D array

Index 0 1 2 3 4
Value 10 20 30 40 50

4. Operations on 1D Array
(i) Insertion in an Array
Insertion means adding a new element at a specific index.
Steps:
1. Shift all elements to the right from the position where you want to insert.
2. Place the new element at the desired index.
3. Increase the size of the array.

Example (Practical Explanation)

Before Insertion:
arr = [10, 20, 30, 40, 50]
Inserting 25 at index 2
arr = [10, 20, 25, 30, 40, 50]

(ii) Deletion in an Array

Deletion means removing an element from a specific index.
Steps:
1. Shift all elements to the left after the deleted index.
2. Reduce the size of the array.

Example (Practical Explanation)

Before Deletion:
arr = [10, 20, 30, 40, 50]
Deleting element at index 2 (30)
arr = [10, 20, 40, 50]
(iii) Traversal of an Array
Traversal means accessing each element one by one.
Example:
arr = [10, 20, 30, 40, 50]
Output: 10 → 20 → 30 → 40 → 50

Traversal is used to display array elements or process them in a loop.

5. Two-Dimensional Array (2D Array)

A 2D array is an array of arrays, used to store data in a tabular format.
Example:
int matrix[2][3] = { {1, 2, 3}, {4, 5, 6} };

Row/Col 0 1 2
0 1 2 3
1 4 5 6

Final Summary for Exam

1. Data Type: Defines the type of data (int, float, char).
2. Data Structure: Organized way to store and process data (Array, Stack, Queue).
3. 1D Array: Linear storage structure with index-based access.
4. Operations on 1D Array:
• Insertion: Adding an element at a position.
• Deletion: Removing an element from a position.
• Traversal: Accessing elements one by one.
5. 2D Array: Stores elements in a row-column format (Matrix).
Agar koi point aur explain karna ho to batao! Exam ke liye Best of Luck! 🎯🔥

Linked List in Data Structure

1. Concept of Linked List
A Linked List is a linear data structure where elements (called nodes) are connected using
pointers. Unlike an array, a linked list does not store elements in contiguous memory locations.
Instead, each node contains:
1. Data (Value of the node)
2. Pointer (Address of the next node)
Advantages of Linked List over Arrays
✔ Dynamic Size: Can grow or shrink as needed.
✔ Efficient Insertions/Deletions: No need to shift elements.

Disadvantages of Linked List

❌ Extra Memory: Requires additional storage for pointers.
❌ Sequential Access: Cannot access elements directly using an index.

2. Types of Linked Lists

(i) Singly Linked List
Each node points to the next node.
Head → [Data | Next] → [Data | Next] → [Data | NULL]

(ii) Doubly Linked List

Each node has two pointers: one to the next node and one to the previous node.
NULL ← [Prev | Data | Next] ↔ [Prev | Data | Next] → NULL

(iii) Circular Linked List

The last node connects back to the first node, forming a circular structure.
• Singly Circular Linked List: Last node points to the first node.
• Doubly Circular Linked List: Last node points to the first and first node points to the last.

3. Operations on Linked List

(i) Insertion in a Linked List
Insertion can be done at:
1. Beginning: New node becomes the head.
2. End: New node is linked at the last position.
3. Middle (After a given node): A new node is inserted between two existing nodes.

Example (Practical Explanation)

Before Insertion:
Head → [10 | Next] → [20 | Next] → [30 | NULL]

After inserting 15 after 10:

Head → [10 | Next] → [15 | Next] → [20 | Next] → [30 | NULL]
(ii) Deletion in a Linked List
Deletion can be done at:
1. Beginning: Head moves to the next node.
2. End: Last node is removed.
3. Middle (Specific Node): The node is bypassed by changing pointers.

Example (Practical Explanation)

Before Deletion:
Head → [10 | Next] → [20 | Next] → [30 | NULL]

After deleting 20:

Head → [10 | Next] → [30 | NULL]

4. List Manipulation with Pointers

Pointers are used to dynamically allocate and deallocate memory in a linked list.
Important Pointer Operations:
✅ Traversing the List: Moving from node to node using Next pointers.
✅ Inserting a Node: Adjusting Next pointers to link the new node.
✅ Deleting a Node: Updating Next pointers to bypass the deleted node.

Example:
If ptr points to a node, we can access the next node using:
ptr = ptr->next;

5. Applications of Linked List

🔹 Dynamic Memory Allocation: Used in OS memory management.
🔹 Implementing Stacks and Queues: Linked lists are used to implement these data structures.
🔹 Graph Representation: Used in adjacency list representation of graphs.
🔹 Undo/Redo Functionality: Used in text editors for maintaining previous states.
🔹 Music or Image Viewer: Uses circular linked lists for navigation.

Final Summary for Exam

1. Linked List is a dynamic data structure where nodes are connected using pointers.
2. Types of Linked Lists:
• Singly Linked List: Each node points to the next.
• Doubly Linked List: Each node has two pointers (next & previous).
• Circular Linked List: Last node connects to the first.
 3. Operations in Linked List:
• Insertion (At Beginning, End, or Middle).
• Deletion (At Beginning, End, or Middle).
4. List Manipulation with Pointers: Used to traverse, insert, and delete elements dynamically.
5. Applications: Used in stacks, queues, memory management, and more.
Agar koi aur concept nahi samajh aa raha ho to batao! All the Best for Your Exam! 🔥📖

Stack in Data Structure

1. Definition of Stack
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. This
means that the last element added (pushed) to the stack is the first one to be removed (popped).

Example of Stack in Real Life

✔ A stack of plates: The plate placed last is picked up first.
✔ Undo/Redo feature in text editors.

2. Stack Operations
(i) Push Operation (Insertion)
• Adds an element to the top of the stack.
• If the stack is full, it results in Stack Overflow.

(ii) Pop Operation (Deletion)

• Removes the top element from the stack.
• If the stack is empty, it results in Stack Underflow.

(iii) Peek (Top)

• Returns the top element without removing it.

(iv) IsEmpty()
• Checks whether the stack is empty.

(v) IsFull()
• Checks whether the stack is full (in case of array-based implementation).
3. Implementation of Stack
(i) Using Array
A stack can be implemented using an array where elements are added or removed from the top.

Operations:
1. Push: Insert an element at the top.
2. Pop: Remove an element from the top.
3. Peek: Return the top element.

Index 0 1 2 3 4
Stack 10 20 30 40 50 (Top)
After popping 50:

Index 0 1 2 3
Stack 10 20 30 40 (Top)

(ii) Using Linked List

A linked list-based stack does not have a fixed size and grows dynamically.
Each node contains:
• Data (value)
• Pointer to next node (link to next element in the stack)

Head (Top) 40 → 30 → 20 → 10 → NULL

• Push(50): Add a node at the beginning.
• Pop(): Remove the head node.

4. Applications of Stack
(i) Expression Conversion and Evaluation
Stack is widely used in converting and evaluating expressions.

Infix, Prefix, and Postfix Expressions

1. Infix Expression: Operator is between operands.
• Example: A + B
2. Prefix Expression (Polish Notation): Operator comes before operands.
• Example: + A B
3. Postfix Expression (Reverse Polish Notation): Operator comes after operands.
• Example: A B +

(ii) Conversion of Infix to Postfix Using Stack

To convert infix expressions to postfix, follow these rules:
 1. Operands (A, B, C, etc.) go directly to the output.
2. *Operators (+, -, , /, etc.) are pushed onto a stack.
3. Higher precedence operators are pushed first.
4. Parentheses ( ) help in prioritization.

Example:
Convert (A + B) * C to postfix.
Solution: A B + C *

(iii) Postfix Expression Evaluation Using Stack

Postfix expressions are evaluated using a stack.
Steps for Evaluation:
1. Read from left to right.
2. Push operands onto the stack.
3. When an operator is encountered, pop two elements, apply the operator, and push the
result back.
4. Continue until the final result is obtained.
Example:
Evaluate: 2 3 + 4 *
Step-by-Step:
• Push 2
• Push 3
• + → Pop 2 and 3, Add (2 + 3 = 5), Push 5
• Push 4
• * → Pop 5 and 4, Multiply (5 * 4 = 20), Push 20
• Final result = 20

Final Summary for Exam

1. Stack follows LIFO principle (Last In, First Out).
2. Operations in Stack: Push, Pop, Peek, IsEmpty, IsFull.
3. Implementation:
• Using Array (Fixed size, faster).
• Using Linked List (Dynamic size, extra memory for pointers).
4. Applications of Stack:
• Expression Conversion (Infix to Postfix, Prefix)
• Postfix Evaluation (Using Stack)
• Backtracking (Maze Solving, Undo/Redo in Text Editors)
• Function Calls (Recursion uses stack internally).
Agar koi point aur samajhna ho to batao! Best of Luck for Your Exam! 🔥📖
Queues in Data Structure
1. Introduction to Queue
A queue is a linear data structure that follows the FIFO (First In, First Out) principle. This
means that the element added first will be removed first.

Example of Queue in Real Life

✔ A queue of people at a ticket counter – The person who comes first gets served first.
✔ Print Queue in a Printer – The first document sent is printed first.

2. Types of Queues
(i) Simple Queue (Linear Queue)
• Follows FIFO (First In, First Out).
• Insertion (Enqueue) happens at the rear, and deletion (Dequeue) happens at the front.
| Front → | 10 | 20 | 30 | 40 | Rear → 50 |

(ii) Circular Queue

• The rear and front wrap around to form a circular structure.
• Prevents wastage of space in a simple queue.
Example of a Circular Queue (after inserting and deleting elements):

Index 0 1 2 3 4
Queue 30 40 50 (Rear) 10 (Front) 20

(iii) Priority Queue

• Every element has a priority associated with it.
• The element with the highest priority is dequeued first, not necessarily the one that was
inserted first.
Example (Tasks with different priority levels):

Task Priority
Task A 2 (High)
Task B 1 (Low)
Task C 3 (Highest)
Order of execution: Task C → Task A → Task B.

(iv) Double-Ended Queue (Deque)

• Elements can be inserted and deleted from both ends.
• Two types:
1. Input-restricted deque: Insertion at one end, deletion at both ends.
 2. Output-restricted deque: Deletion at one end, insertion at both ends.
Example:
| Front → 20 | 30 | 40 (Rear) → |
• Insert at Front: New element added at the front.
• Insert at Rear: New element added at the rear.

3. Queue Operations
(i) Enqueue (Insertion)
• Adds an element at the rear of the queue.
• In circular queue, the rear moves in a circular manner.

(ii) Dequeue (Deletion)

• Removes an element from the front of the queue.
• In circular queue, the front moves in a circular manner.

(iii) Peek (Front)

• Returns the element at the front without removing it.

(iv) isEmpty()
• Checks if the queue is empty.

(v) isFull()
• Checks if the queue is full (applicable for array implementation).

4. Implementation of Queue
(i) Using Array
• Uses a fixed-size array.
• Needs a front and rear pointer.
Example of a queue using an array:

Index 0 1 2 3 4
Queue 10 20 30 40 50 (Rear)
Operations:
• Enqueue(60): Adds 60 at the rear.
• Dequeue(): Removes 10 from the front.
After Dequeue:
 Index 0 1 2 3 4
Queue X 20 30 40 50
Front → 20 Rear → 50

(ii) Using Linked List

• A linked list-based queue does not have a fixed size.
• Uses nodes, each containing:
• Data (value)
• Pointer to next node
Example:
| Front (Head) → 10 → 20 → 30 → 40 → 50 (Rear) |
• Enqueue(60): Add a node at the rear.
• Dequeue(): Remove the head node (10).
After Dequeue:
| Front (Head) → 20 → 30 → 40 → 50 (Rear) |

5. Applications of Queue
(i) CPU Scheduling
• Round Robin Scheduling uses a queue to allocate CPU time to processes.

(ii) Printer Queue

• When multiple documents are sent to a printer, they are printed in FIFO order.

(iii) Call Center System

• Customer calls are answered in the order they were received.

(iv) Data Streaming

• In online video buffering, data packets are processed in the order they arrive.

Final Summary for Exam

1. Queue follows FIFO (First In, First Out).
2. Types of Queues:
• Simple Queue (Linear).
• Circular Queue (Efficient memory use).
• Priority Queue (Elements dequeued based on priority).
• Double-Ended Queue (Deque) (Insertion/Deletion at both ends).
 3. Operations in Queue: Enqueue, Dequeue, Peek, isEmpty, isFull.
4. Implementation:
• Using Array (Fixed size, simple).
• Using Linked List (Dynamic size, requires extra memory).
5. Applications of Queue:
• CPU Scheduling
• Printer Queue
• Call Centers
• Data Streaming (Buffering in Videos)
Agar koi aur topic clear karna ho to batao! Best of Luck for Your Exam! 🔥📖

Trees in Data Structure

1. Definition of Tree
A tree is a non-linear data structure that consists of nodes connected by edges. It is a hierarchical
structure where:
• The topmost node is called the root.
• Each node contains a data value and pointers to child nodes.
• The last nodes in a tree (without children) are called leaf nodes.

2. Types of Trees
1. General Tree: Each node can have any number of children.
2. Binary Tree: Each node has at most two children (Left & Right).
3. Binary Search Tree (BST): A binary tree with the left subtree containing smaller values and
the right subtree containing larger values.
4. AVL Tree: A self-balancing BST, where the difference in height of left and right subtrees is
at most 1.
5. B-Tree: A self-balancing tree used for database indexing, where each node has multiple
children.
6. B+ Tree: An improved version of the B-Tree where all values are stored in leaf nodes for
faster searching.

3. Binary Tree
Properties of Binary Trees
1. Maximum nodes at level L = 2^L
2. Maximum nodes in a tree of height h = 2^(h+1) - 1
3. Minimum height of a binary tree with N nodes = log₂(N+1)
4. Maximum edges in a tree with N nodes = N-1
4. Binary Tree Operations
(i) Insertion in Binary Tree
• If the root is empty, insert the first node.
• Else, traverse the tree and insert the new node at the first empty position.

(ii) Deletion in Binary Tree

1. Find the node to be deleted.
2. Replace it with the deepest node in the tree.
3. Remove the deepest node.

(iii) Searching in Binary Tree

• Traverse the tree to find the target node.
• If found, return the node; otherwise, return NULL.

5. Tree Traversal Algorithms

Tree traversal means visiting all the nodes in a specific order. There are three types of traversal:

(i) Preorder Traversal (Root → Left → Right)

1. Visit the root node.
2. Recursively traverse the left subtree.
3. Recursively traverse the right subtree.

Example:
A
/ \
B C
/ \ \
D E F

Preorder Traversal Output: A → B → D → E → C → F

(ii) Inorder Traversal (Left → Root → Right)

1. Recursively traverse the left subtree.
2. Visit the root node.
3. Recursively traverse the right subtree.

Example:
Inorder Traversal Output: D → B → E → A → C → F
(iii) Postorder Traversal (Left → Right → Root)
1. Recursively traverse the left subtree.
2. Recursively traverse the right subtree.
3. Visit the root node.

Example:
Postorder Traversal Output: D → E → B → F → C → A

6. Binary Search Tree (BST)

A Binary Search Tree is a binary tree with:
• Left subtree → Contains values less than the root.
• Right subtree → Contains values greater than the root.

BST Operations
(i) Insertion in BST
• Start from the root.
• If the new value is less than the root, go to the left subtree.
• If the new value is greater, go to the right subtree.

(ii) Deletion in BST

1. Case 1: Node has no children → Simply remove it.
2. Case 2: Node has one child → Replace it with its child.
3. Case 3: Node has two children → Replace it with inorder successor.

(iii) Searching in BST

• Start from the root.
• If the value matches, return it.
• If the value is smaller, search in the left subtree.
• If the value is larger, search in the right subtree.

7. AVL Tree (Self-Balancing BST)

An AVL Tree is a self-balancing BST where the height difference (balance factor) between left
and right subtrees is at most 1.

AVL Tree Rotations

To maintain balance, AVL trees perform rotations:
1. Right Rotation (LL Rotation)
2. Left Rotation (RR Rotation)
3. Left-Right Rotation (LR Rotation)
 4. Right-Left Rotation (RL Rotation)

8. B-Tree
A B-Tree is a self-balancing search tree where:
• Each node has multiple children (not just 2).
• Used in databases and file systems.
• Ensures logarithmic search time.

Example of B-Tree (Order 3)

[30]
/ \
[10] [40, 50]

9. B+ Tree
• Enhanced version of B-Tree used in databases.
• All values are stored in leaf nodes for faster search.

Example of B+ Tree (Order 3)

[30]
/ \
[10, 20] [40, 50]

• The internal nodes only store keys, while the actual data is in leaf nodes.

10. Summary for Exam

Topic Key Points
Tree Hierarchical data structure.
Binary Tree Max 2 children per node.
Preorder (Root → Left → Right), Inorder (Left → Root → Right),
Tree Traversals
Postorder (Left → Right → Root).
Binary Search Tree
Left subtree < Root < Right subtree.
(BST)
AVL Tree Self-balancing BST (Balance factor ≤ 1).
B-Tree Used in databases, multiple children per node.
B+ Tree Improved B-Tree, values only in leaf nodes.

Agar aur koi topic clear karna ho to batao! Best of Luck for Your Exam! 🎯📚🔥
Searching in Data Structure
Searching is a process of finding an element in a given data structure (like an array, linked list, or
tree).

1. Types of Searching Algorithms

Best
Search Type Concept Worst Case Complexity
Case
Check each element one
Linear Search O(1) O(n) O(n)
by one
Repeatedly divide array
Binary Search O(1) O(log n) O(log n)
in half
Binary Search Tree Search using tree O(log n) (Balanced), O(n)
O(1) O(log n)
(BST) structure (Unbalanced)

2. Linear Search Algorithm

Definition:
Linear Search checks each element of the array one by one until the required element is found.

Algorithm (Steps)
1. Start from index 0.
2. Compare the element with the target value.
3. If found, return the index.
4. If not found, move to the next element.
5. If end of the array is reached, return "Not Found".

Example
🔹 Array = [10, 25, 36, 42, 50]
🔹 Search for 42

Step Element Checked Found?

1 10 ❌
2 25 ❌
3 36 ❌
4 42 ✅ (Found at index 3)
✅ Best Case: O(1) (Element is at the first index).
❌ Worst Case: O(n) (Element is at last index or not present).
3. Binary Search Algorithm
Definition:
Binary Search divides the array into two halves at each step. The array must be sorted before
applying Binary Search.

Algorithm (Steps)
1. Sort the array (if not sorted).
2. Set low = 0 and high = last index.
3. Find mid = (low + high) / 2.
4. If arr[mid] == target, return mid.
5. If arr[mid] < target, search in right half (low = mid + 1).
6. If arr[mid] > target, search in left half (high = mid - 1).
7. Repeat until found or low > high (element not present).

Example
🔹 Sorted Array = [10, 20, 30, 40, 50, 60, 70]
🔹 Search for 50

Step Low High Mid Mid Value Found?

1 0 6 3 40 ❌ (50 > 40, search right)
2 4 6 5 60 ❌ (50 < 60, search left)
3 4 4 4 50 ✅ (Found at index 4)
✅ Best Case: O(1) (Element at the middle).
❌ Worst Case: O(log n) (Repeatedly dividing the array).

4. Binary Search Tree (BST)

Definition:
A Binary Search Tree (BST) is a tree where:
✅ Left subtree contains smaller values.
✅ Right subtree contains larger values.
✅ Left & Right subtrees are also BSTs.

Example of a BST
50
/ \
30 70
/ \ / \
20 40 60 80

(i) Construction of a BST

1. Start with an empty tree.
 2. Insert the first element as the root.
3. For each new element:
• If smaller, go left.
• If larger, go right.
4. Repeat until the correct position is found.
✅ Time Complexity (Insertion): O(log n) for balanced BST, O(n) for skewed BST.

(ii) Insertion in BST

Insert 45 into the BST below:
50
/ \
30 70
/ \ / \
20 40 60 80

✅ Since 45 < 50 → Left, 45 > 30 → Right, 45 > 40 → Insert at Right of 40

Updated BST:
50
/ \
30 70
/ \ / \
20 40 60 80
\
45

✅ Time Complexity: O(log n) (Balanced), O(n) (Unbalanced).

(iii) Deletion in BST

To delete a node X from a BST:
1. Case 1: Leaf Node (No Child) → Simply delete it.
2. Case 2: One Child → Replace with its only child.
3. Case 3: Two Children → Replace with:
• Inorder Successor (smallest value in right subtree) OR
• Inorder Predecessor (largest value in left subtree).

(iv) Search in BST

1. If root == target → Found ✅
2. If target < root → Search left subtree.
3. If target > root → Search right subtree.
4. If reached NULL, element is not present.
✅ Time Complexity: O(log n) (Balanced), O(n) (Unbalanced).
5. Complexity Analysis of Searching Algorithms
Algorithm Best Case Worst Case Average Case
Linear Search O(1) O(n) O(n)
Binary Search O(1) O(log n) O(log n)
BST Search O(1) O(log n) (Balanced) / O(n) (Unbalanced) O(log n)

6. Summary for Exam

Topic Key Points
Linear Search Check each element one by one. O(n) complexity.
Binary Search Divide & conquer method. Works on sorted arrays. O(log n) complexity.
Stores data in tree format for fast search, insertion & deletion. O(log n)
BST
complexity.
Insertion in BST Smaller → Left, Larger → Right.
Deletion in BST Three cases (Leaf node, One child, Two children).
Search in BST Compare & move left/right recursively.

Agar koi aur doubt ho ya kisi topic par aur explanation chahiye ho to batao! Best of Luck for Your
Exam! 🎯📚🔥

Sorting Algorithms in Data Structure

Sorting is the process of arranging elements in a specific order, usually ascending or descending.
Sorting helps in searching, data analysis, and efficient retrieval.

1. Types of Sorting Algorithms

Algorithm Best Case Worst Case Average Case Time Complexity
Bubble Sort O(n) O(n²) O(n²) Slow for large data
Insertion Sort O(n) O(n²) O(n²) Good for small/partially sorted data
Selection Sort O(n²) O(n²) O(n²) Inefficient for large data
Quick Sort O(n log n) O(n²) O(n log n) Fastest sorting in most cases
Merge Sort O(n log n) O(n log n) O(n log n) Good for large datasets
Heap Sort O(n log n) O(n log n) O(n log n) Efficient for priority-based sorting
Radix Sort O(nk) O(nk) O(nk) Non-comparative sorting
Tree Sort O(n log n) O(n²) O(n log n) Uses BST for sorting

2. Bubble Sort
Definition: Bubble Sort repeatedly swaps adjacent elements if they are in the wrong order.
✅ Simple but inefficient.
Algorithm Steps
1. Start from index 0.
2. Compare adjacent elements: swap if arr[i] > arr[i+1].
3. Repeat for n-1 passes.

Example
🔹 Unsorted Array: [5, 2, 9, 1, 6]
🔹 Step-by-Step Execution

Pass Array State

1st [2, 5, 1, 6, 9]
2nd [2, 1, 5, 6, 9]
3rd [1, 2, 5, 6, 9]
4th [1, 2, 5, 6, 9] (Sorted ✅)
❌ Worst Case Complexity: O(n²)
✅ Best Case (Already Sorted): O(n)

3. Insertion Sort
Definition: Builds a sorted array one element at a time by inserting each element at its correct
position.

Algorithm Steps
1. Assume the first element is sorted.
2. Pick the next element and insert it in the correct position in the sorted part.
3. Repeat until all elements are sorted.

Example
🔹 Unsorted Array: [7, 3, 5, 1]

Step Array State

Start [7, 3, 5, 1]
Insert 3 [3, 7, 5, 1]
Insert 5 [3, 5, 7, 1]
Insert 1 [1, 3, 5, 7] (Sorted ✅)
❌ Worst Case Complexity: O(n²)
✅ Best Case Complexity: O(n) (Already sorted).

4. Selection Sort
Definition: Selection Sort finds the smallest element and swaps it with the first unsorted element.
Algorithm Steps
1. Find the smallest element in the array.
2. Swap it with the first unsorted element.
3. Repeat for the remaining elements.

Example
🔹 Unsorted Array: [29, 10, 14, 37, 13]

Pass Array State

1st [10, 29, 14, 37, 13]
2nd [10, 13, 14, 37, 29]
3rd [10, 13, 14, 29, 37]
4th [10, 13, 14, 29, 37] (Sorted ✅)
❌ Worst Case Complexity: O(n²)
✅ Best Case Complexity: O(n²) (No improvement).

5. Quick Sort
Definition: Quick Sort picks a pivot element and partitions the array into two halves: smaller
elements on the left and larger on the right.

Algorithm Steps
1. Choose a pivot (typically last/first/middle element).
2. Partition the array into left (smaller) & right (larger) parts.
3. Recursively repeat for left & right parts.

Example
🔹 Unsorted Array: [10, 80, 30, 90, 40, 50, 70]
🔹 Pivot = 50

Step Left Subarray Pivot Right Subarray

Partition [10, 30, 40] 50 [80, 90, 70]
Sort Left [10, 30, 40]
Sort Right [70, 80, 90]
Final Sorted [10, 30, 40, 50, 70, 80, 90] ✅
❌ Worst Case Complexity: O(n²) (When already sorted).
✅ Best/Average Complexity: O(n log n).

6. Merge Sort
Definition: Merge Sort divides the array into halves, sorts each half, and merges them back.
Algorithm Steps
1. Divide the array into two halves.
2. Recursively sort both halves.
3. Merge the sorted halves.
🔹 Unsorted Array: [12, 11, 13, 5, 6, 7]

Step Left Half Right Half

Split [12, 11, 13] [5, 6, 7]
Sort [11, 12, 13] [5, 6, 7]
Merge [5, 6, 7, 11, 12, 13] ✅
✅ Time Complexity: O(n log n) (Always).

7. Heap Sort
Definition: Heap Sort converts the array into a Heap (binary tree) and extracts the
maximum/minimum repeatedly.
✅ Time Complexity: O(n log n).

8. Radix Sort
Definition: Radix Sort sorts elements digit by digit from the least significant digit (LSD) to the
most significant digit (MSD).
✅ Time Complexity: O(nk).

9. Tree Sort
Definition: Tree Sort inserts elements into a Binary Search Tree (BST) and performs inorder
traversal to retrieve sorted elements.
✅ Time Complexity: O(n log n).

10. External Sorting

Definition: External Sorting is used when the dataset is too large to fit in RAM. It divides the data
into chunks, sorts them separately, and merges the sorted chunks.
✅ Used in databases & big data applications.
Summary Table
Algorithm Best Case Worst Case Average Case Stability
Bubble Sort O(n) O(n²) O(n²) ✅ Stable
Insertion Sort O(n) O(n²) O(n²) ✅ Stable
Selection Sort O(n²) O(n²) O(n²) ❌ Unstable
Quick Sort O(n log n) O(n²) O(n log n) ❌ Unstable
Merge Sort O(n log n) O(n log n) O(n log n) ✅ Stable
Heap Sort O(n log n) O(n log n) O(n log n) ❌ Unstable
Radix Sort O(nk) O(nk) O(nk) ✅ Stable

🔥 Exam Tip:
✔ Focus on Quick Sort & Merge Sort (Efficient).
✔ Remember Bubble, Selection & Insertion Sort (Basic).
✔ Learn Heap & Radix Sort for advanced cases.
🔹 Let me know if you need more details! 🚀📚