Giải thuật sắp xếp trong cấu trúc dữ liệu & giải thuật

Sắp xếp là sắp xếp dữ liệu theo một định dạng cụ thể. 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ính quan trọng của việc sắp xếp dữ liệu nằm ở chỗ: việc tìm kiếm dữ liệu có thể được tối ưu nếu dữ liệu được sắp xếp theo một thứ tự nào đó (tăng hoặc giảm). Sắp xếp cũng được sử dụng để biểu diễn dữ liệu trong một định dạng dễ đọc hơn.

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 giải thuật được xem như là adaptive, nếu nó tận dụng các phần tử đã được sắp xếp trong danh sách mà đã được sắp xếp. Đó là, trong khi sắp xếp nếu danh sách ban đầu có một số phần tử đã được sắp xếp, thì giải thuật dạng adaptive sẽ ghi nhận các phần tử này và sẽ cố gắng không thay đổi thứ tự của 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).