Thuật toán sắp xếp

Sorting Strings Across Languages

ASCII sorting is simple: compare byte values. But for multilingual text, byte-order sorting produces absurd results: "ä" sorts after "z" in ASCII, "纳" appears nowhere near "那" despite being phonetically similar, and "naïve" sorts far from "naive". The Unicode Collation Algorithm (UCA), specified in Unicode Technical Standard #10, provides a framework for language-aware sorting.

Multi-Level Comparison Keys

The UCA uses up to four comparison levels, applied in order. If two strings are equal at level 1, level 2 is consulted, and so on:

This means a case-insensitive, accent-insensitive search operates at level 1: "naïve" equals "naive" equals "NAIVE". A case-insensitive but accent-sensitive sort uses levels 1–2: "naive" < "naïve" because they differ at level 2.

import locale

# On Linux/macOS with proper locale support
locale.setlocale(locale.LC_ALL, "en_US.UTF-8")
words = ["naive", "naïve", "NAIVE", "résumé", "resume"]
words.sort(key=locale.strxfrm)
print(words)  # locale-aware sort

# For robust multilingual sorting, use the PyICU library
# pip install pyicu
from icu import Collator, Locale
collator = Collator.createInstance(Locale("en_US"))
words.sort(key=collator.getSortKey)

CLDR Tailorings

The UCA defines a default collation order (DUCET — Default Unicode Collation Element Table), but different locales require different sort orders. The Unicode Common Locale Data Repository (CLDR) provides tailorings that modify the UCA for specific languages:

• In Swedish, v and w are treated as equivalent at the primary level (both sort before x)
• In Spanish (traditional), ch sorts as a unit after all c words
• In German (phone book order), ä = ae, so "Ärger" sorts with "Ärger" near "Aero"
• In Japanese, hiragana and katakana may be treated as equivalent at level 1

Without CLDR tailorings, sorting Swedish or German text with the default UCA produces results that feel wrong to native speakers.

Practical Python Sorting

# Simple locale-aware sort (depends on OS locale support)
import locale
locale.setlocale(locale.LC_COLLATE, "de_DE.UTF-8")
german_words = ["Äpfel", "Apfel", "Zorn", "außen"]
german_words.sort(key=locale.strxfrm)

# Check if a string needs normalization before collation
import unicodedata
def collation_key(s: str) -> str:
    return locale.strxfrm(unicodedata.normalize("NFC", s))

Quick Facts