Sorting
- Arranging data based on defined order
- Order is established based on comparisons
Types of Sorting Algorithms
- Iterative Sorting Algorithms
- Iterate through the data several times to sort using comparisons.
- e.g., Bubble Sort, Cocktail Shaker Sort, Insertion Sort, Selection Sort
- Divide & Conquer Sorting Algorithms
- Tear the data down into subsets and sorts the subsets using comparisons
- e.g., Merge Sort, In-place Quicksort
- Non-Comparison Sorting Algorithms
- Sort certain types data with properties can use to sort
- e.g., LSD(Least Significant Digit), Radix Sort
What are the qualities to consider when analyzing sorting algorithms?
- Time Complexity
- Stability(Stable or not stable?)
The term “Stable” in the context of sorting algorithms refers to the property of maintaining the relative order of duplicate data throughout the algorithm after sorting is applied.
- Adaptivity(Adaptive or not adaptive?)
The term “Adaptive” refers to the ability of an algorithm to improve its general performance under certain conditions. For example, the Insertion Sort, which has a time complexity of O(n^2), can have a time complexity of O(n) when dealing with a sorted array.
- Place(In-place or Out-of-place?)
The characteristic distinction between in-place and out-of-place pertains to whether the sorting operation is performed directly on the original array, or if it uses additional memory space. Examples of in-place sorting algorithms include Bubble Sort, Insertion Sort, and Quick Sort, while an example of an out-of-place sorting algorithm is Merge Sort.
Leave a comment