Guida a Ordinamento · 4/6
Per ora questo capitolo è disponibile solo in inglese.
Time complexity alone does not pick a sorting algorithm. You also need the gap between best, average and worst case, extra memory, stability, and sensitivity to input patterns. This chapter tabulates the main sorts, shows why comparison sorting cannot beat n log n, and explains how counting and radix sort sidestep that bound.
| Algorithm | Best | Average | Worst | Extra memory | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble sort (early exit) | O(n) | O(n²) | O(n²) | O(1) | yes | yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | no | yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | yes | yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | yes | no |
| Quicksort (random pivot) | O(n log n) | O(n log n) | O(n²) | O(log n) stack | no | yes |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | no | yes |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | yes | no |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | no | yes |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | yes | no |
| Radix sort | O(d(n + b)) | O(d(n + b)) | O(d(n + b)) | O(n + b) | yes | no |
Here k is the value range, d the number of digits and b the base (values per digit). Quicksort's O(log n) stack holds only when the implementation recurses on the smaller side; naive recursion on both sides can go O(n) deep.
Merge sort follows the recurrence T(n) = 2T(n/2) + O(n). Halving gives log n levels, each level merges elements in total, so the cost is . The split ignores the data, so best and worst case are the same.
nO(n log n)Quicksort depends on how evenly the pivot splits the array. Even splits give O(n log n); if one side is always empty, the cost is n + (n - 1) + ... + 1 = O(n²). With a random pivot the expected number of comparisons is about 1.39 n log₂ n, a bit more than merge sort, but quicksort scans contiguous memory in place and is usually faster in practice. You can measure how badly a naive "first element as pivot" quicksort does on sorted input:
import random
def quicksort_count(a, choose):
comparisons = 0
stack = [(0, len(a) - 1)]
while stack:
lo, hi = stack.pop()
if lo >= hi:
continue
p = choose(lo, hi)
a[p], a[hi] = a[hi], a[p]
pivot, i = a[hi], lo
for j in range(lo, hi):
comparisons += 1
if a[j] < pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
stack += [(lo, i - 1), (i + 1, hi)]
return comparisons
n = 2000
print(quicksort_count(list(range(n)), lambda lo, hi: lo)) # 1999000 = n(n-1)/2
print(quicksort_count(list(range(n)), lambda lo, hi: random.randint(lo, hi))) # roughly 25000A comparison sort learns the order only through yes/no questions of the form "is a < b?". Drawing every possible sequence of questions gives a decision tree whose leaves correspond to permutations of the input. There are n! orderings of n distinct elements, so the tree needs at least n! leaves, and a binary tree of height h has at most 2^h leaves. Hence 2^h ≥ n!, so h ≥ log₂(n!). Since n! is at least (n/2)^(n/2), we get log₂(n!) ≥ (n/2) log₂(n/2), and the worst-case number of comparisons is Ω(n log n).
This means merge sort and heapsort are asymptotically optimal. It also means that dropping the "comparisons only" assumption can buy speed.
import math
for n in [10, 100, 1000]:
lower = math.ceil(math.log2(math.factorial(n)))
print(n, lower, round(n * math.log2(n)))
# 10 22 33
# 100 525 664
# 1000 8530 9966Counting sort runs in O(n + k) when the value range k is comparable to n or smaller. Ages, scores from 0 to 100 and byte values are good fits; when k is huge, time and memory follow k.
Radix sort splits w-bit integers into r-bit digits and runs d = w / r stable counting passes. For 32-bit integers with 8-bit digits, d = 4 and b = 256, so the cost is 4(n + 256), effectively linear. Fixed-length strings can be sorted the same way.
def radix_sort(a, bits=32, r=8):
mask = (1 << r) - 1
for shift in range(0, bits, r):
buckets = [[] for _ in range(1 << r)]
for x in a: # appended in order, so each pass is stable
buckets[(x >> shift) & mask].append(x)
a = [x for bucket in buckets for x in bucket]
return a
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]This version handles non-negative integers only; negatives need the sign bit flipped or a separate pass.
O(n log n) in the worst case; quicksort is fast on average but needs a good pivot strategy to avoid O(n²).Ω(n log n).
0 commenti
Accedi · Accedi per lasciare un commento.