Thuật Toán Quick Sort

Chào mừng các bạn đến với chủ đề thuật toán lập trình.

Hôm nay chúng ta cùng tìm hiểu về thuật toán Quick Sort.
1. Nguyên lý cơ bản của Quick Sort.

– Cũng dựa trên nguyên lý chia để trị, nó chia mảng thành nhiều vùng nhỏ rồi mới thực hiện việc sắp xếp.

– Đạt được tốc độ rất nhanh cho việc sắp xếp một mảng, hiệu quả và tiêu tốn ít tài nguyên.

– Độ phức tạp thời gian là: O(nLog2(n)) với n là số lượng phần tử của tập. xấu nhất sẽ là: O(n²)

– Nguyên lý thực hiện đó là phải chọn được một phần tử ngẫu nhiên gọi là: pivot. (có thể là đầu, cuối giữa…)

– Sắp xếp các phần tử < pivot sang bên trái, còn các phần tử > pivot sang bên phải.

– Sau đó chia nó thành hai tập, một tập trái và một tập phải.

=> Mỗi tập con lúc này lại như một tập ban đầu, lại cần được sắp xếp lại => lại thực hiện chọn chốt, lại phân chia, cho đến khi số lượng phần tử chỉ còn 1. => Tính chất đệ quy.

 

2 Thực hành Thuật toán Quick Sort

– Mấu chốt của thuật toán đó là chọn được phần tử chốt hợp lý nhất, và sau đó là cách chia tệp thành 2 phần, một phần nhỏ hơn chốt và một phần lớn hơn chốt. Sau đó sử dụng tính chất đệ quy để hoàn thành quá trình sắp xếp

 

___________________________

Pass Pham

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.