is used to rearrange a given array or list of elements according to a comparison operator on the elements.
Sorting Algorithm
is used to decide the new order of elements in the respective data structure
Comparison Operator
What are the applications of sorting algorithms
Searching Algorithms
Data Management
Database Optimization
Machine Learning
Data Analysis
Operating Systems
Sorting is often a crucial step in search algorithms like binary search and ternary search. A lot of Greedy Algorithms use sorting as a first step to apply Greedy Approach. For example Activity Selection, Fractional Knapsack, Weighted Job Scheduling, etc.
Searching Algorithms
Sorting data makes it easier to search, retrieve, and analyze. For example the order by operations in SQL queries requires sorting
Data Management
Sorting data in databases improves query performance. We preprocess the data by sorting so that efficient searching can be applied
Database Optimization
Sorting is used to prepare data for training machine learning models
Machine Learning
Sorting helps in identifying patterns, trends, and outliers in datasets. It plays a vital role in statistical analysis, financial modeling, and other data-driven fields
Data Analysis
Sorting algorithms are used in operating systems for tasks like task scheduling, memory management, and file system organizations
Operating Systems
Types of Sorting Algorithms
Bubble Sort
Insertion Sort
Selection Sort
Merge Sort
Quick Sort
Heap Sort
Bogo Sort
Repeatedly compares and swaps adjacent elements if they are in the wrong order. SImple but inefficient for large data (O(n2))
Bubble Sort
Builds the sorted array one item at a time by inserting each element into its proper position. Efficient for small or nearly sorted data
Insertion Sort
Selects the smallest (or largest) element and places it in the correct position, Easy to understand but always O(n2).
Selection Sort
Divides the array into halves, recursively sors each half, and merges them. Efficient and stable with O(n log n)
Merge Sort
Pick a pivot element, partitions the array, and sorts each partition recursively. Very fast in practice, average case O(n log n)
Quick Sort
Builds a binary heap from the data, then repeatedly extracts the maximum (or minimum). Good worst-case performance (O(n log n))
Heap Sort
Randomly shuffles the array until it becomes sorted. Highly inefficient and used mostly for teaching or fun. Average time complexity is O(n!)
Bogo Sort
What are the Characteristics of Sorting?
Time Complexity
Space Complexity
Stability
In-Place Sorting
Adaptivity
a measure of how long it takes to run an algorithm, is used to categorize sorting algorithms. The worst-case, average-case, and the best-case performance of a sorting algorithm can be used to quantify the time complexity of the process
Time Complexity
Which is the amount of memory required to execute the algorithm
Space Complexity
A sorting algorithm is said to be stable if the relative order of equal elements is preserved after sorting. This is important in certain applications where the original order of equal elements must be maintained
Stability
is one that does not require additional memory to sort the data. This is important when the available memory is limited or when the data cannot be moved.
In-Place Sorting
is one that takes advantage of pre-existing order in the data to improve performance
Adaptivity
What are the Time Complexities
O(1) Constant Time
O(log n) Logarithmic Time
O(n) Linear Time
O(n log n) Linearithmic Time
O(n^2) Quadratic Time
