Kỹ thuật sắp xếp
Sắp xếp là sắp xếp dữ liệu theo một định dạng cụ thể như theo thứ tự anphabet tăng/giảm dần, theo thứ tự số tăng/giảm dần. Trong khoa học máy tính, giải thuật sắp xếp xác định cách để sắp xếp dữ liệu theo một thứ tự nào đó. Sắp xếp theo thứ tự ở đây là sắp xếp theo thứ tự dạng số hoặc thứ tự dạng chữ cái như trong 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ế -
- 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.
- 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.
Giải thuật sắp xếp In-place và Not-in-place
Các giải thuật sắp xếp có thể cần thêm một số bộ nhớ phụ để so sánh và bộ nhớ tạm để lưu giữ một số phần tử dữ liệu.
Những giải thuật mà không yêu cầu thêm bất kỳ bộ nhớ phụ và việc sắp xếp được tiến hành trong chính phần bộ nhớ đã khai báo trước đó (ví dụ trong một mảng chẳng hạn) thì được gọi là in-place sorting. Ví dụ cho loại giải thuật sắp xếp này là giải thuật sắp xếp nổi bọt (bubble sorting).
Nhưng trong một số giải thuật sắp xếp, chương trình cần thêm lượng bộ nhớ mà có thể lớn hơn hoặc bằng với số phần tử đang được sắp xếp. Các giải thuật này được gọi là not-in-place sorting. Ví dụ cho loại giải thuật này là sắp xếp trộn (merge sort).
Giải thuật sắp xếp cố định và sắp xếp so sánh
Một giải thuật sắp xếp được gọi là sắp xếp cố định nếu sau khi tiến hành sắp xếp thì vị trí tương đối giữa các phần tử bằng nhau không bị thay đổi.
Một giải thuật được gọi là sắp xếp so sánh nếu trong quá trình thực hiện giải thuật chúng ta tiến hành so sánh các khóa và đổi chỗ các phần tử cho nhau. Tức là khi đó vị trí tương đối của các phần tử bằng nhau bị thay đổi.
Giải thuật sắp xếp Adaptive và Non-Adaptive
Một thuật toán sắp xếp được cho là Adaptive, 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 Adaptive sẽ tính đến điều này và sẽ cố gắng không sắp xếp lại chúng.
Trái ngược với loại giải thuật trên, giải thuật dạng non-adaptive sẽ không ghi nhận các phần tử đã được sắp xếp trước đó. Giải thuật loại này sẽ vấn cố gắng sắp xếp lại từng phần tử trong danh sách ban đầu.
Các khái niệm quan trọng trong giải thuật sắp xếp
Dưới đây là phần giới thiệu ngắn gọn cho một số khái niệm xuất hiện trong khi thảo luận về các giải thuật sắp xếp:
Thứ tự tăng
Một dãy giá trị được xem như trong thứ tự tăng dần nếu phần tử đứng sau lớn hơn phần tử đứng trước. Ví dụ: 1, 3, 5, 6, 9.
Thứ tự giảm
Một dãy giá trị được xem như trong thứ tự giảm dần nếu phần tử đứng sau nhỏ hơn phần tử đứng trước. Ví dụ: 9, 6, 5, 3, 1.
Thứ tự không tăng
Một dãy giá trị được xem như trong thứ tự không tăng nếu phần tử đứng sau nhỏ hơn hoặc bằng phần tử đứng trước. Ví dụ: 9, 6, 5, 5, 1. Loại thứ tự này xuất hiện khi trong một dãy có chứa các giá trị giống nhau (trong ví dụ là 5).
Thứ tự không giảm
Một dãy giá trị được xem như trong thứ tự không giảm nếu phần tử đứng sau lớn hơn hoặc bằng phần tử đứng trước. Ví dụ: 1, 5, 5, 6, 9. Loại thứ tự này xuất hiện khi trong một dãy có chứa các giá trị giống nhau (trong ví dụ là 5).
- Hiếu Kiều -
Bài viết nổi bật
Bài viết nổi bật