QuickSort là gì? Cách triển khai Quick Sort cho các ngôn ngữ lập trình
03/09/2026Được Tony Hoare phát triển từ năm 1959, QuickSort đã trở thành một trong những thuật toán sắp xếp được sử dụng rộng rãi trong khoa học máy tính. Cùng Viettel IDC tìm hiểu QuickSort là gì, cách thuật toán hoạt động, độ phức tạp, ưu nhược điểm và cách triển khai trong thực tế.
QuickSort là gì?
QuickSort là một thuật toán sắp xếp dựa trên phương pháp Chia để trị (Divide and Conquer). Quicksort chọn một phần tử làm pivot và phân hoạch mảng đã cho xung quanh pivot đó bằng cách đặt pivot vào đúng vị trí của nó trong mảng đã sắp xếp.
Cách thức hoạt động của thuật toán QuickSort như thế nào?
QuickSort hoạt động bằng cách chọn một phần tử làm mốc, chia mảng thành các phần nhỏ hơn dựa trên phần tử đó rồi tiếp tục áp dụng cùng quy trình cho từng mảng con. Quá trình lặp lại cho đến khi các phần tử được đưa về đúng thứ tự.
- Bước 1: Chọn phần tử Pivot: Thuật toán chọn một phần tử trong mảng làm pivot. Pivot có thể là phần tử đầu, cuối, ở giữa hoặc được chọn ngẫu nhiên tùy theo cách triển khai.
- Bước 2: Phân hoạch mảng theo Pivot: Các phần tử nhỏ hơn pivot được đưa về một phía, còn các phần tử lớn hơn được chuyển sang phía còn lại. Sau bước này, pivot được đặt vào vị trí phù hợp trong thứ tự sắp xếp.
- Bước 3: Tiếp tục sắp xếp các mảng con: Quick Sort tiếp tục áp dụng cùng quy trình cho hai phần mảng nằm ở hai phía của pivot. Mỗi mảng con lại được chọn pivot và phân hoạch cho đến khi kích thước ngày càng nhỏ.
- Bước 4: Dừng quá trình đệ quy: Khi mảng con chỉ còn một phần tử hoặc không còn phần tử nào, thuật toán dừng xử lý vì phần đó đã được xem là có thứ tự. Sau khi toàn bộ quá trình đệ quy hoàn tất, mảng ban đầu được sắp xếp theo thứ tự mong muốn.
Ví dụ: Giả sử cần sắp xếp mảng [8, 3, 1, 7, 0, 10, 2] theo thứ tự tăng dần và chọn 7 làm pivot.
- Sau khi phân hoạch theo pivot 7, các phần tử nhỏ hơn 7 được đưa về một phía, còn các phần tử lớn hơn 7 nằm ở phía còn lại. Mảng có thể được chia thành hai phần tương ứng là [3, 1, 0, 2] và [8, 10].
- QuickSort tiếp tục áp dụng cùng quy trình cho từng mảng con, chọn pivot mới và phân hoạch cho đến khi mỗi phần chỉ còn một phần tử.
- Khi toàn bộ quá trình hoàn tất, mảng thu được là [0, 1, 2, 3, 7, 8, 10].
Cách chọn Pivot và Partition trong QuickSort
Pivot và partition là hai thành phần quyết định cách QuickSort chia nhỏ mảng trong mỗi lần xử lý. Pivot đóng vai trò làm mốc so sánh, còn partition sắp xếp lại các phần tử dựa trên mốc đó để tạo ra các mảng con.
Một pivot phù hợp giúp mảng được chia thành các phần tương đối cân bằng, qua đó duy trì hiệu suất tốt cho QuickSort. Ngược lại, nếu pivot liên tục tạo ra các phân hoạch quá lệch, độ phức tạp của thuật toán có thể tăng lên O(n²).
Ưu điểm và nhược điểm của QuickSort là gì?
Thuật toán QuickSort được sử dụng phổ biến nhờ tốc độ xử lý tốt và khả năng sắp xếp dữ liệu hiệu quả trong nhiều trường hợp. Tuy nhiên, hiệu suất của thuật toán phụ thuộc đáng kể vào cách chọn pivot và trạng thái của dữ liệu đầu vào.
Ưu điểm của QuickSort:
- Có độ phức tạp trung bình O(n log n), phù hợp với các tập dữ liệu lớn.
- Có thể triển khai theo hướng in-place, giúp hạn chế lượng bộ nhớ bổ sung cần sử dụng.
- Hoạt động hiệu quả với mảng nhờ khả năng truy cập dữ liệu liên tục trong bộ nhớ.
- Cấu trúc chia để trị giúp thuật toán dễ áp dụng cho nhiều bài toán sắp xếp khác nhau.
- Khi pivot được lựa chọn hợp lý, các mảng con được chia tương đối cân bằng và tốc độ xử lý được duy trì tốt.
Nhược điểm của QuickSort:
- Độ phức tạp có thể tăng lên O(n²) trong trường hợp pivot liên tục tạo ra các phân hoạch mất cân bằng.
- Hiệu suất phụ thuộc nhiều vào chiến lược chọn pivot và phương pháp partition.
- QuickSort thông thường không phải là thuật toán sắp xếp ổn định, nên thứ tự tương đối của các phần tử có giá trị bằng nhau có thể thay đổi.
- Quá trình đệ quy có thể làm tăng mức sử dụng stack nếu mảng bị chia lệch nhiều lần liên tiếp.
- Việc triển khai và tối ưu QuickSort phức tạp hơn một số thuật toán sắp xếp cơ bản.
Độ phức tạp của thuật toán QuickSort
Hiệu suất của QuickSort phụ thuộc vào cách pivot chia mảng sau mỗi lần partition. Khi các phần được chia tương đối cân bằng, thuật toán đạt tốc độ tốt; ngược lại, phân hoạch quá lệch có thể khiến số phép xử lý tăng đáng kể.
Trường hợp tốt nhất (Best Case QuickSort)
Trường hợp tốt nhất xảy ra khi pivot chia mảng thành hai phần có kích thước gần bằng nhau sau mỗi lần partition. Khi đó, số cấp đệ quy vào khoảng log n và mỗi cấp cần xử lý khoảng n phần tử, nên độ phức tạp thời gian đạt O(n log n).
Ví dụ: Với mảng [1, 2, 3, 4, 5, 6, 7], nếu chọn 4 làm pivot, hai mảng con thu được là [1, 2, 3] và [5, 6, 7].
Công thức truy hồi:
T(n) = 2T(n/2) + O(n)
Trường hợp trung bình (Average Case QuickSort)
Trong trường hợp trung bình, các lần phân hoạch không hoàn toàn cân bằng nhưng cũng không liên tục tạo ra những mảng con quá lệch. QuickSort vẫn duy trì độ phức tạp kỳ vọng khoảng O(n log n) và đây cũng là lý do thuật toán đạt hiệu suất tốt trong nhiều tình huống thực tế.
Ví dụ: Mảng [8, 3, 6, 1, 7, 2, 5, 4] có thể được chia thành các mảng con với kích thước khác nhau tùy pivot, nhưng không liên tục rơi vào dạng 0 và n - 1.
Công thức tổng quát:
T(n) = T(k) + T(n - k - 1) + O(n)
Trường hợp xấu nhất (Worst Case QuickSort)
Worst Case xảy ra khi pivot liên tục là phần tử nhỏ nhất hoặc lớn nhất trong vùng dữ liệu đang xử lý. Mỗi lần partition khi đó chỉ tách được một phần tử, làm độ sâu đệ quy tăng đến gần n và độ phức tạp thời gian đạt O(n²).
Ví dụ: Với mảng [1, 2, 3, 4, 5, 6, 7], nếu luôn chọn phần tử cuối làm pivot, QuickSort sẽ lần lượt chọn 7, 6, 5...
Công thức truy hồi:
T(n) = T(n - 1) + O(n)
Khi khai triển, tổng số phép xử lý tăng theo:
n + (n - 1) + ... + 1
Do đó, độ phức tạp thời gian trong Worst Case là O(n²).
Hướng dẫn cách triển khai QuickSort cho các ngôn ngữ lập trình
QuickSort có thể được triển khai trên nhiều ngôn ngữ lập trình với cùng nguyên lý. Dưới đây là cách cài đặt thuật toán trên một số ngôn ngữ phổ biến.
Triển khai thuật toán Quick Sort C++
Trong C++, QuickSort có thể được xây dựng bằng hai hàm chính là partition() để phân hoạch mảng và quickSort() để thực hiện quá trình sắp xếp đệ quy.
Trong đoạn mã trên, hàm partition() chọn phần tử cuối mảng làm pivot và đưa các giá trị nhỏ hơn pivot về phía trước. Sau khi phân hoạch hoàn tất, hàm trả về vị trí mới của pivot. Hàm quickSort() tiếp tục gọi đệ quy cho hai phần mảng nằm trước và sau pivot.
Kết quả:
Thuật toán QuickSort Java
Với Java, QuickSort có thể xử lý trực tiếp các phần tử trong mảng thông qua chỉ số vị trí. Sau mỗi lần phân hoạch, pivot được đưa về vị trí phù hợp và hai phần còn lại tiếp tục được sắp xếp bằng đệ quy.
Trong ví dụ trên, phần tử cuối của mỗi đoạn mảng được chọn làm pivot. Hàm partition() xác định vị trí phù hợp cho pivot, còn quickSort() tiếp tục xử lý hai phần dữ liệu ở hai phía cho đến khi mảng được sắp xếp hoàn chỉnh.
Kết quả:
Cách triển khai Quick Sort Python 3
Python 3 hỗ trợ hoán đổi giá trị trực tiếp bằng cú pháp a, b = b, a, nên phần triển khai QuickSort gọn hơn so với nhiều ngôn ngữ khác. Ví dụ dưới đây sắp xếp danh sách số nguyên theo thứ tự tăng dần.
Điểm đáng chú ý trong phiên bản Python là thao tác hoán đổi hai phần tử không cần biến tạm, giúp code ngắn và dễ theo dõi hơn. Danh sách ban đầu được thay đổi trực tiếp trong quá trình chạy nên không cần tạo thêm một danh sách kết quả riêng.
Kết quả:
Triển khai QuickSort trong C#
Trong C#, QuickSort có thể được xây dựng với mảng số nguyên và các phương thức tĩnh để xử lý từng vùng dữ liệu. Cách viết dưới đây giữ cấu trúc rõ ràng, phù hợp khi cần minh họa thuật toán trong ứng dụng console.
Trong phiên bản này, string.Join() được sử dụng để hiển thị toàn bộ mảng trên cùng một dòng, giúp phần kết quả dễ theo dõi hơn. Hàm QuickSort() thay đổi trực tiếp thứ tự phần tử trong mảng gốc.
Kết quả:
Triển khai QuickSort Javascript
Trong JavaScript, có thể tách riêng thao tác hoán đổi phần tử thành hàm swap() để phần xử lý partition rõ ràng hơn. Cách triển khai dưới đây chọn phần tử cuối mảng làm pivot và tiếp tục sắp xếp hai vùng dữ liệu bằng đệ quy.
Ở cách viết này, swap() đảm nhiệm riêng thao tác đổi chỗ hai phần tử, giúp phần partition() dễ theo dõi hơn. Sau mỗi lần phân hoạch, pivotIndex được dùng để xác định hai vùng mảng cần tiếp tục xử lý.
So sánh QuickSort và Merge Sort khác gì nhau?
QuickSort và Merge Sort đều dựa trên phương pháp chia để trị (Divide and Conquer), nhưng khác nhau ở cách xử lý dữ liệu sau khi chia. QuickSort phân hoạch mảng quanh một pivot, trong khi Merge Sort chia mảng thành các phần nhỏ rồi hợp nhất chúng theo đúng thứ tự.
Kết luận
Hiểu rõ QuickSort là gì giúp người đọc nắm được nguyên lý chia để trị, vai trò của pivot và cách thuật toán xử lý dữ liệu theo từng bước. Đây là nền tảng quan trọng khi nghiên cứu các thuật toán sắp xếp và lựa chọn phương pháp phù hợp cho từng bài toán lập trình.
Để tìm hiểu thêm về dịch vụ, vui lòng liên hệ đến Viettel IDC:
- Hotline: 1800.8088 (miễn phí cước gọi)
- Fanpage: https://www.facebook.com/viettelidc
- Website: https://viettelidc.com.vn/
Viettel IDC - Nhà cung cấp dẫn đầu về giải pháp Trung tâm dữ liệu và Điện toán đám mây tại Việt Nam
Tin liên quan
"SOVEREIGN CLOUD" VÀ NGHỊCH LÝ CHUYỂN ĐỔI SỐ: GIẢI MÃ BÀI TOÁN TUÂN THỦ CHO NGÀNH TÀI CHÍNH & CHÍNH PHỦ
Các tổ chức thuộc nhóm ngành trọng yếu như tài chính, ngân hàng (BFSI) và cơ quan nhà nước đang khao khát hiện đại hóa hệ thống IT (chuyển đổi sang kiến trúc Microservices, sử dụng Container/Kubernetes) để tăng tốc độ triển khai dịch vụ và nâng cao trải nghiệm người dùng. Tuy nhiên, họ lại đang vấp phải một "nghịch lý" lớn: Càng muốn áp dụng công nghệ Cloud hiện đại, rào cản về tuân thủ pháp lý và an toàn thông tin càng trở nên khắt khe.
BÀI TOÁN "NOISY NEIGHBOR" TRÊN CLOUD VÀ CHIẾN LƯỢC TỐI ƯU HIỆU NĂNG CHO HỆ THỐNG CỐT LÕI
Trong kỷ nguyên mà dữ liệu là "dầu mỏ mới", việc vận hành các hệ thống xương sống (Core ERP, Core Banking) hay các workload tính toán chuyên sâu (AI, Machine Learning, Datalake) đòi hỏi năng lực phần cứng vô cùng mạnh mẽ.
"BÃO GIÁ" HẠ TẦNG CNTT VÀ BÀI TOÁN SỐNG CÒN CỦA DOANH NGHIỆP: VÌ SAO PRIVATE CLOUD DẠNG DỊCH VỤ LÊN NGÔI?
Làn sóng bùng nổ hạ tầng AI toàn cầu đang tạo ra một "cơn địa chấn" về giá phần cứng máy chủ, chip nhớ DRAM, ổ cứng doanh nghiệp và chi phí năng lượng. Đứng trước áp lực phải chuyển đổi số nhưng lại vấp phải bài toán chi phí đầu tư (CapEx) đắt đỏ cùng thời gian giao hàng kéo dài hàng tháng, các nhà quản trị công nghệ (CIO) và tài chính (CFO) đang tìm kiếm một hướng đi mới: Không cần bỏ hàng tỷ đồng mua sắm hạ tầng mà vẫn sở hữu riêng một hệ thống Private Cloud hoàn chỉnh, an toàn và sẵn sàng vận hành ngay lập tức.
Digital Workplace là gì? Xu hướng môi trường làm việc số cho doanh nghiệp
Digital Workplace là gì? Khám phá mô hình vận hành, thành phần, lợi ích, ứng dụng, thách thức và xu hướng môi trường làm việc số cho doanh nghiệp.
Lỗ hổng Shellshock là gì? Cơ chế, tác động và cách khắc phục
Lỗ hổng Shellshock (CVE-2014-6271) trong Bash là gì, vì sao nghiêm trọng? Tìm hiểu nguyên nhân, hệ thống bị ảnh hưởng và cách kiểm tra, vá lỗi.
Scratch là gì? Cách hoạt động, ứng dụng và đối tượng phù hợp
Scratch là gì? Tìm hiểu cách lập trình bằng khối lệnh, các khái niệm có thể học, ứng dụng thực tế và sự khác nhau giữa Scratch với ScratchJr.
Phân biệt các loại Web Hosting: Đâu là lựa chọn phù hợp cho website?
Phân biệt các loại Web Hosting và tìm hiểu cách mỗi mô hình hoạt động, từ đó lựa chọn giải pháp phù hợp với nhu cầu, quy mô và định hướng phát triển website.
Website có cần hosting không? Giải đáp chi tiết từ A-Z
Website có cần hosting không? Tìm hiểu vai trò của hosting, domain và các trường hợp cần và không cần mua hosting riêng cho website.
Top nhà cung cấp dịch vụ Cloud Camera uy tín tại Việt Nam
Top nhà cung cấp dịch vụ Cloud Camera uy tín tại Việt Nam, cùng tiêu chí lựa chọn và những lưu ý quan trọng trước khi đăng ký dịch vụ.
Trigger là gì trong DBMS? Cách hoạt động, các loại phổ biến và ứng dụng
Trigger là gì trong DBMS? Tìm hiểu cách trigger hoạt động, các loại phổ biến, ví dụ minh họa, ưu nhược điểm và khi nào nên sử dụng.
Bình luận ()