Thuật toán Quick Sort là gì? 2 phút làm quen với thuật toán Quick Sort

3686
Thuật toán Quick Sort là gì

Bài viết hôm nay sẽ giới thiệu cho các bạn khái niệm thuật toán Quick Sort là gì. Bên cạnh đó, sẽ giúp các bạn làm quen với kỹ thuật chọn phần tử, ý tưởng và giải thuật với Quick Sort.

Cùng bắt đầu nhé!

  Bí mật của thuật toán ngẫu nhiên
  Hệ gợi ý bằng thuật toán Sørensen–Dice trong Rails với gem Predictor

Thuật toán Quick Sort là gì?

Thuật toán Quick Sort là một thuật toán sắp xếp hiệu quả dựa trên việc phân chia mảng dữ liệu thành các nhóm phần tử nhỏ hơn. Giải thuật sắp xếp nhanh chia mảng thành hai phần bằng cách so sánh từng phần tử của mảng với một phần tử được gọi là phần tử chốt.

Một mảng bao gồm các phần tử nhỏ hơn hoặc bằng phần tử chốt và một mảng gồm các phần tử lớn hơn phần tử chốt.

Quá trình phân chia này diễn ra cho đến khi độ dài của các mảng con đều bằng 1. Với phương pháp đệ quy ta có thể sắp xếp nhanh các mảng con sau khi kết thúc chương trình ta được một mảng đã sắp xếp hoàn chỉnh.

Giải thuật sắp xếp nhanh tỏ ra khá hiệu quả với các tập dữ liệu lớn khi mà độ phức tạp là O(nlogn).

Kỹ thuật chọn phần tử chốt

Kỹ thuật chọn phần tử chốt ảnh hưởng khá nhiều đến khả năng rơi vào các vòng lặp vô hạn đối với các trường hợp đặc biệt. Tốt nhất chọn phần tử chốt nằm ở trung vị của danh sách. Khi đó, sau log2(n) lần chia ta đạt được kích thưởng mảng con bằng 1.

Dưới đây là một số cách chọn phần tử chốt:

  • Chọn phần tử đứng đầu hoặc đứng cuối làm phần tử chốt.
  • Chọn phần tử đứng giữa danh sách làm phần tử chốt.
  • Chọn phần tử trung vị trong ba phần tử đứng đầu, đứng giữa và đứng cuối làm phần tử chốt.
  • Chọn phần tử ngẫu nhiên làm phần tử chốt. Tuy nhiên cách này rất dễ dẫn đến khả năng rơi vào các trường hợp đặc biệt.

Ý tưởng thuật toán Quick Sort

  1. Chọn phần tử chốt.
  2. Khai báo 2 biến con trỏ để trỏ để duyệt 2 phía của phần tử chốt.
  3. Biến bên trái trỏ đến từng phần tử mảng con bên trái của phần tử chốt.
  4. Biến bên phải trỏ đến từng phần tử mảng con bên phải của phần tử chốt.
  5. Khi biến bên trái nhỏ hơn phần tử chốt thì di chuyển sang phải.
  6. Khi biến bên phải nhỏ hơn phần tử chốt thì di chuyển sang trái.
  7. Nếu không xảy ra trưởng hợp 5 và 6 thì tráo đổi giá trị 2 biến trái và phải.
  8. Nếu trái lớn hơn phải thì đây là giá trị chốt mới.

Giải thuật

Dưới đây là chương trình mô phỏng thuật toán đệ quy viết trên ngôn ngữ lập trình java:

Kết luận

Cảm ơn các bạn đã theo dõi bài viết! Hy vọng các bạn có thể biết được thuật toán Quick Sort là gì sau bài viết này.

Tham khảo:

Đừng bỏ lỡ những bài viết hay về:

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

TopDev via viblo

  Core Audio là gì? Tìm hiểu về Core Audio
  Framework Hapi.js là gì? Làm quen với Hapi.js cơ bản
SHARE