■ Algorithms & Sorting Techniques – B.
Tech Notes
Introduction to Algorithms
An algorithm is a finite sequence of well-defined steps to solve a problem. It takes input, performs
processing, and produces output. Algorithms should be correct, efficient, and easy to understand.
Analyzing Algorithms
Analysis of algorithms is the process of finding the computational complexity of algorithms—the
amount of time, storage, or other resources needed to execute them. Main goals are to compare
multiple solutions and choose the best one.
Complexity of Algorithms
The complexity of an algorithm is measured in terms of: - **Time Complexity:** Number of
operations executed. - **Space Complexity:** Amount of memory used.
Growth of Functions
Growth functions describe how runtime grows with input size (n). Common notations: - **Big-O
(O):** Worst-case growth. - **Theta (Θ):** Average/Exact growth. - **Omega (Ω):** Best-case
growth.
Performance Measurements
Algorithm performance can be measured in: - Execution Time - Memory Usage - Disk I/O
Operations - Network Usage (if applicable)
Sorting and Order Statistics
Sorting is the process of arranging elements in a specific order (ascending/descending). Order
statistics refer to finding elements based on their rank (e.g., minimum, maximum, kth smallest).
Shell Sort
Shell Sort is an optimization of Insertion Sort. It allows exchanges of elements far apart.
Complexity: O(n log n) to O(n^2) depending on gap sequence.
Quick Sort
Quick Sort is a divide-and-conquer algorithm: 1. Choose a pivot. 2. Partition array into elements
less than and greater than pivot. 3. Recursively sort partitions. Average Complexity: O(n log n),
Worst Case: O(n^2).
Merge Sort
Merge Sort is a stable divide-and-conquer algorithm: 1. Divide array into two halves. 2. Recursively
sort each half. 3. Merge sorted halves. Complexity: O(n log n) in all cases.
Heap Sort
Heap Sort uses a binary heap data structure: 1. Build max-heap. 2. Repeatedly extract the
maximum element. Complexity: O(n log n). Requires no extra space (in-place).
Comparison of Sorting Algorithms
Comparison based on Time Complexity, Space Complexity, Stability: - Quick Sort: Fastest on
average, not stable. - Merge Sort: Stable, requires O(n) extra space. - Heap Sort: In-place, not
stable. - Shell Sort: Efficient for small/medium datasets.
Sorting in Linear Time
Some algorithms can sort in O(n) time when keys are integers in limited range: - Counting Sort -
Radix Sort - Bucket Sort
