การเรียงแบบเร็วและการเลือกหมุด

การเรียงลำดับแบบเร็ว: การแบ่งแล้วพิชิตภายในพื้นที่เดิม

def quick_sort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        pivot_idx = partition(arr, lo, hi)
        quick_sort(arr, lo, pivot_idx - 1)  # sort left
        quick_sort(arr, pivot_idx + 1, hi)  # sort right

def partition(arr, lo, hi):
    pivot = arr[hi]  # Lomuto: choose last element as pivot
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    return i + 1

arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr)  # [1, 1, 2, 3, 6, 8, 10]

รูปแบบการแบ่งส่วนของโลมูโต

def lomuto_partition_traced(arr, lo, hi):
    pivot = arr[hi]
    i = lo - 1
    print(f'Pivot: {pivot}, array: {arr[lo:hi+1]}')
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    print(f'After partition: {arr[lo:hi+1]}')
    return i + 1

arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)

รูปแบบการแบ่งส่วนของฮอร์

def hoare_partition(arr, lo, hi):
    pivot = arr[lo]  # first element as pivot
    i, j = lo - 1, hi + 1
    while True:
        i += 1
        while arr[i] < pivot: i += 1
        j -= 1
        while arr[j] > pivot: j -= 1
        if i >= j: return j
        arr[i], arr[j] = arr[j], arr[i]

