Lecture 331:- Criteria used for Analysing Sorts

When analyzing sorting algorithms, several criteria are used to evaluate their performance and efficiency. Some of the key criteria are:

1. Time Complexity: It measures how the running time of the algorithm increases with the size of the input data. Time complexity is expressed using Big O notation and provides an upper bound on the growth rate of the algorithm as the input size approaches infinity.
2. Space Complexity: It measures how much additional memory or space is required by the algorithm. Space complexity is also expressed using Big O notation.
3. Stability: A sorting algorithm is stable if it preserves the relative order of equal elements in the input array. For example, if there are two elements with the same key, a stable sorting algorithm will ensure that their original order is preserved in the sorted output.
4. Comparison vs. Non-comparison: Sorting algorithms can be categorized as comparison-based or non-comparison-based. Comparison-based algorithms make decisions based on the comparison of elements, while non-comparison-based algorithms use other techniques like counting or hashing.
5. Adaptive: An adaptive sorting algorithm is efficient for partially sorted or nearly sorted arrays. It takes advantage of the existing order to reduce the number of comparisons or swaps.
6. In-place: An in-place sorting algorithm uses a constant amount of extra memory for swapping elements during the sorting process. It does not require additional memory proportional to the input size.
7. Best, Average, and Worst-case Time Complexity: Sorting algorithms can have different time complexities based on the input data. Best-case time complexity refers to the scenario when the input is already sorted, average-case time complexity refers to the expected performance on random input, and worst-case time complexity is the maximum time taken for any input data.
8. Stability: A sorting algorithm is stable if it maintains the relative order of equal elements after sorting. For example, if there are two elements with the same key, a stable sorting algorithm will ensure that their original order is preserved in the sorted output.
9. Randomness: Some sorting algorithms behave differently on different types of data. For example, some algorithms may perform well on almost sorted data but poorly on highly unsorted data.
10. Comparison Count and Swaps: The number of comparisons and swaps made by the algorithm is also considered to evaluate its efficiency.

It's essential to consider these criteria to choose the appropriate sorting algorithm for specific use cases and data types. The best sorting algorithm depends on the nature and size of the data to be sorted and the specific requirements of the application.