Cộng đồng chia sẻ tri thức Lib24.vn

Cấu trúc dữ liệu - Kỹ thuật sắp xếp

Gửi bởi: Võ Thị Hường 13 tháng 2 2020 lúc 11:13:52


Mục lục
* * * * *

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ể. Các lệnh phổ biến nhất 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ế -

  1. Danh bạ điện thoại - Danh bạ điện thoại lưu số điện thoại của những người được sắp xếp theo tên của họ, để có thể tìm kiếm tên dễ dàng.
  2. Từ điển - 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 tại chỗ

Các thuật toán sắp xếp có thể cần một số không gian bổ sung để so sánh và lưu trữ tạm thời một vài yếu tố dữ liệu. Các thuật toán này không yêu cầu bất kỳ không gian bổ sung và sắp xếp được cho là xảy ra tại chỗ, hoặc ví dụ, trong chính mảng. Điều này được gọi là sắp xếp tại chỗ . 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à sắp xếp không tại chỗ . Hợp nhất sắp xếp là một ví dụ về sắp xếp không tại chỗ.

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 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à sắp xếp ổn định .

Cấu trúc dữ liệu - Kỹ thuật sắp xếp

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à sắp xếp không ổn định .

Cấu trúc dữ liệu - Kỹ thuật sắp xếp

Tính ổn định của một thuật toán quan trọng khi chúng ta muốn duy trì chuỗi các phần tử gốc, ví dụ như trong một tuple.

Thuật toán sắp xếp thích ứng và không thích ứng

Một thuật toán sắp xếp được cho là thích ứng, nếu nó tận dụng các yếu tố đã được 'sắp xếp' trong danh sách sẽ được sắp xếp. Đó là, trong khi sắp xếp nếu danh sách nguồn đã được sắp xếp một số phần tử, 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.

Một thuật toán không thích ứng là một thuật toán không tính đến các yếu tố đã được sắp xếp. Họ cố gắng buộc mọi yếu tố đơn lẻ được sắp xếp lại để xác nhận sự 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ề kỹ thuật sắp xếp, đây là một 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à theo thứ tự tăng dần , nếu phần tử kế tiếp lớn hơn phần 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à theo thứ tự giảm dần , 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à theo thứ tự không tăng , nếu phần tử kế tiếp nhỏ hơn hoặc bằng phần tử trước đó trong chuỗi. 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 đó.

Lệnh không giảm

Một chuỗi các giá trị được cho là theo thứ tự không giảm , nếu phần tử kế tiếp lớn hơn hoặc bằng phần tử trước đó trong chuỗi. 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.


Được cập nhật: 25 tháng 3 lúc 13:20:55 | Lượt xem: 476