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).
Theo Tutorialspoint
Bài trước: Cấu trúc dữ liệu Hash Table
Bài tiếp: Giải thuật sắp xếp nổi bọt (Bubble Sort)
Bạn nên đọc
Theo Nghị định 147/2024/ND-CP, bạn cần xác thực tài khoản trước khi sử dụng tính năng này. Chúng tôi sẽ gửi mã xác thực qua SMS hoặc Zalo tới số điện thoại mà bạn nhập dưới đây:

- Code NgầuThích · Phản hồi · 3 · 17/08/20

Cũ vẫn chất
-
Remote Desktop Connection: Cách thiết lập chi tiết, 100% truy cập máy tính qua Internet thành công
Hôm qua 2 -
Cách bật báo biến động số dư trên Techcombank Mobile qua loa
Hôm qua -
Tổng hợp câu hỏi khó về tình yêu của con gái và bí kíp trả lời hoàn hảo cho các chàng
Hôm qua -
Những cách đơn giản để bắt chuyện với bất kỳ ai
Hôm qua -
Cách đổi số tiền thành chữ trong Excel, không cần add-in, hỗ trợ cả Excel 32-bit và 64-bit
Hôm qua 1 -
Cách tặng trang phục cho bạn bè trong Liên Quân
Hôm qua -
'Hack' tựa game khủng long của Google Chrome để chú T-Rex của bạn trở nên bất tử và max speed
Hôm qua 57 -
Cách tạo đường viền bảng trong Word
Hôm qua -
Hướng dẫn toàn tập chỉnh sửa ảnh trong GIMP
Hôm qua -
Những dòng stt cô gái mạnh mẽ hay nhất
Hôm qua