Selection Sort:
- Repeatedly finds the minimum (or maximum) element from the unsorted portion of the array.
- Swaps it with the first unsorted element.
- Simple but inefficient for large datasets: O(n2) time complexity.
Insertion Sort:
- Builds the sorted portion of the array incrementally.
- For each element, it is inserted into its correct position in the sorted portion by shifting elements.
- Efficient for small or nearly sorted datasets: O(n2) time complexity.
Bubble Sort:
- Repeatedly compares adjacent elements and swaps them if they are in the wrong order.
- Largest elements “bubble” to the end of the array.
- Inefficient for large datasets: O(n2) time complexity.
Merge Sort:
- Divides the array into halves recursively until each subarray contains one element.
- Merges subarrays in sorted order.
- Efficient and stable: O(nlogn) time complexity.
Shell Sort:
- A generalization of insertion sort.
- Sorts elements far apart first, using a gap sequence.
- Gaps reduce over iterations until it becomes regular insertion sort.
- Average time complexity depends on gap sequence, typically O(n1.25) to O(n1.5).
Quick Sort:
- Picks a “pivot” element, partitions the array into elements less than and greater than the pivot.
- Recursively applies this process to subarrays.
- Highly efficient: O(nlogn) on average, but O(n2) in the worst case (e.g., with poor pivot choice).