Một trong những thuật toán phổ biến nhất được sử dụng trong lập trình không thể không nhắc đến Quick short. Đây là một thuật toán hỗ trợ, có chức năng chính là sắp xếp và phân loại dữ liệu. Tuy nhiên, để hiểu rõ thuật toán này và biết cách sử dụng nó đòi hỏi người dùng phải dành thời gian phân tích kỹ lưỡng. Ở bài viết hôm nay, LPTech sẽ hướng dẫn đến bạn các khái niệm cơ bản về Quick sort. Cùng tìm hiểu nhé!
Quick sort là gì?
Quick sort là một thuật toán dùng trong ngôn ngữ lập trình C++, dùng để sắp xếp, phân loại nhanh. Quick sort hoạt động theo cơ chế: Chọn một phần tử bất kỳ làm điểm đánh dấu và chia mảng thành hai mảng con bằng cách so sánh các phần tử trong cùng mảng với điểm đã đánh dấu. Lúc này, mảng 1 sẽ chia ra làm các phần tử nhỏ hơn hoặc bằng điểm đánh dấu, mảng 2 sẽ chia ra làm các phần tử lớn hơn điểm đánh dấu.
Tùy theo mỗi người là thuật ngữ "điểm đánh dấu" quan trọng trong Quick sort sẽ có những cách gọi khác nhau như pivot hoặc phần tử chốt. Trong bài viết này, pivot hay phần tử chốt cũng đều được hiểu là điểm đánh dấu.
Hiện nay Quick sort được ứng dụng để sắp xếp dữ liệu vì nó có hiệu suất cao và có thể xử lý được tệp dữ liệu lớn. Thuật toán này cũng được sử dụng trong việc tìm kiếm danh sách sắp xếp. Bằng cách sắp xếp danh sách trước khi thực hiện thao tác tìm kiếm, qua đó, thuật toán sẽ được thực hiện nhanh chóng hơn.
> Xem thêm: Regex là gì? Ứng dụng và cách viết Regex chi tiết nhất
Cách chọn pivot (phần tử chốt)
Quick sort áp dụng cách thức Divide and Conquer để sắp xếp dữ liệu. Vì vậy nên tốc độ sắp xếp dữ liệu phụ thuộc vào khá nhiều vào kĩ thuật chọn pivot. Tùy theo từng trường hợp cụ thể mà ta sẽ có những cách chọn như sau:
- Chọn phần tử đầu tiên trong mảng làm pivot.
- Chọn phần tử cuối cùng trong mảng làm pivot.
- Chọn phần tử có giá trị nằm giữa mảng làm pivot.
- Chọn random một phần tử bất kỳ trong mảng làm pivot. Tuy nhiên nên hạn chế cách này vì sẽ dễ làm chúng ta rơi vào các trường hợp đặc biệt nơi các vòng lặp vô hạn diễn ra.
Cách 1: Cách chọn phần tử đầu làm pivot
Để chọn phần tử đầu làm pivot, bạn thực hiện lệnh sau:
quickSort = (unSortedArr) => {
// nếu mảng không quá 1 phần tử thì mảng đó đã được sản xuất
if (unSortedArr.length < 2) return unSortedArr;
const pivot = unSortedArr[0]; //lấy phần tử đầu của mảng làm phần tử chốt
const leftArr = []; // mảng chứa phần tử nhỏ hơn pivot
const rightArr = []; // mảng chứa phần tử lớn hơn pivot
let currentItem; // phần tử đang được xét
// loop các phần tử còn lại trong mảng trừ phần tử chốt.
// Do pivot là ptu đầu tiên nên i sẽ bắt đầu từ 1
for (let i = 1; i < unSortedArr.length; i++) {
currentItem = unSortedArr[i];
if (currentItem < pivot) {
leftArr.push(currentItem);
} else {
rightArr.push(currentItem);
}
}
return […this.quickSort(leftArr), pivot, …this.quickSort(rightArr)];
}
Cách 2: Cách chọn phần tử cuối làm pivot
Đối với cách chọn phần tử chốt làm điểm đánh dấu, bạn áp dụng câu lệnh dưới đây nhé:
quickSort = (unSortedArr) => {
if (unSortedArr.length < 2) return unSortedArr;
const pivot = unSortedArr[unSortedArr.length – 1]; //phần tử cuối mảng làm chốt
const leftArr = [];
const rightArr = [];
let currentItem;
// Do pivot là ptu cuối nên length sẽ trừ đi 1
for (let i = 0; i < unSortedArr.length – 1; i++) {
currentItem = unSortedArr[i];
if (currentItem < pivot) {
leftArr.push(currentItem);
} else {
rightArr.push(currentItem);
}
}
return […this.quickSort(leftArr), pivot, …this.quickSort(rightArr)];
}
Cách 3: Cách chọn phần tử giữa làm pivot
Với cách áp dụng chọn phần tử giữa làm pivot, cách thức thực hiện như sau:
quickSort = (unSortedArr) => {
if (unSortedArr.length < 2) return unSortedArr;
// lấy phần tử giữa làm chốt
const pivotIndex = Math.floor(unSortedArr.length / 2);
const pivot = unSortedArr[pivotIndex];
const leftArr = [];
const rightArr = [];
let currentItem;
unSortedArr.splice(pivotIndex, 1); // loại bỏ ptu pivot trong mảng
for (let i = 0; i < unSortedArr.length; i++) {
currentItem = unSortedArr[i];
if (currentItem < pivot) {
leftArr.push(currentItem);
} else {
rightArr.push(currentItem);
}
}
return […this.quickSort(leftArr), pivot, …this.quickSort(rightArr)];
}
Quick sort có độ phức tạp như thế nào?
Độ phức tạp của thuật toán Quick Sort phụ thuộc rất nhiều vào cách chọn phần tử chốt (pivot) và cấu trúc dữ liệu ban đầu. Quick sort có công thức tính thời gian như sau:
T(n) = T(k) + T(n-k-1) + θ(n)
Trong đó:
- T(k) và T(n-k-1): Thời gian cho 2 cuộc gọi đệ quy.
- θ(n): Tiến trình phân vùng.
- k: Số phần tử nhỏ hơn phần tử chốt
Lưu ý: Thời gian của thuật toán Quick sort phụ thuộc vào mảng đầu và chiến lược chia trong mảng.
Từ công thức tính thời gian trong quick sort trên, chúng ta có thể suy ra được mức độ phức tạp của các trường hợp khi sử dụng quick sort. Cụ thể:
- Trường hợp tốt nhất: Khi mỗi lần phân hoạch chia mảng thành hai phần có kích thước gần bằng nhau, độ phức tạp của Quick Sort là O(n log n). Đây là trường hợp lý tưởng và thường xảy ra khi dữ liệu đầu vào phân bố ngẫu nhiên.
- Trường hợp trung bình: Trong hầu hết các trường hợp, độ phức tạp của Quick Sort cũng là O(n log n).
- Trường hợp xấu nhất: Khi mảng đã được sắp xếp hoặc gần như sắp xếp, và việc chọn pivot luôn là phần tử nhỏ nhất hoặc lớn nhất, độ phức tạp sẽ lên đến O(n^2). Điều này xảy ra vì mỗi lần phân hoạch chỉ tạo ra một phần tử con có kích thước n-1.
Ưu, nhược điểm của quick sort
Là một thuật toán được sử dụng phổ biến trong ngôn ngữ lập trình, Quick sort có những ưu và nhược điểm cụ thể.
Ưu điểm của Quick sort
Quick sort là thuật toán được sử dụng rất phổ biến bởi nó mang theo những ưu điểm nổi bật như sau:
- Quick sort là một trong những thuật toán sắp xếp và phân bố nhanh nhất, đặc biệt là khi áp dụng với những tệp dữ liệu lớn. Quick sort có độ phức tạp trung bình O(n log n) với tốc độ chạy nhanh dù cho đó là bộ dữ liệu lớn.
- Thuật toán quick sort có thiết kế đơn giản, dễ triển khai và cũng rất dễ hiểu. Việc này hỗ trợ quá trình cài đặt và sử dụng Quick sort nhanh hơn khi so với những thuật toán còn lại.
- Quick sort có khả năng tự sắp xếp trong chính nó, nghĩa là nó không cần dùng thêm mảng phụ để lưu trữ giá trị trung gian. Từ đó, Quick sort giúp hạn chế việc sử dụng bộ nhớ và gia tăng hiệu suất.
- Thuật toán này có thể tùy biến theo từng tình huống khác nhau cho phù hợp với dữ liệu thực tế bằng cách chọn pivot hoặc xử lý phần tử bị trùng lặp.
Nhược điểm của Quick sort
Dù có nhiều ưu điểm, Quick sort vẫn là thuật toán tồn tại hạn chế nhất định. Nhược điểm lớn nhất của Quick sort đó là trong trường hợp xấu nhất, khi mảng đã bị đảo ngược, thuật toán sẽ hoạt động chậm và hao tốn nhiều bộ nhớ hơn.
Vì thế, khi dùng Quick sort, bạn cần cân nhắc kết hợp thêm những thuật toán khác để đảm bảo được hiệu suất tối ưu nhất.
Minh họa thuật toán quick sort trong C++
Để hiểu rõ về thuật toán Quick sort và cách hoạt động của nó, hãy cùng LPTech phân tích qua ví dụ minh họa trong C++ sau đây. Các bước thực hiện bao gồm: Chọn phần tử chốt (Pivot) > Phân hoạch mảng (Partition) > Di chuyển chỉ số > Đặt pivot vào đúng vị trí > Gọi đệ quy
Cho một mã triển khai của Quick Sort như sau:
#include <bits/stdc++.h>
using namespace std;
int partition(vector<int>& arr, int low, int high) {
//Chọn pivot
int pivot = arr[high];
// Chỉ số của phần tử nhỏ hơn và chỉ ra vị trí đúng của pivot đã tìm thấy cho đến nay
int i = low - 1;
// Duyệt qua mảng arr từ low đến high và di chuyển tất cả các phần tử nhỏ hơn về phía bên trái. Các phần tử từ low đến i sẽ nhỏ hơn sau mỗi lần lặp
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
// Di chuyển pivot đến sau các phần tử nhỏ hơn và trả về vị trí của nó
swap(arr[i + 1], arr[high]);
return i + 1;
}
// Thực hiện hàm sắp xếp nhanh QuickSort
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
// pi là chỉ số trả về của pivot sau khi phân hoạch
int pi = partition(arr, low, high);
// Gọi đệ quy cho các phần tử nhỏ hơn và các phần tử lớn hơn hoặc bằng
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
vector<int> arr = {10, 7, 8, 9, 1, 5};
int n = arr.size();
quickSort(arr, 0, n - 1);
cout << "Sorted Array\n";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Đầu ra
Mảng được sắp xếp
1 5 7 8 9 10
Ứng dụng của quick sort
Quick Sort được sử dụng trong nhiều lĩnh vực của khoa học máy tính, từ các hệ thống cơ sở dữ liệu đến các thuật toán tìm kiếm và đồ họa.
Trong lĩnh vực thiết kế app và thiết kế website chuyên nghiệp, quick sort hỗ trợ lập trình viên rất nhiều trong các công việc như sắp xếp danh sách, tìm kiếm nhị phân, phân tích dữ liệu và các thuật toán khác. Cụ thể:
- Ứng dụng thương mại điện tử: Quick sort lúc này sẽ sắp xếp danh sách sản phẩm theo giá từ thấp đến cao hoặc ngược lại để người dùng dễ dàng tìm thấy sản phẩm phù hợp.
- Ứng dụng quản lý danh bạ: Quick sort sắp xếp danh bạ theo tên, số điện thoại hoặc địa chỉ để thuận tiện cho việc tìm kiếm.
- Ứng dụng bản đồ: Các điểm đánh dấu trên bản đồ được quick sort sắp xếp theo khoảng cách đến vị trí hiện tại của người dùng.
Bài viết trên đây đã mang đến những thông tin hữu ích về thuật toán sắp xếp Quick sort. Có thể nhận thấy được rằng, đây là thuật toán hữu ích và phổ biến được sử dụng trong ngôn ngữ lập trình C++. Hy vọng bài viết đã mang đến cho bạn những kiến thức cơ bản cần thiết về thuật toán Quick sort và phục vụ cho quá trình học tập, làm việc thật hiệu quả nhé!
