Quick Sort - Thuật toán sắp xếp đột phá trong thế kỉ XX

Thời đại công nghệ số phát triển như vũ bão kéo theo nhiều thuật toán ra đời với tất cả sự sáng tạo tuyệt vời. Quick Sort – một trong những thuật toán sắp xếp đột phá trong thế kỉ XX cung cấp đến người dùng cách thức tiếp cận nhanh chóng nhất, giúp có được những phương pháp sắp xếp dễ dàng nhất. Cpphinditutorials sẽ cùng bạn tìm hiểu tất tần tật về thuật toán QUICK SORT.

THUẬT TOÁN QUICK SORT LÀ GÌ?

Quick Sort được biết đến là một thuật toán quan trọng hiện nay được dùng phổ biến trong lập trình C++. Quick Sort được hiểu là thuật toán sắp xếp theo kiểu Part Sort (phân chia). Sử dụng thuật toán này mang lại hiệu quả cao dựa trên việc phân chia các mảng dữ liệu thành những nhóm phần tử nhỏ hơn.

Thuật toán Quick Sort chia mảng thành hai phần, bằng việc so sánh từng phần tử của mảng với phần tử chốt. Một mảng là các phần tử nhỏ hơn hoặc mảng bằng phần tử chốt, một mảng là các phần tử lớn hơn so với phần tử chốt. Quá trình tiếp tục diễn ra cho đến khi độ dài của những mảng con đều bằng 1. Sử dụng phương pháp đệ quy, chúng ta có thể có cách sắp xếp nhanh những mảng con, sau khi kết thúc chương trình sẽ được một mảng đã được sắp xếp hoàn chỉnh.

KỸ THUẬT CHỌN PHẦN TỬ CHỐT

Trong những trường hợp đặc biệt, kỹ thuật chọn phần tử chốt có ảnh hưởng rất lớn đến khả năng rơi vào các vòng lặp vô hạn. Vì vậy tốt nhất chúng ta nên chọn phần tử chốt nằm trung vị ở danh sách. Sau log2(n) lần chia sẽ đạt được kích thướng mảng con là bằng 1. Cách chọn phần tử chốt như sau:

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

Ý TƯỞNG THUẬT TOÁN QUICK SORT

Ứng dụng của thuật toán Quick Sort có thể nói là rất hữu ích đối với nhiều lĩnh vực như máy tính thương mại, tính toán số hay tìm kiếm thông tin nhanh chóng. Những ý tưởng của thuật toán Quick Sort phổ biến nhất là:

Lựa chọn được phần tử chốt.
Khai báo hai biến con trỏ để duyệt hai phía của phần tử chốt.
Biến bên trái sẽ trỏ đến từng phần tử của mảng con, còn biến bên trái là của phần tử chốt.
Biến bên phải sẽ trỏ đến từng phần tử của mảng con, biến bên trái sẽ là của phần tử chốt.
Nếu thấy biến bên trái nhỏ hơn phần tử chốt thì chúng ta sẽ tiến hành di chuyển sang phải.
Nếu thấy biến bên phải nhỏ hơn phần tử chốt thì chúng ta sẽ di chuyển sang trái.
Trong trường hợp nếu không xảy ra như ở trường hợp 5 và 6, chúng ta sẽ tráo đổi giá trị của 2 biến trái và phải.
Nếu biến bên trái lớn hơn biến bên phải thì đây là giá trị chốt mới.
Giải thuật.

GIẢI THUẬT

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

