Mục đích

Chia một mảng ra thành hai cụm: một cụm thỏa điều kiện, và cụm còn lại.

Cài đặt

def partition(a, pred):
  head = [x for x in a if pred(x)]
  tail = [x for x in a if not pred(x)]
  return head + tail, len(head)

def partition(a, pred):
    okay_idx = 0
    for i, x in enumerate(a):
        if pred(x):
            a[okay_idx], a[i] = a[i], a[okay_idx] # swap
            okay_idx += 1
    return a, okay_idx

Độ phức tạp

Thời gian chạy

O(n)

Bộ nhớ cần thiết

O(n) nếu sử dụng mảng phụ, hoặc O(1) nếu không

Ứng dụng

Ứng dụng nổi tiếng nhất là thuật toán QuickSort do Tony Hoare sáng tạo ra. Thuật toán QuickSort sắp xếp một mảng với độ phức tạp trung bình là O(n*logn) với n là số lượng phần tử trong mảng. Độ phức tạp trong trường hợp xấu nhất có thể là O(n*n).

Sau đây là một cài đặt dễ hiểu của QuickSort. Cài đặt này chỉ dùng để thể hiện ý tưởng chứ không nên dùng trong các ứng dụng.

Ý tưởng chủ đạo là lấy ra một phần tử nào đó trong A (tức là A' chỉ còn N-1 phần tử) gọi là pivot, ngăn A' thành hai cụm (một cụm nhỏ hơn pivot, một cụm còn lại). Tiếp tục gọi đệ quy để sắp xếp hai cụm đó và nối chúng lại với nhau thông qua pivot.

def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = a[-1]
    a, pivot_idx = partition(a[ : -1], lambda x: x <= pivot)
    return quicksort(a[ : pivot_idx]) + [pivot] + quicksort(a[pivot_idx : ])

import itertools
for l in range(8):
    a = range(l)
    for p in itertools.permutations(a):
        p = list(p)
        assert quicksort(p) == a

Bài toán mở rộng

• Cho một mảng số nguyên A. Tìm K phần tử nhỏ nhất trong A.
• Cho một mảng số nguyên A và một số nguyên X. Đếm số tập hợp 2-phần-tử trong mảng A có tổng nhỏ hơn hoặc bằng X.

Các bạn có thể trao đổi về cách giải bài các bài toán mở rộng này với độ phức tạp trung bình O(n) trong diễn đàn.