Các thuật toán sắp xếp lập trình viên phải biết

2978
thuật toán sắp xếp

Trong khoa học máy tính và trong toán học, thuật toán sắp xếp là một thuật toán sắp xếp các phần tử của một danh sách (hoặc một mảng) theo thứ tự (tăng hoặc giảm).

Bài viết này xin phép tổng hợp lại một số thuật toán sắp xếp phổ biến. Cùng bắt đầu nhé!

  Thuật toán trong lập trình – Đôi điều tản mạn
  Thuật toán NegaMax - Biến thể tối giản của MiniMax

Merge sort

Giống như Quick sort, Merge sort là thuật toán chia để trị. Chia mảng thành các mảng nhỏ, sau đó gộp các mảng nhỏ đã sắp xếp lại với nhau.

Ví dụ với mảng 38, 27, 43, 3, 9, 82, 10, trình tự của merge sort sẽ như sau:

thuật toán sắp xếp

Triển khai thuật toán: Vì merge sort là một thuật toán sử dụng rất nhiều bộ nhớ nên sẽ tốt hơn khi sử dụng linked list, với linked list thì việc tách mảng và lưu trữ sẽ đơn giản hơn rất nhiều so với sử dụng mảng thông thường (Bạn cần có kiến thức cơ bản về con trỏ trước khi xem đoạn code dưới).

Counting sort

Counting sort là một kỹ thuật sắp xếp các đối tượng trong một phạm vị cụ thể. Nó hoạt động bằng cách đếm số lượng các đôi tượng có giá trị giống nhau. Sau đó sử dụng một chút toán học để tính toán vị trí cuối cùng của đối tượng đó.

Độ phức tạp của thuật toán này là O(n+k) với n là số lượng đối lượng, k là phạm vị giá trị của n đối tượng.

Hãy tìm hiểu thông qua 1 ví dụ:

Triển khai thuật toán:

Đây là một đoạn code sắp xếp mảng các ký tự, thuật toán cũng có thể được sử dụng để sắp xếp mảng các số nguyên. Với mảng các số nguyên bao gồm cả số âm và dương thì cần phải thay đổi thuật toán 1 chút. Lí do là vì trong c++ bạn không thể truy cập giá trị tại ví trí âm trong mảng. Để giải quyết vấn đề này bạn cần tính lại khoảng k và xây dựng lại mảng count sao cho phần tử nhỏ nhất ở trị trí 0.

Xem thêm bộ tài liệu tiếng Việt học lập trình C++ hay nhất.

Radix sort

Các thuật toán quen thuộc như quick sort, merge sort, heap sort,… là các thuật toán sắp xếp dựa vào giá trị của các phép so sánh, độ phức tạo của các thuật toán này không thể tốt hơn O(nLogn). Còn với thuật toán counting sort ở trên, là một thuật toán tuyến tính với độ phức tạp là O(n+k). Trong trường hợp k bằng n*n thì counting sort là một lựa chọn tồi. Radix sort là một lựa chọn tốt trong TH này.

Tư tưởng của thuật toán này là sắp xếp các số theo giá trị của hàng chục, hàng trăm, hàng nghìn, …

Ví dụ:

Triển khai thuật toán:

Bài viết tham khảo:

Đừng bỏ lỡ các bài viết hay nhất về thuật toán:

Xem thêm việc làm Software Developers mới nhất trên TopDev

TopDev via viblo

  Hệ gợi ý bằng thuật toán Sørensen–Dice trong Rails với gem Predictor
  Thuật toán sắp xếp nào là nhanh nhất?
SHARE