Cấu trúc dữ liệu - Kỹ thuật sắp xếp
Sắp xếp đề cập đến việc sắp xếp dữ liệu theo một định dạng cụ thể. Thuật toán sắp xếp chỉ định cách sắp xếp dữ liệu theo một thứ tự cụ thể. Hầu hết các đơn đặt hàng phổ biến là theo thứ tự số hoặc từ điển.
Tầm quan trọng của việc sắp xếp nằm ở chỗ, việc tìm kiếm dữ liệu có thể được tối ưu hóa ở mức rất cao, nếu dữ liệu được lưu trữ theo cách được sắp xếp. Sắp xếp cũng được sử dụng để thể hiện dữ liệu ở các định dạng dễ đọc hơn. Sau đây là một số ví dụ về sắp xếp trong các tình huống thực tế -
Telephone Directory - Danh bạ lưu trữ số điện thoại của những người được sắp xếp theo tên của họ, để có thể tra cứu tên dễ dàng.
Dictionary - Từ điển lưu trữ các từ theo thứ tự bảng chữ cái để việc tìm kiếm bất kỳ từ nào trở nên dễ dàng.
Sắp xếp tại chỗ và Sắp xếp không tại chỗ
Các thuật toán sắp xếp có thể yêu cầu thêm một số không gian để so sánh và lưu trữ tạm thời một số phần tử dữ liệu. Các thuật toán này không yêu cầu thêm bất kỳ khoảng trống nào và việc sắp xếp được cho là diễn ra tại chỗ, hoặc ví dụ, trong chính mảng. Đây được gọi làin-place sorting. Sắp xếp bong bóng là một ví dụ về sắp xếp tại chỗ.
Tuy nhiên, trong một số thuật toán sắp xếp, chương trình yêu cầu không gian lớn hơn hoặc bằng các phần tử được sắp xếp. Sắp xếp sử dụng không gian bằng hoặc nhiều hơn được gọi lànot-in-place sorting. Merge-sort là một ví dụ về sắp xếp không đúng vị trí.
Sắp xếp ổn định và không ổn định
Nếu một thuật toán sắp xếp, sau khi sắp xếp các nội dung, không thay đổi chuỗi nội dung tương tự mà chúng xuất hiện, nó được gọi là stable sorting.
Nếu một thuật toán sắp xếp, sau khi sắp xếp nội dung, thay đổi chuỗi nội dung tương tự mà chúng xuất hiện, nó được gọi là unstable sorting.
Tính ổn định của một thuật toán rất quan trọng khi chúng ta muốn duy trì chuỗi các phần tử ban đầu, chẳng hạn như trong một bộ tuple.
Thuật toán sắp xếp thích ứng và không thích ứng
Thuật toán sắp xếp được cho là thích ứng, nếu nó tận dụng các phần tử đã được 'sắp xếp' trong danh sách được sắp xếp. Nghĩa là, trong khi sắp xếp nếu danh sách nguồn có một số phần tử đã được sắp xếp, các thuật toán thích ứng sẽ tính đến điều này và sẽ cố gắng không sắp xếp lại chúng.
Thuật toán không thích ứng là thuật toán không tính đến các phần tử đã được sắp xếp. Họ cố gắng buộc từng phần tử được sắp xếp lại để xác nhận tính sắp xếp của chúng.
Điều khoản quan trọng
Một số thuật ngữ thường được đặt ra trong khi thảo luận về các kỹ thuật sắp xếp, đây là phần giới thiệu ngắn gọn về chúng -
Tăng cao sự đặt hàng
Một chuỗi các giá trị được cho là trong increasing order, nếu phần tử kế tiếp lớn hơn phần tử trước đó. Ví dụ: 1, 3, 4, 6, 8, 9 theo thứ tự tăng dần, vì mọi phần tử tiếp theo đều lớn hơn phần tử trước.
Lệnh giảm
Một chuỗi các giá trị được cho là trong decreasing order, nếu phần tử kế tiếp nhỏ hơn phần tử hiện tại. Ví dụ: 9, 8, 6, 4, 3, 1 theo thứ tự giảm dần, vì mọi phần tử tiếp theo đều nhỏ hơn phần tử trước.
Đơn hàng không tăng
Một chuỗi các giá trị được cho là trong non-increasing order, nếu phần tử kế tiếp nhỏ hơn hoặc bằng phần tử trước đó của nó trong dãy. Thứ tự này xảy ra khi chuỗi chứa các giá trị trùng lặp. Ví dụ: 9, 8, 6, 3, 3, 1 theo thứ tự không tăng, vì mọi phần tử tiếp theo đều nhỏ hơn hoặc bằng (trong trường hợp 3) nhưng không lớn hơn bất kỳ phần tử nào trước đó.
Thứ tự không giảm
Một chuỗi các giá trị được cho là trong non-decreasing order, nếu phần tử kế tiếp lớn hơn hoặc bằng phần tử trước đó của nó trong dãy. Thứ tự này xảy ra khi chuỗi chứa các giá trị trùng lặp. Ví dụ: 1, 3, 3, 6, 8, 9 theo thứ tự không giảm, vì mọi phần tử tiếp theo đều lớn hơn hoặc bằng (trong trường hợp 3) nhưng không nhỏ hơn phần tử trước.