카운팅,래딕스 정렬 복습하기전에 다른 정렬 특징 정리
Insertion Sort(삽입 정렬)
- Easy to code
- Fast on small inputs (less than ~50 elements)
- Fast on nearly-sorted inputs
- Worst case=O(n^2), Best case=O(n), Average case=O(n^2)[reverse-sorted case]
Merge Sort(병합 정렬)
- Divide-and-Conquer
-Split array in half
-Recursively sort subarrays
-Linear-time merge step” → It means that merging two sorted sublists of total length n takes O(n) time. - all case is O(nlogn)
- it does not sort in place -> need temporary array
Heap Sort(힙 정렬(maxheap))
- it uses the very useful heap data structure
-Complete binary tree
-Heap property: parent key > children's keys - O(nlgn) is worst case
- it sorts in place
Quick Sort(퀵 정렬(pivot))
- Divide-and-Conquer
-Partition array into two subarrays, recursively sort
-All of first subarray < all of second subarray
-No merge step needed - O(nlgn) average case, O(n^2) worst case
-worst case on sorted input
-Randomized Quick Sort chooses pivots randomly to avoid worst case
All of the sorting algorithms so far are comparison sorts
and all comparison sorts are Omega(nlgn) (lowerbound)
이는 Decision 트리로 각 레벨마다 비교 조건을 붙인다해소 최소 하한총 레벨은 lgn이다.
그래서 비교를 안하는 정렬인 Counting Sort로 시간복잡도를 더욱 줄일 수 있다.
stable,unstable sort?
A stable sort is a sorting algorithm that preserves the relative order of elements with equal keys after sorting.
Typical examples include Merge Sort, Insertion Sort, and Counting Sort (when implemented stably).
In contrast, Quick Sort, Heap Sort, and Selection Sort are unstable sorting algorithms.
Stability is important in multi-key sorting because it ensures that the order of elements with identical keys remains consistent across sorting passes.
Counting sort
Features
- No coparisions between elements
- But depends on assumption about the numbers being sorted
Basic Idea
- For each input element x, determine the number of element less than or equal to x
- For each integer i (0<=i<=k), count "how many elements whose values are i"
->Then we know how many elements are less than or equal to i
Algorithm Storage
A[1..n]= input elements
B[1..n]= sorted elements
C[0..k]= hold the number of elements less than or equal to i
Algorithm Step
1. Count phase
Create an array C[0..k], where each index represents a value.
Count how many times each value appears in the input array A.
k is max num in A[].
2. Prefix sum phase
Convert each C[i] to store the total number of elements ≤ i.
This gives the final index positions for each value.
C[i] = C[i] + C[i-1] we should sort stable
Note: After prefix sum, C[i] represents the number of elements ≤ i —
that’s why we place each element at index C[x]-1 and then decrement C[x].
3. Placement phase
Traverse A from right to left.
For each value x, decrease C[x] by 1 and place x into B[C[x]].
Processing in reverse order makes the algorithm stable.
4. Copy phase (optional)
Copy the sorted array B back to A.
sudo code
O(k)+O(n)+O(k)+O(n)=O(n+k)
Total time: O(n+k)
Usually, k=O(n).
Thus counting sort runs in O(n). but Usually.
But sorting is Omega(nlogn)
-No contradiction->not comparison sort
-In fact, there are no comparisions at all
And this Algorithm is stable
Problem:
if k is much bigger number like O(n+10^10), Total time is O(10^10).
so if k is moderately small, the Total time is O(n)
Radix Sort
Key idea
Sort the least significant digit first
sudo code
RadixSort(A, d)
for i=1 to d
StableSort(A) on digit i
Conclusion(Radix sort)
When Radix Sort uses Counting Sort for each digit, the sorting is performed based on digits ranging from 0 to 9.
Therefore, in the time complexity O(n + k) of Counting Sort, k = 10, which is a constant.
As a result, the overall complexity becomes O(n) for each digit position.
In Radix Sort, Counting Sort runs in O(d(n + 10)) = O(n) per digit since digits range from 0–9.
Time Complexity Summary
| Algorithm | Best | Average | Worst | Stable? | In-place? |
|---|---|---|---|---|---|
| Insertion | O(n) | O(n²) | O(n²) | Yes | Yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | Yes | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | No | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | No | Yes |
| Counting | O(n + k) | O(n + k) | O(n + k) | Yes | No |
| Radix | O(d·n) | O(d·n) | O(d·n) | Yes | No |
