Sorting Algorithms in DSA
Presented by: Yash Priyam 24BCE10474 Presented to: Dr. Raghavendra Mishra
CONTENTS
1. Introduction to Sorting Algorithms 2. Types of Comparison-Based
Sorting Algorithms
3. Key Characteristics and Trade-offs 4. Conclusion
01
Introduction to Sorting Algorithms
Introduction to Sorting Algorithms
Definition and Importance
• Sorting algorithms arrange elements in a specific order (ascending/descending).
• Fundamental for efficient searching, data analysis, and optimization.
• Used in databases, machine learning, and real-world applications.
Common Use Cases
• Organizing large datasets for faster retrieval.
• Preparing data for algorithms like binary search.
• Enhancing performance in applications like e-commerce and finance.
Types of Sorting Algorithms
Simple Sorting Algorithms
Bubble Sort Selection Sort Insertion Sort
• Repeatedly swaps adjacent elements if • Builds the sorted array one element at
• Selects the smallest element and
in wrong order. a time.
swaps it with the first unsorted element.
• Time Complexity: O(n²) in worst and • Efficient for small or nearly sorted
average cases. • Time Complexity: O(n²) in all cases. datasets.
• Space Complexity: O(1) (in-place). • Space Complexity: O(1) (in-place). • Time Complexity: O(n²) in worst and
average cases, O(n) in best case.
• Space Complexity: O(1) (in-place).
Advanced Sorting Algorithms
1 2
Merge Sort Quick Sort
• Divide-and-conquer approach (recursively splits and merges). • Pivot-based partitioning (divide-and-conquer).
• Stable sorting algorithm. • Generally faster in practice than Merge Sort.
• Time Complexity: O(n log n) in all cases. • Time Complexity: O(n log n) average case, O(n²) worst case.
• Space Complexity: O(n) (requires extra space). • Space Complexity: O(log n) (due to recursion stack).
Algorithm Best Case Average Case Worst Case Space Complexity Stability
Bubble Sort O(n) O(n²) O(n²) O(1) Stable
Selection Sort O(n²) O(n²) O(n²) O(1) Unstable
Insertion Sort O(n) O(n²) O(n²) O(1) Stable
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Stable
Quick Sort O(n log n) O(n log n) O(n²) O(log n) Unstable
Key Characteristics
1 2 3
Time Complexity Comparison Space Efficiency Stability
• Fastest for Large Datasets: Merge Sort • In-Place Sorting: Bubble Sort, Selection • Stable Algorithms: Bubble Sort, Insertion
and Quick Sort (O(n log n)). Sort, Insertion Sort (O(1)). Sort, Merge Sort.
• Slowest: Bubble Sort, Selection Sort, • Unstable Algorithms: Selection Sort,
• Extra Space Required: Merge Sort (O(n)).
Insertion Sort (O(n²)). Quick Sort.
Conclusion
Summary
• Comparison-based sorting algorithms vary in efficiency, stability, and space
usage.
• Selection Sort, Bubble Sort, and Insertion Sort are simple but inefficient for large
datasets.
• Merge Sort and Quick Sort are more efficient for large-scale sorting.
Thank You
