Viết thuật toán sắp xếp nhanh (Quick Sort Algorithm) bằng JavaScript
Được đăng vào 17/03/2023 04:00 bởi Duy Nguyễn.
1 phút đọc
238 lượt xem
Trong hướng dẫn này, bạn sẽ học cách viết thuật toán sắp xếp nhanh (Quick Sort Algorithm) bằng JavaScript và khám phá các khái niệm chính đằng sau thuật toán.
🫤 Quick Sort là gì ?
Sắp xếp nhanh hay còn gọi là Quick Sort là một thuật toán sắp xếp được sử dụng rộng rãi giúp sắp xếp hiệu quả một mảng các phần tử bằng cách chia mảng đó thành các mảng con nhỏ hơn dựa trên phần tử trục đã chọn.
Trong bài viết này, chúng ta sẽ hướng dẫn cách viết thuật toán sắp xếp nhanh bằng JavaScript và khám phá các khái niệm chính đằng sau thuật toán.
Sắp xếp là một nhiệm vụ phổ biến trong lập trình máy tính và có nhiều thuật toán sắp xếp có sẵn có thể được sử dụng theo những cách khác nhau. Một trong những thuật toán sắp xếp phổ biến và hiệu quả nhất là sắp xếp nhanh.
Sắp xếp nhanh là một thuật toán chia để trị giúp sắp xếp một mảng bằng cách chọn một phần tử trục và 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 trục và mảng còn lại chứa các phần tử lớn hơn trục. Hai mảng con sau đó được sắp xếp đệ quy cho đến khi toàn bộ mảng được sắp xếp.
Lưu ý: Trong thuật toán sắp xếp nhanh, trục là phần tử được chọn từ mảng được dùng làm điểm tham chiếu để phân vùng mảng thành hai mảng con nhỏ hơn.
Trục thường được chọn làm phần tử đầu tiên hoặc cuối cùng của mảng, mặc dù có các phương pháp khác để chọn trục.
🌟 Triển khai thuật toán sắp xếp nhanh với Javascript
Trước khi bắt đầu triển khai thuật toán sắp xếp nhanh, trước tiên chúng ta hãy hiểu các khái niệm cơ bản của nó. Như chúng tôi đã đề cập trước đó, sắp xếp nhanh là thuật toán chia để trị. Thuật toán có thể được chia thành ba bước chính:
- Chọn một phần tử trục từ mảng.
- Phân vùng mảng thành hai mảng con, một mảng chứa các phần tử nhỏ hơn trục và mảng còn lại chứa các phần tử lớn hơn trục.
- Áp dụng đệ quy thuật toán sắp xếp nhanh cho hai mảng con cho đến khi toàn bộ mảng được sắp xếp.
Với sự hiểu biết này, hãy chuyển sang triển khai thuật toán trong JavaScript.
const quickSort = (arr) => {
if (arr.length <= 1) {
return arr;
}
let pivot = arr[0];
let leftArr = [];
let rightArr = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
leftArr.push(arr[i]);
} else {
rightArr.push(arr[i]);
}
}
return [...quickSort(leftArr), pivot, ...quickSort(rightArr)];
};
Chúng ta hãy từng bước thực hiện điều này. Đầu tiên ta tạo hàm xử lý thao tác sắp xếp nhanh và nắm giữ thuật toán.
Bước 1: Chọn một phần tử Pivot
Đầu tiên ta hãy chọn một dữ liệu từ mảng và lưu phần tử pivot. Phần tử này giúp chúng ta có thể biết vị trí để sử dụng ở bước sau. Trong đoạn code này, tôi sẽ sử dụng phần tử đầu tiên của mảng.
const pivot = arr[0];
Bước 2: Phân tách Mảng
Sau khi chọn phần tử pivot, bước tiếp theo là phân tách mảng ra thành 2 mảng con. Trong đó, chúng ta dùng phần tử pivot để chia thành 2 mảng. Một mảng sẽ chứa phần tử nhỏ hơn pivot và một mảng chứa những phần tử lớn hơn pivot.
Chúng ta có thể thực hiện được điều này bằng cách dùng vòng lặp để so sánh từng phần tử với pivot và thêm nó vào mảng thích hợp.
let leftArr = [];
let rightArr = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
leftArr.push(arr[i]);
} else {
rightArr.push(arr[i]);
}
}
Bước 3: Sắp xếp đệ quy cho Mảng con
Tiếp theo, ta sẽ áp dụng đệ quy thuật toán Sắp xếp nhanh cho 2 Mảng con cho đến khi toàn bộ mảng đã được sắp xếp xong. Sau đó, ta sử dụng ... hay còn gọi la Improved array manipulation trong Javascript để kết hợp hai mảng con sau khi được sắp xếp thành công theo thứ tự leftArr, pivot, rightArr.
return [...quickSort(leftArr), pivot, ...quickSort(rightArr)];
Nhưng để điều này không tiếp tục lặp đi lặp lại, phải có một trường hợp cơ sở để dừng đệ quy.
Bước 4: Xác định trường hợp cơ sở
Bước cuối cùng là xác định trường hợp cơ sở (hay là lệnh dừng) cho hàm đệ quy. Điều này được chạy khi mảng có độ dài 0 hoặc 1, vì một mảng có một phần tử đã được coi là đã sắp xếp thành công
if (arr.length <= 1) {
return arr;
}
👌 Kiểm tra thuật toán
Để kiểm tra thuật toán sắp xếp nhanh, chúng ta có thể tạo một mảng các số ngẫu nhiên và truyền vào hàm quickSort().
Đây là một ví dụ:
let myArray = [3, 7, 2, 5, 1, 4, 6, 8];
console.log(quicksort(myArray)); // Output: [1,2,3,4,5,6,7,8]
Code mẫu mà mình trên Replit.com
✨ Kết thúc
Trong bài viết này, bạn đã biết ý nghĩa của thuật toán sắp xếp nhanh và cách bạn có thể tạo thuật toán này bằng Javascript. Chúc các bạn thành công.
Tags: codealgorithmquick-sortjavascriptNhững Bài Viết Liên Quan: