Junior
What sorting algorithms do you know?
sobes.tech AI
Answer from AI
- Selection Sort: Finds the minimum element from the unsorted part of the array and places it at the beginning.
- Insertion Sort: Gradually builds a sorted array by inserting each element from the unsorted part into its correct position.
- Bubble Sort: Repeatedly traverses the array, comparing adjacent elements and swapping them if they are in the wrong order.
- Merge Sort: Recursively divides the array into two halves, sorts each half, and then merges the sorted halves.
- Quick Sort: Selects a pivot element and partitions the other elements into two subarrays: those less than the pivot and those greater. Then recursively sorts these subarrays.
- Heap Sort: Uses a heap data structure. Builds a max heap from the array, then repeatedly extracts the maximum element and places it at the end of the sorted part.
- Shell Sort: An improvement over insertion sort. Sorts elements separated by a certain interval, then reduces the interval and repeats.
- Counting Sort: Used for sorting integer data within a specific range. Counts the occurrences of each element and uses this information to build the sorted array.
- Radix Sort: Sorts numbers by processing their digits (ones, tens, hundreds, etc.) using an auxiliary sorting algorithm (e.g., counting sort).
Some characteristics of certain sorts:
| Sorting Algorithm | Average Complexity | Worst-case Complexity | Space Complexity | Stable | In-place |
|---|---|---|---|---|---|
| Selection | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion | O(n²) | O(n²) | O(1) | Yes | Yes |
| Bubble | O(n²) | O(n²) | O(1) | Yes | Yes |
| Merge | O(n log n) | O(n log n) | O(n) | Yes | No |
| Quick | O(n log n) | O(n²) | O(log n) (recursion) | No | Yes (depends on implementation) |
| Heap | O(n log n) | O(n log n) | O(1) | No | Yes |
| Shell | Depends on steps | Depends on steps | O(1) | No | Yes |
| Counting | O(n + k) | O(n + k) | O(k) | Yes | No |
| Radix | O(nk) | O(nk) | O(n + k) | Yes | No |
where n is the size of the array, k is the range of values (for Counting Sort), or the number of digits (for Radix Sort).