UNIT I – Algorithms and Sorting
[Sessions: 9]
1. Introduction to Algorithms
Definition: An algorithm is a finite sequence of well-defined instructions for solving a
computational problem.
Examples: Recipe for cooking food, Long division method, Binary search.
Characteristics of a Good Algorithm:
1. Input – Zero or more input values.
2. Output – At least one output is produced.
3. Finiteness – Must terminate after finite steps.
4. Definiteness – Each step must be clear and unambiguous.
5. Effectiveness – Each instruction must be basic and feasible.
2. Analyzing Algorithms
Why Analyze? Multiple algorithms may exist for a problem. Analysis helps to choose the
most efficient one.
Types of Analysis:
- Best Case (Ω): Minimum steps.
- Worst Case (O): Maximum steps.
- Average Case (Θ): Expected steps.
Example (Linear Search):
Best case → O(1), Worst case → O(n), Average case → O(n).
3. Complexity of Algorithms
Time Complexity: Running time as a function of input size.
Space Complexity: Memory used.
Asymptotic Notations:
- Big-O (O): Upper bound.
- Big-Ω (Ω): Lower bound.
- Big-Θ (Θ): Tight bound.
4. Growth of Functions
Common Orders of Growth:
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n) < O(n!).
Example: Binary search O(log n) is much faster than Linear search O(n).
5. Performance Measurements
Methods:
- Theoretical (Asymptotic Analysis).
- Empirical (Experimental Testing).
Factors Affecting Performance: Algorithm design, Input size, Hardware, Software.
6. Sorting and Order Statistics
Sorting: Arranging elements in ascending/descending order.
Applications: Searching, Databases, Information retrieval.
Order Statistics:
- Minimum (1st order), Maximum (nth order), Median (middle element), k-th smallest
element.
7. Sorting Algorithms
Shell Sort:
- Improves insertion sort using gaps.
- Complexity: O(n log n) to O(n²).
- Space: O(1). Not stable.
Quick Sort:
- Divide & Conquer.
- Best: O(n log n), Worst: O(n²), Average: O(n log n).
- Not stable.
Merge Sort:
- Divide & Conquer with merging.
- O(n log n) in all cases. Stable. Requires O(n) space.
Heap Sort:
- Uses binary heap.
- O(n log n). Space O(1). Not stable.
8. Comparison of Sorting Algorithms
Algorithm Best Case Average Worst Case Space Stable
Case
Quick Sort O(n log n) O(n log n) O(n²) O(log n) No
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes
Heap Sort O(n log n) O(n log n) O(n log n) O(1) No
Shell Sort O(n log n) - O(n²) O(1) No
9. Sorting in Linear Time
Counting Sort:
- Works when range is small.
- O(n + k).
Radix Sort:
- Sorts digit by digit.
- O(d(n + k)), where d = digits.
Bucket Sort:
- Distributes elements into buckets.
- O(n + k).
