Chào các bạn!
Tiếp theo chuỗi series về các thuật toán sắp xếp và tìm kiếm căn bản, thì ở bài viết này mình sẽ trình bày các bạn phần thuật toán Sắp xếp nhanh – Quick Sort.
Được mệnh danh là một trong các thuật toán sắp xếp nhanh, hiệu quả và dễ implement! Chúng ta cùng tìm hiểu xem nó sao nhé!
Đặt vấn đề
Cho một dãy số kích thước N phần tử, hãy sắp xếp dãy số đó theo thứ tự tăng dần.
Ở bài viết trước, mình đã trình bày về giải thuật Selection Sort, thì ta đã thấy rằng, nhược điểm của nó là… quá chậm. Và trong một số ứng dụng, điều này là không thể chấp nhận.
Vậy nên từ đó, người ta đã nghĩ ra một giải pháp chạy nhanh hơn, thay thế cho Selection Sort với độ phức tạp thuật toán nhỏ hơn
O(n∗logn)O(n*logn) (tuy nhiên, không phải lúc nào cũng đúng bằng
n∗lognn*logn nhé mn).
Ý tưởng thuật toán
Thuật toán chia làm 3 bước sau đây:
- Nếu dãy số đã cho có không quá 1 phần tử, thì coi như dãy số đã được sắp xếp. Không cần làm gì thêm.
- Trong trường hợp dãy số nhiều hơn 1 phần tử thì, chia dãy số đã cho ra làm 2 nửa:
- Nửa bên trái bao gồm các số
<Xlt X - Nửa bên phải bao gồm các số
≥Xgeq X
với
XX là một giá trị nào đó (thuộc dãy số đã cho).
- Nửa bên trái bao gồm các số
- Tiếp tục, lặp lại bước 1, bước 2 ở trên với 2 dãy con vừa chia đôi một cách độc lập.
Dưới đây là hình minh họa cho thuật toán này (nguồn ảnh)
Có 2 điểm quan trọng nhất của thuật toán này mà bạn cần nắm chắc. Chỉ cần nắm chắc nó, thì coi như bạn đã hiểu rõ thuật toán QuickSort, để rồi không cần phải học thuộc hay copy code gì nữa… 2 điểm đó là:
- Ý tưởng chính của thuật toán là: chia để trị (chia dãy số ra làm 2)
- Nhưng chia như thế nào? Cách chọn giá trị
XXlà điểm mấu chốt
Dưới đây là đoạn code mẫu mình đã chuẩn bị:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | <span class="token keyword">void</span> <span class="token function">quickSort</span><span class="token punctuation">(</span><span class="token keyword">int</span> <span class="token operator">*</span>arr<span class="token punctuation">,</span> <span class="token keyword">int</span> l<span class="token punctuation">,</span> <span class="token keyword">int</span> r<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// Nếu dãy số không quá 1 phần tử</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>l <span class="token operator">>=</span> r<span class="token punctuation">)</span> <span class="token keyword">return</span><span class="token punctuation">;</span> <span class="token comment">// Nếu dãy số >1 phần tử</span> <span class="token keyword">int</span> i <span class="token operator">=</span> l<span class="token punctuation">,</span> j <span class="token operator">=</span> r<span class="token punctuation">;</span> <span class="token comment">// Chọn X là giá trị ngẫu nhiên trong arr</span> <span class="token keyword">int</span> X <span class="token operator">=</span> arr<span class="token punctuation">[</span><span class="token function">random</span><span class="token punctuation">(</span>l<span class="token punctuation">,</span> r<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// Phân đôi dãy số</span> <span class="token keyword">while</span> <span class="token punctuation">(</span>i <span class="token operator"><</span> j<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">while</span> <span class="token punctuation">(</span>arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator"><</span> X<span class="token punctuation">)</span> i<span class="token operator">++</span><span class="token punctuation">;</span> <span class="token keyword">while</span> <span class="token punctuation">(</span>arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">></span> X<span class="token punctuation">)</span> j<span class="token operator">--</span><span class="token punctuation">;</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>i <span class="token operator"><=</span> j<span class="token punctuation">)</span> <span class="token function">swap</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>i<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">,</span> arr<span class="token punctuation">[</span>j<span class="token operator">--</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token comment">// Sau vòng lặp while ở trên, ta đã có: </span> <span class="token comment">// [l..j] bao gôm những giá trị <= X</span> <span class="token comment">// [i..r] bao gồm những giá trị >= X</span> <span class="token comment">// Tuy nhiên, không đảm bảo rằng các phần tử trong 2 dãy con này đã được sắp xếp.</span> <span class="token comment">// Do đó, ta cần gọi lại đệ quy để xử lý 2 dãy con.</span> <span class="token function">quickSort</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> i<span class="token punctuation">,</span> r<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">quickSort</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> l<span class="token punctuation">,</span> j<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> |
Xem full code chương trình: https://ideone.com/hI4NQB
Đoạn code trên, mình đã lựa chọn điểm
XX chính là giá trị ngẫu nhiên trong dãy số. Lí do vì sao thì là để cho dãy số được chia 2 dựa trên một yếu tố ngẫu nhiên (lưu ý: một số tài liệu khác có thể chọn giá trị cố định như ở đầu hoặc ở cuối hoặc giữa). Và điều này, theo mình là hoàn toàn không liên quan đến tốc độ chạy của thuật toán, do dãy số đã cho ban đầu cũng sẽ có một thứ tự ngẫu nhiên không biết trước được, dẫn đến cách chọn nào cũng sẽ có ưu và nhược điểm. Nhưng ở đây, mình vẫn lựa chọn vị trí ngẫu nhiên, để ý muốn nói rằng, chúng ta hoàn toàn tự do trong việc lựa chọn giá trị
XX.
Đánh giá độ phức tạp
Độ phức tạp của thuật toán Quick sort đã được chứng minh đạt giá trị trung bình là:
O(N∗logN)O(N*logN).
Khi các bạn nhấm vào link full code ở trên: các bạn sẽ tìm thấy dòng
Success #stdin #stdout 0.14s 7508KB
Nó mô tả Memory và Thời gian xử lý của đoạn code: mình đã tạo ra ngẫu nhiên 1.000.000 số và sắp xếp lại nó, nhưng thời gian sắp xếp chỉ có 0.14s. Cho thấy độ mạnh mẽ của thuật toán.
Kết luận
Trên đây, mình đã trình bày các bạn về thuật toán Quick Sort. Hi vọng bài viết sẽ giúp bạn phần nào hiểu được ý tưởng cũng như cài đặt nó mà không cần học thuộc bất cứ dòng code nào.
Nếu bạn có bất cứ ý kiến nào đóng góp, xin hãy gửi comment, mình sẽ trả lời và khắc phục cho những lần sau.