Buzz
Trong lĩnh vực khoa học máy tính và toán học, thuật toán sắp xếp là phương pháp để sắp xếp các phần tử trong một danh sách (hoặc một mảng) theo thứ tự (tăng dần hoặc giảm dần). Thông thường, thuật toán này được áp dụng khi các phần tử cần sắp xếp là các số. Các nhà nghiên cứu đã quan tâm rất nhiều đến bài toán sắp xếp này.
Phân loại thuật toán sắp xếp.
Sắp xếp ổn định
Một thuật toán sắp xếp được gọi là sắp xếp ổn định nếu sau khi sắp xếp, vị trí tương đối giữa các phần tử bằng nhau không bị thay đổi.
Sắp xếp bằng so sánh
Một thuật toán sắp xếp được gọi là sắp xếp so sánh khi trong quá trình thực hiện thuật toán ta so sánh các khóa và đổi chỗ các phần tử cho nhau. Hầu hết các thuật toán sắp xếp sau đây đều là sắp xếp so sánh, riêng sắp xếp đếm phân phối không thuộc loại này.
Những thuật toán sắp xếp khác
Sắp xếp nổi lên
Sắp xếp nổi lên (bubble sort) là một phương pháp sắp xếp đơn giản, dễ hiểu thường được giảng dạy trong lĩnh vực khoa học máy tính. Giải thuật bắt đầu từ đầu của tập dữ liệu. Nó so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ cho nhau. Tiếp tục làm như vậy với cặp phần tử tiếp theo cho đến khi hết tập hợp dữ liệu. Sau đó, nó quay lại với hai phần tử đầu cho đến khi không còn cần phải đổi chỗ nữa.
Sắp xếp chèn
Sắp xếp chèn (insertion sort) là thuật toán sắp xếp bằng cách chèn phần tử đang xét vào vị trí thích hợp trong dãy số đã sắp xếp phía trước để duy trì tính sắp xếp của dãy số.
Sắp xếp lựa chọn
Sắp xếp lựa chọn (selection sort) là phương pháp sắp xếp bằng cách chọn phần tử nhỏ nhất và đặt vào vị trí đầu tiên, sau đó tiếp tục với các phần tử nhỏ thứ hai, thứ ba,...
Sắp xếp trộn
Sắp xếp trộn (sắp xếp merge) cùng sắp xếp nhanh là hai thuật toán sắp xếp dựa trên phương pháp 'chia để trị' (chia và chinh phân). Quá trình cơ bản là trộn hai danh sách đã sắp xếp thành một danh sách mới theo thứ tự. Có thể bắt đầu quá trình trộn bằng cách so sánh hai phần tử đầu tiên (chẳng hạn phần tử thứ nhất với phần tử thứ hai, sau đó phần tử thứ ba với phần tử thứ tư...) và khi hoàn thành bước 1, tiếp tục sang bước 2. Tại bước 2, hai danh sách phần tử được trộn thành bốn danh sách phần tử. Quá trình này tiếp tục cho đến khi hai danh sách cuối cùng được trộn thành một.
Sắp xếp vun đống
Sắp xếp vun đống (heapsort) là một trong các phương pháp sắp xếp chọn. Trong mỗi bước của quá trình sắp xếp chọn, chúng ta chọn phần tử lớn nhất (hoặc nhỏ nhất) và đặt nó vào đầu (hoặc cuối) danh sách, sau đó tiếp tục với phần còn lại của danh sách. Thông thường, sắp xếp chọn có độ phức tạp O(n). Tuy nhiên, heapsort giảm độ phức tạp này bằng cách sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap). Đống là một cây nhị phân trong đó giá trị của nút gốc lớn hơn hoặc bằng giá trị của các nút con. Khi danh sách dữ liệu đã được sắp xếp thành đống, nút gốc sẽ là phần tử lớn nhất và thuật toán sẽ loại bỏ nó khỏi đống để đặt vào cuối danh sách. Sắp xếp vun đống chạy trong thời gian O(n log n).
Sắp xếp nhanh
Sắp xếp nhanh (quick sort) là một thuật toán dựa trên phương pháp chia để trị, nó dựa vào quá trình chia như sau: để chia một dãy số, chọn một phần tử gọi là 'chốt' (pivot), di chuyển tất cả các phần tử nhỏ hơn chốt về phía trước chốt và tất cả các phần tử lớn hơn chốt về phía sau (nếu sắp xếp theo thứ tự tăng dần); nếu sắp xếp theo thứ tự giảm dần, di chuyển tất cả các phần tử nhỏ hơn chốt về bên phải chốt và lớn hơn chốt về bên trái chốt. Quá trình này có thể thực hiện trong thời gian tuyến tính. Tiếp tục chia các dãy con như vậy cho đến khi các dãy chỉ còn một phần tử.
Điểm khác biệt giữa sắp xếp nhanh và sắp xếp trộn là trong sắp xếp trộn, thứ tự được xác định khi 'trộn', nghĩa là khi tổng hợp các giải pháp sau khi các bài toán con đã được giải, trong khi đó sắp xếp nhanh tập trung vào thứ tự các phần tử khi phân chia một danh sách thành hai danh sách con.
Ngoài ra, còn nhiều thuật toán sắp xếp khác, nhiều trong số đó đã được cải tiến từ các thuật toán trên. Trong số các thuật toán liệt kê trên, chúng ta thường coi các thuật toán chèn, chọn, nổi bọt là những thuật toán cơ bản, với độ phức tạp trung bình là . Ba thuật toán còn lại thường được coi là các thuật toán cao cấp, với độ phức tạp trung bình tính toán là .
Sắp xếp theo cơ số
Sắp xếp theo cơ số (radix sort) dựa trên tính chất 'số' của các khóa. Trong thuật toán sắp xếp theo cơ số, chúng ta không chỉ so sánh giá trị của các khóa mà còn so sánh từng thành phần của khóa. Giả sử các khóa là các số biểu diễn theo hệ cơ số M. Khi đó, sắp xếp theo cơ số sẽ so sánh từng...
Chúng ta mô tả cách sắp xếp này khi M=10. Giả sử cần sắp xếp các hồ sơ đánh số bởi 3 chữ số thập phân. Đầu tiên, chia các hồ sơ thành các đống dựa trên chữ số hàng trăm (đồng thời sắp xếp các đống theo thứ tự của chữ số hàng trăm), trong mỗi đống con, chia tiếp theo chữ số hàng chục, cuối cùng trong từng đống cùng chữ số hàng trăm và hàng chục, sắp xếp theo thứ tự của chữ số hàng đơn vị.
Trong máy tính, việc sắp xếp theo cơ số nhị phân (cơ số 2) hoặc các lũy thừa của 2 là phương pháp thuận lợi nhất. Trường hợp cụ thể với cơ số 2, phân hoạch giống như trong Quick Sort, chỉ khác ở cách lựa chọn phần tử chốt.
Sắp xếp đếm phân phối
Sắp xếp đếm phân phối là phương pháp sắp xếp có độ phức tạp tuyến tính trong trường hợp các khóa có giá trị hữu hạn trong khoảng xác định. Giả sử danh sách các phần tử chứa các giá trị tự nhiên trong khoảng
Sắp xếp đếm phân phối đầu tiên đếm số lượng các phần tử thuộc danh sách có giá trị k với . Số lượng này được ghi vào mảng . Sau đó, duyệt qua các giá trị k từ 1 đến M, ta xếp lần lượt các phần tử vào danh sách theo số lần đếm.
Sắp xếp Shell
Shell sort là một thuật toán sắp xếp rất hiệu quả dựa trên thuật toán sắp xếp chèn. Thuật toán này tránh được việc phải hoán đổi vị trí của các phần tử xa nhau trong quá trình sắp xếp, khác biệt so với thuật toán sắp xếp chọn.
