Data Structure & Algorithm - Sort Algorithms - Quick Sort
Quick Sort là gì?
Quick Sort là một thuật toán sắp xếp hiệu quả, dựa trên phương pháp "chia để trị". Thuật toán này hoạt động bằng cách chọn một phần tử, gọi là "pivot", từ mảng và phân chia các phần tử khác thành hai mảng con, tùy thuộc vào việc chúng có nhỏ hơn hay lớn hơn pivot hay không. Sau đó, Quick Sort gọi lại chính nó một cách đệ quy để sắp xếp hai mảng con đó.
Quy trình của Quick Sort bao gồm các bước sau:
- B1: Chọn một phần tử, gọi là "pivot", từ mảng.
- B2: Phân chia mảng thành hai mảng con, một mảng chứa các phần tử nhỏ hơn pivot và một mảng chứa các phần tử lớn hơn pivot.
- B3: Gọi lại Quick Sort đệ quy cho hai mảng con để sắp xếp chúng 4.
Quick Sort có những ưu điểm và nhược điểm riêng:
Ưu điểm:
- Hiệu quả: Quick Sort là một thuật toán sắp xếp hiệu quả, nó hoạt động tốt với các tập dữ liệu lớn.
- Có độ phức tạp thời gian trung bình là O(n log n), trong khi trong trường hợp tồi tệ nhất, độ phức tạp thời gian là O(n^2)
Nhược điểm:
- Không ổn định: Quick Sort không phải là một thuật toán sắp xếp ổn định, nghĩa là nó có thể thay đổi thứ tự của các phần tử có giá trị bằng nhau.
- Lựa chọn pivot kém: Nếu pivot được chọn sai, Quick Sort có thể có độ phức tạp thời gian tồi tệ là O(n^2). Tuy nhiên, có nhiều biến thể của Quick Sort đã giải quyết vấn đề này
Quick Sort hoạt động như thế nào?
Giả sử chúng ta có một mảng sau: 9, 7, 5, 11, 12, 2, 14, 3, 10, 6
Bước 1: Chọn một phần tử, gọi là "pivot". Trong ví dụ này, chúng ta sẽ chọn phần tử cuối cùng của mảng, 6, làm pivot.
Bước 2: Phân chia mảng thành hai mảng con, một mảng chứa các phần tử nhỏ hơn pivot và một mảng chứa các phần tử lớn hơn pivot.
- Mảng con 1:
9, 7, 5, 2, 3, 6(phần tử nhỏ hơn pivot) - Mảng con 2:
11, 12, 14, 10(phần tử lớn hơn pivot)
Bước 3: Gọi lại Quick Sort đệ quy cho hai mảng con để sắp xếp chúng.
- Sắp xếp mảng con 1:
2, 3, 5, 6, 7, 9 - Sắp xếp mảng con 2:
10, 11, 12, 14
Bước 4: Ghép các mảng đã được sắp xếp lại với nhau: 2, 3, 5, 6, 7, 9, 10, 11, 12, 14
Vậy, mảng ban đầu 9, 7, 5, 11, 12, 2, 14, 3, 10, 6 đã được sắp xếp thành 2, 3, 5, 6, 7, 9, 10, 11, 12, 14
Cách cài đặt Quick Sort
function quickSort(arr, left = 0, right = arr.length - 1) {
const index = partition(arr, left, right);
if(left < index - 1) {
quickSort(arr, left, index - 1);
}
if(index < right) {
quickSort(arr, index, right);
}
return arr;
}
function partition(arr, left, right) {
const pivot = arr[Math.floor((right + left) / 2)];
while(left <= right) {
while(arr[left] < pivot) {
left++;
}
while(arr[right] > pivot) {
right--;
}
if (left <= right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}
return left;
}
Ứng dụng của Quick Sort
Thuật toán Quick Sort có nhiều ứng dụng trong các lĩnh vực khác nhau. Dưới đây là một số ví dụ:
- Commercial Computing: Quick Sort được sử dụng rộng rãi trong các tổ chức chính phủ và cá nhân khác để sắp xếp các dữ liệu như tệp theo tên/ngày/giá, sắp xếp sinh viên theo số lớp, sắp xếp hồ sơ tài khoản theo ID đã cho, v.v.
- Information Searching: Quick Sort cũng được sử dụng rộng rãi trong việc tìm kiếm thông tin và là thuật toán sắp xếp nhanh nhất, do đó nó thường được sử dụng như một cách tìm kiếm hiệu quả hơn.
- Operational Research and Event-Driven Simulation: Quick Sort cũng được sử dụng trong nghiên cứu kinh doanh và mô phỏng dựa trên sự kiện.
- Numerical Computations and Scientific Research: Trong các tính toán số học và nghiên cứu khoa học, nhiều thuật toán được phát triển hiệu quả sử dụng Quick Sort để sắp xếp.
- Separate Kth Smallest or Largest Elements: Các biến thể của Quick Sort được sử dụng để phân chia các phần tử thứ K nhỏ hoặc lớn nhất.
- Primitive Type Methods: Quick Sort cũng được sử dụng để triển khai các phương thức của các kiểu dữ liệu cơ bản
- Sorted Data Search: Khi dữ liệu được sắp xếp, việc tìm kiếm thông tin trở nên dễ dàng và hiệu quả
Nguồn tham khảo
All rights reserved
