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.

QuickSort là gì?

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 thức hoạt động của thuật toán QuickSort như thế nào?

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²).

Phương pháp	Cách hoạt động	Đặc điểm
Pivot đầu mảng	Lấy phần tử ở đầu mảng làm pivot	Dễ triển khai nhưng dễ tạo phân hoạch lệch nếu dữ liệu đã gần được sắp xếp
Pivot cuối mảng	Sử dụng phần tử nằm cuối mảng làm pivot	Thường được dùng với Lomuto Partition nhờ cách cài đặt đơn giản
Pivot giữa mảng	Chọn phần tử nằm gần vị trí trung tâm của mảng	Giúp giảm nguy cơ chia mảng quá lệch trong một số trường hợp
Pivot ngẫu nhiên	Xác định pivot bằng cách chọn ngẫu nhiên một phần tử trong mảng	Hạn chế khả năng liên tục gặp trường hợp phân hoạch không cân bằng
Lomuto Partition	Duyệt mảng theo một hướng và sử dụng chỉ số để xác định ranh giới giữa các nhóm phần tử	Dễ hiểu, dễ lập trình nhưng có thể phát sinh nhiều phép hoán đổi
Hoare Partition	Sử dụng hai con trỏ di chuyển từ hai phía và hoán đổi các phần tử nằm sai vị trí	Thường cần ít phép hoán đổi hơn nhưng cách triển khai phức tạp hơn

Cách chọn Pivot và Partition trong QuickSort

Ư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	Time Complexity	Space Complexity
Best Case	O(n log n)	O(log n)
Average Case	O(n log n)	O(log n)
Worst Case	O(n²)	O(n)

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²).

Độ phức tạp của thuật toán QuickSort

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.

#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;

for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}

swap(arr[i + 1], arr[high]);
return i + 1;
}

void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);

quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}

int main() {
int arr[] = {8, 3, 1, 7, 0, 10, 2};
int n = sizeof(arr) / sizeof(arr[0]);

quickSort(arr, 0, n - 1);

for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}

return 0;
}

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ả:

Trạng thái	Dữ liệu
Before Sorting	8 3 1 7 0 10 2
After Sorting	0 1 2 3 7 8 10

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.

public class QuickSortExample {

static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;

for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;

return i + 1;
}

static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);

quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}

public static void main(String[] args) {
int[] arr = {9, 4, 12, 2, 7, 1, 10, 5};

System.out.print("Before Sorting: ");
for (int value : arr) {
System.out.print(value + " ");
}

quickSort(arr, 0, arr.length - 1);

System.out.print("\nAfter Sorting: ");
for (int value : arr) {
System.out.print(value + " ");
}
}
}

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ả:

Trạng thái	Dữ liệu
Before Sorting	9 4 12 2 7 1 10 5
After Sorting	1 2 4 5 7 9 10 12

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.

def partition(arr, low, high):
pivot = arr[high]
i = low - 1

for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]

arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1

def quick_sort(arr, low, high):
if low < high:
pivot_index = partition(arr, low, high)

quick_sort(arr, low, pivot_index - 1)
quick_sort(arr, pivot_index + 1, high)

arr = [13, 6, 2, 15, 4, 9, 1, 8]

print("Before Sorting:", *arr)

quick_sort(arr, 0, len(arr) - 1)

print("After Sorting:", *arr)

Đ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ả:

Trạng thái	Dữ liệu
Before Sorting	13 6 2 15 4 9 1 8
After Sorting	1 2 4 6 8 9 13 15

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.

using System;

class QuickSortExample
{
static int Partition(int[] arr, int low, int high)
{
int pivot = arr[high];
int i = low - 1;

for (int j = low; j < high; j++)
{
if (arr[j] < pivot)
{
i++;

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

int swap = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = swap;

return i + 1;
}

static void QuickSort(int[] arr, int low, int high)
{
if (low < high)
{
int pivotIndex = Partition(arr, low, high);

QuickSort(arr, low, pivotIndex - 1);
QuickSort(arr, pivotIndex + 1, high);
}
}

static void Main()
{
int[] arr = {14, 5, 9, 2, 11, 3, 7};

Console.WriteLine("Before Sorting: " + string.Join(" ", arr));

QuickSort(arr, 0, arr.Length - 1);

Console.WriteLine("After Sorting: " + string.Join(" ", arr));
}
}

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ả:

Trạng thái	Dữ liệu
Before Sorting	14 5 9 2 11 3 7
After Sorting	2 3 5 7 9 11 14

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ý.

Trạng thái	Dữ liệu
Before Sorting	18 6 13 4 10 2 15 8
After Sorting	2 4 6 8 10 13 15 18

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ự.

Tiêu chí	QuickSort	Merge Sort
Nguyên lý hoạt động	Chọn pivot, phân hoạch mảng rồi tiếp tục sắp xếp các phần con	Chia mảng thành hai phần, sắp xếp từng phần rồi hợp nhất
Độ phức tạp trung bình	O(n log n)	O(n log n)
Độ phức tạp trường hợp xấu nhất	O(n²)	O(n log n)
Bộ nhớ bổ sung	Thấp hơn khi triển khai in-place	Thường cần thêm bộ nhớ để lưu dữ liệu khi merge
Tính ổn định	Không ổn định trong cách triển khai phổ biến	Có tính ổn định
Hiệu suất với mảng	Thường phù hợp khi sắp xếp dữ liệu trực tiếp trong bộ nhớ	Hiệu quả nhưng cần thêm vùng nhớ khi xử lý mảng
Phù hợp với linked list	Không phải lựa chọn tối ưu	Phù hợp hơn do quá trình chia và hợp nhất thuận tiện
Yếu tố ảnh hưởng hiệu suất	Phụ thuộc đáng kể vào cách chọn pivot và partition	Hiệu suất ổn định hơn giữa các trường hợp

So sánh QuickSort và Merge Sort khác gì nhau?

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