Sắp xếp và tìm kiếm

Thuật toán sắp xếp (tiếng Anh: Sorting math) là một thuật toán có thể sắp xếp một chuỗi dữ liệu theo một thứ tự cụ thể.

Tính ổn định của thuật toán sắp xếp

Tính ổn định : Thuật toán sắp xếp ổn định sẽ duy trì thứ tự tương đối của các bản ghi mà ban đầu có cùng giá trị khóa. Tức là, nếu một thuật toán sắp xếp ổn định, khi có hai bản ghi R và S có giá trị khóa bằng nhau và R xuất hiện trước S trong danh sách ban đầu, thì R cũng sẽ đứng trước S trong danh sách đã sắp xếp.

Khi các phần tử bằng nhau không thể phân biệt được, chẳng hạn như số nguyên, thì tính ổn định không phải là vấn đề. Tuy nhiên, giả sử các cặp số sau sẽ được sắp xếp theo số đầu tiên của chúng.

(4, 1)  (3, 1)  (3, 7)（5, 6）

Trong tình huống này, có thể tạo ra hai kết quả khác nhau, một là duy trì thứ tự tương đối của các bản ghi có cùng giá trị khóa, trong khi kết quả kia thì không:

(3, 1)  (3, 7)  (4, 1)  (5, 6)  
(3, 7)  (3, 1)  (4, 1)  (5, 6)  

Các thuật toán sắp xếp không ổn định có thể thay đổi thứ tự tương đối của các bản ghi trong các giá trị khóa bằng nhau, nhưng các thuật toán sắp xếp ổn định không bao giờ làm. Các thuật toán sắp xếp không ổn định có thể được triển khai cụ thể là ổn định. Một cách để làm điều này là mở rộng so sánh các giá trị khóa theo cách thủ công, để so sánh giữa hai đối tượng có cùng giá trị khóa, (ví dụ: thêm tiêu chí thứ hai vào so sánh ở trên: kích thước của giá trị khóa thứ hai) Nó sẽ được quyết định sử dụng các mục trong chuỗi dữ liệu ban đầu như một kết quả cuối cùng. Tuy nhiên, hãy nhớ rằng thứ tự này thường liên quan đến gánh nặng không gian bổ sung.