public class QuickSort {

public static void main(String[] args) {

int[] x = {6, 2, 3, 4, 5, 9, 1};

printArray(x);

NHỮNG ĐIỀU CẦN NÊN BIẾT VỀ THUẬT TOÁN SẮP XẾP ĐỘT PHÁ CỦA TK XX – QUICK SORT

NGUYÊN TẮC HOẠT ĐỘNG CỦA QUICKSORT

QuickSort hoạt động dựa trên nguyên tắc “chia để trị”. Quy trình hoàn chỉnh của thuật toán có thể được mô tả như sau:

– Shuffle: hoán vị toàn bộ mảng. Đây là bước đầu tiên của QuickSort có nhiệm vụ “đảo” toàn bộ mảng nhằm tránh trường hợp xấu nhất là mảng sắp xếp theo thứ tự giảm dần.

– Select pivot: QuickSort chọn một phần tử từ mảng, gọi là “pivot”, thường là phần tử cuối cùng hoặc phần tử đầu tiên trong mảng.

– Partition: QuickSort chia mảng thành hai phần, một phần có các phần tử nhỏ hơn hoặc bằng pivot và phần còn lại chứa các phần tử lớn hơn pivot.

– Sort: Sau khi phân loại, Quicksort đệ quy lên hai mảng con này, lặp lại quá trình cho đến khi mảng đã sắp xếp hoàn chỉnh.

ƯU ĐIỂM CỦA QUICKSORT

– Hiệu suất cao: QuickSort là một trong những thuật toán sắp xếp nhanh nhất trong thực tế. Trong trường hợp trung bình, độ phức tạp là O(nlogn).

– Sử dụng ít bộ nhớ bổ sung: QuickSort là một thuật toán sắp xếp trong (in-place) tức là về cơ bản, QuickSort không yêu cầu thêm bộ nhớ (như MergeSort)

– Dễ cài đặt: Thuật toán này có thể được cài đặt một cách đơn giản và hiệu quả, thường chỉ cần vài dòng mã.

NHƯỢC ĐIỂM CỦA QUICKSORT

– Trong trường hợp xấu nhất, khi pivot được chọn không tốt hoặc mảng được sắp xếp giảm dần, QuickSort có thể có độ phức tạp là O(n^2). Tuy nhiên, trường hợp này đã được hạn chế nhờ bước shuffle đầu tiên.

– Ngoài ra, vào thập niên 90 của thế kỷ trước, tức là sau khi Quicksort được phát triển 30 năm, các nhà khoa học nhận ra QuickSort xử lý mảng có nhiều phần tử trùng lặp với thời gian rất lâu. Tuy nhiên, cũng trong thập kỷ này, Edsger Dijkstra (một nhà khoa học người Hà Lan) đã lấy ý tưởng từ lá cờ Hà Lan

để phát minh ra thuật toán 3-way partitioning hay Dutch National Flag với ý tưởng có thể trình bày một cách ngắn gọn như sau: Chia mảng ra 3 phần bằng phần tử pivot, bé hơn phần tử pivot và lớn hơn phần tử pivot. Với cách thức này, thuật toán QuickSort đã tối ưu hoá sắp xếp mảng có các phân tử trùng lặp với độ phức tạp gần như tuyến tính.

ỨNG DỤNG CỦA QUICKSORT

QuickSort được sử dụng rộng rãi trong thực tế và có nhiều ứng dụng, bao gồm:

Sắp xếp dữ liệu trong cơ sở dữ liệu.
Tìm kiếm phần tử trong danh sách đã sắp xếp.
Sử dụng trong các thư viện sắp xếp của nhiều ngôn ngữ lập trình.

Trong tổng quan, QuickSort là một thuật toán sắp xếp mạnh mẽ và hiệu quả khi được triển khai đúng cách. Mặc dù có một số điểm yếu, nhưng các biến thể và cải tiến đã giúp nâng cao hiệu suất của nó và biến nó thành một công cụ quan trọng trong thế giới lập trình và khoa học máy tính.

ĐỘ NỔI TIẾNG CỦA QUICKSORT

QuickSort được xem là thuật toán sắp xếp đột phá nhất, đứng vào hàng ngũ những thuật toán có sức ảnh hưởng lớn nhất thế kỷ 20 MATH 6140 – The Top Ten Algorithms from the 20th Century | pi.math.cornell.edu. Đặc biệt hơn, thuật toán QuickSort đã giúp người cha của nó – Sir Charles Antony Richard Hoare thắng giải Turing năm 1980. Ngày nay, QuickSort vẫn được xem là thuật toán sắp xếp quan trọng nhất và có ảnh hưởng lớn nhất đối với ngành Khoa học máy tính nói riêng và Công nghệ thông tin nói chung.