# Thứ tự từ điển

Trên các kiểu dữ liệu đơn giản chuẩn, người ta thường nói tới khái niệm thứ tự. Ví dụ trên kiểu Integer thì có quan hệ: 1 < 2; 2 < 3; 3 < 10;..., trên kiểu ký tự Char thì cũng có quan hệ 'A' < 'B'; 'C' < 'c'...

Xét quan hệ thứ tự toàn phần nhỏ hơn hoặc bằng ký hiệu trên một tập hợp , là quan hệ hai ngôi thoả mãn bốn tính chất:

Với ∀a, b, c ∈ S
Tính phổ biến: Hoặc là a ≤ b, hoặc b ≤ a;
Tính phản xạ: a ≤ a
Tính phản đối xứng: Nếu a ≤ b và b ≤ a thì bắt buộc a = b.
Tính bắc cầu: Nếu có a ≤ b và b ≤ c thì a ≤ c.

Trong trường hợp và , ta dùng ký hiệu cho gọn, (ta ngầm hiểu các ký hiệu như , , khỏi phải định nghĩa)

Ví dụ như quan hệ trên các số nguyên cũng như trên các kiểu vô hướng, liệt kê là quan hệ thứ tự toàn phần.

Trên các dãy hữu hạn, người ta cũng xác định một quan hệ thứ tự:

Xét và là hai dãy độ dài , trên các phần tử của và đã có quan hệ thứ tự .

Khi đó nếu như

• Hoặc với .

• Hoặc tồn tại một số nguyên dương để:

Trong trường hợp này, ta có thể viết .

Thứ tự đó gọi là thứ tự từ điển trên các dãy độ dài .

Khi độ dài hai dãy và không bằng nhau, người ta cũng xác định được thứ tự từ điển. Bằng cách thêm vào cuối dãy hoặc dãy những phần tử đặc biệt gọi là phần tử để độ dài của a và b bằng nhau, và coi những phần tử này nhỏ hơn tất cả các phần tử khác, ta lại đưa về xác định thứ tự từ điển của hai dãy cùng độ dài.

Ví dụ:

(1, 2, 3, 4) < (5, 6)
(a, b, c) < (a, b, c, d)
'calculator' < 'computer'