def quick_sort_hoare(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        p = hoare_partition(arr, lo, hi)
        quick_sort_hoare(arr, lo, p)      # note: p not p-1
        quick_sort_hoare(arr, p+1, hi)

arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_hoare(arr)
print(arr)  # [1, 1, 2, 3, 6, 8, 10]

กรณีแย่ที่สุด O(n²): อินพุตที่เรียงลำดับอยู่แล้ว

import sys
sys.setrecursionlimit(5000)

def quick_sort_naive(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    comparisons = [0]
    def _qs(lo, hi):
        if lo >= hi: return
        pivot = arr[hi]  # last element pivot
        i = lo - 1
        for j in range(lo, hi):
            comparisons[0] += 1
            if arr[j] <= pivot:
                i += 1; arr[i], arr[j] = arr[j], arr[i]
        arr[i+1], arr[hi] = arr[hi], arr[i+1]
        p = i + 1
        _qs(lo, p-1); _qs(p+1, hi)
    _qs(lo, hi)
    return comparisons[0]

import math
n = 100
sorted_arr = list(range(n))
ops = quick_sort_naive(sorted_arr)
print(f'n={n}, ops={ops}, n^2={n**2}')  # ops close to n*(n-1)/2

จุดหมุนแบบสุ่ม: คาดว่าจะใช้เวลา O(n log n)

import random

def quick_sort_random(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        # Randomise pivot
        rand_i = random.randint(lo, hi)
        arr[rand_i], arr[hi] = arr[hi], arr[rand_i]
        # Lomuto partition with last element as pivot
        pivot = arr[hi]
        i = lo - 1
        for j in range(lo, hi):
            if arr[j] <= pivot:
                i += 1; arr[i], arr[j] = arr[j], arr[i]
        arr[i+1], arr[hi] = arr[hi], arr[i+1]
        p = i + 1
        quick_sort_random(arr, lo, p - 1)
        quick_sort_random(arr, p + 1, hi)

arr = list(range(100, 0, -1))  # worst case for naive
quick_sort_random(arr)
print(arr[:10])  # [1,2,3,4,5,6,7,8,9,10]

จุดหมุนค่ามัธยฐานของสามค่า

def median_of_three(arr, lo, hi):
    mid = (lo + hi) // 2
    # Sort lo, mid, hi values in place
    if arr[lo] > arr[mid]:  arr[lo], arr[mid] = arr[mid], arr[lo]
    if arr[lo] > arr[hi]:   arr[lo], arr[hi]  = arr[hi],  arr[lo]
    if arr[mid] > arr[hi]:  arr[mid], arr[hi] = arr[hi],  arr[mid]
    # Median is now at arr[mid]; swap to arr[hi-1] as pivot
    arr[mid], arr[hi] = arr[hi], arr[mid]
    return arr[hi]  # pivot value

arr = [3, 9, 1]
print(median_of_three(arr, 0, 2), arr)  # 3, [1,3,9] (sorted)

ธงชาติเนเธอร์แลนด์: การแบ่งส่วนสามทาง

def three_way_partition(arr, lo, hi):
    pivot = arr[lo]
    lt = lo      # arr[lo..lt-1] < pivot
    gt = hi      # arr[gt+1..hi] > pivot
    i = lo       # current
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1; i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1  # don't advance i
        else:
            i += 1
    return lt, gt  # pivot occupies arr[lt..gt]

arr = [3, 1, 4, 1, 5, 9, 2, 6, 3, 3]
lt, gt = three_way_partition(arr, 0, len(arr)-1)
print(arr, '| pivot region:', lt, 'to', gt)

Quickselect: ค่าที่น้อยที่สุดลำดับที่ k ใน O(n)

import random

def quickselect(nums, k):
    '''Find kth smallest (0-indexed) in O(n) average.'''
    def _select(lo, hi):
        if lo == hi: return nums[lo]
        rand_i = random.randint(lo, hi)
        nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
        pivot = nums[hi]
        i = lo - 1
        for j in range(lo, hi):
            if nums[j] <= pivot:
                i += 1; nums[i], nums[j] = nums[j], nums[i]
        p = i + 1
        nums[p], nums[hi] = nums[hi], nums[p]
        if p == k:    return nums[p]
        elif k < p:   return _select(lo, p - 1)
        else:         return _select(p + 1, hi)
    return _select(0, len(nums) - 1)

print(quickselect([3,2,1,5,6,4], 1))  # 2  (2nd smallest)

ความซับซ้อนด้านพื้นที่ของการเรียงลำดับแบบเร็ว

def quick_sort_optimised(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    while lo < hi:
        p = lomuto_partition_qs(arr, lo, hi)
        # Recurse on smaller partition; iterate on larger
        if p - lo < hi - p:
            quick_sort_optimised(arr, lo, p - 1)
            lo = p + 1  # tail-call elimination
        else:
            quick_sort_optimised(arr, p + 1, hi)
            hi = p - 1

def lomuto_partition_qs(arr, lo, hi):
    pivot = arr[hi]; i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot: i += 1; arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    return i + 1

การเปรียบเทียบอัลกอริทึมการเรียงลำดับ

# Python's sorted() uses Timsort:
# - Hybrid: merge sort for large runs, insertion sort for small (< 64 elements)
# - Stable, O(n log n) worst case
# - O(n) best case for sorted/reverse-sorted/nearly-sorted
# - O(n) extra space

import random
arr = random.sample(range(10000), 1000)
sorted_arr = sorted(arr)  # Timsort
print(sorted_arr[:5], '...')  # first 5 elements

Introsort: การผสานทั้งสามวิธี

# Introsort hybrid (simplified)
def introsort(arr, depth_limit=None):
    if depth_limit is None:
        import math
        depth_limit = 2 * int(math.log2(len(arr) + 1)) if arr else 0
    if len(arr) <= 16:
        # insertion sort for small arrays
        for i in range(1, len(arr)):
            key = arr[i]; j = i - 1
            while j >= 0 and arr[j] > key:
                arr[j+1] = arr[j]; j -= 1
            arr[j+1] = key
        return arr
    if depth_limit == 0:
        arr.sort()  # fall back to heapsort equivalent
        return arr
    # Otherwise quick sort
    pivot = arr[-1]
    small = [x for x in arr[:-1] if x <= pivot]
    large = [x for x in arr[:-1] if x > pivot]
    return introsort(small, depth_limit-1) + [pivot] + introsort(large, depth_limit-1)

print(introsort([5,3,8,1,9,2,7]))

แบบทดสอบสั้น ๆ

ทบทวนบทเรียน