NỘI DUNG BÀI VIẾT
Trong bài viết này, các bạn sẽ tìm hiểu tổng quan về sắp xếp trong JavaScript, các thuật toán sắp xếp và hàm sort() trong JavaScript.
Sắp xếp là gì?
Sắp xếp là 1 bài toán cơ bản và đơn giản nhất đối với bất cứ ai khi bắt đầu học lập trình. Nó chắc chắn cũng chẳng xa lạ gì, vì trong thực tế chúng ta đã gặp những bài toán tương tự như vậy. Ví dụ như sắp xếp danh sách học sinh, sắp xếp sách, sắp xếp bộ bài,… Vậy thì bài toán sắp xếp là gì?
Bài toán sắp xếp là gì?
Bài toán sắp xếp là sắp xếp lại các phần tử của một danh sách theo chiều tăng dần hoặc giảm dần theo một tiêu chí nào đó của phần tử trong danh sách.
Ví dụ như sắp xếp danh sách học sinh theo điểm trung bình từ cao đến thấp, sắp xếp những quyển sách theo năm xuất bản, sắp xếp những lá bài trong bộ bài từ 1 đến K,…
Tóm tắt bài toán sắp xếp tăng dần:
Input: Một mảng n phần tử A = (a_1, a_2, a_3, …, a_na1,a2,a3,…,an)
Output: Một hoán vị của A là mảng A’ = (a’_1, a’_2, a’_3, …, a’_na1′,a2′,a3′,…,an′), thỏa mãn điều kiện: a’_1 <= a’_2 <= a’_3 <= … <= a’_na1′<=a2′<=a3′<=…<=an′
Phép toán cơ bản trong bài toán sắp xếp
Có 2 phép toán cơ bản cho bài toán sắp xếp:
1. Phép toán đổi chỗ:
Là phép toán đảo giá trị của 2 biến.
function swap(a, b) {
var temp = a;
a = b;
b = temp;
}
Code language: JavaScript (javascript)2. Phép toán so sánh:
Trả về true nếu a > b và trả về false cho trường hợp ngược lại.
function compare(a, b) {
if (a > b) {
return true;
} else {
return false;
}
}
Code language: JavaScript (javascript)Đây là 2 phép toán con thường được sử dụng trong các bài toán sắp xếp. Giống như phép
+-trong số học vậy.
Sắp xếp trong JavaScript
1. Dùng thuật toán sắp xếp
Từ trước đến nay, có rất nhiều nhà khoa học đã nghiên cứu và để lại cho chúng ta rất nhiều thuật toán sắp xếp. Các thuật toán này được sinh ra để giải quyết các vấn đề tồn đọng, cấp thiết.
Việc của chúng ta là tiếp nhận, học và hiểu cách thuật toán cài đặt và chạy như thế nào. Rồi sau đó, ứng dụng vào các bài toán cụ thể để có tư duy suy luận khi nào nên sử dụng chúng, so sánh giữa các thuật toán sắp xếp, tại sao dùng thuật toán này mà không phải thuật toán kia,…
Một số thuật toán sắp xếp phổ biến bất cứ ai học lập trình đều phải biết về chúng:
- Sắp xếp nổi bọt (Bubble Sort)
- Sắp xếp chọn (Selection Sort)
- Sắp xếp chèn (Insertion Sort)
- Sắp xếp trộn (Merge Sort)
- Sắp xếp nhanh (Quick Sort)
- Sắp xếp đếm phân phối (Counting Sort)
- Ngoài ra, còn rất nhiều thuật toán sắp xếp khác…
2. Sử dụng hàm sort() trong JavaScript
Khi ta muốn sắp xếp trong JavaScript, ta có thể sử dụng hàm sort() được cài đặt sẵn. Tuy nhiên, khác với một số ngôn ngữ lập trình khác, hàm sort() trong JavaScript sẽ có điểm khác biệt và chúng ta cần lưu ý trước khi sử dụng.
Sort is not necessarily stable
const myArray = [33, 2, 98, 25, 4];
myArray.sort(); // [2, 25, 33, 4, 98]Code language: JavaScript (javascript)Ủa, gì kì vậy? Tại sao 25 -> 33 -> 4?
Phương thức sort sẽ sắp xếp các phần tử trong một mảng theo bảng chữ cái alphabet hoặc chữ số với thứ tự tăng dần hoặc giảm dần.
Mặc định các phần tử sẽ được sắp xếp theo bảng chữ cái với thứ tự tăng dần. Điều này khiến phương thức sort sẽ sắp xếp các chuỗi rất chính xác, tuy nhiên khi sắp xếp các số sẽ không được chính xác(ví dụ 33 và 4 thì 4 sẽ lớn hơn 33 vì 4 > 3).
const numbers = [80, 9]
numbers.sort() // [80, 9]
const strings = ['80', '9']
strings.sort() // ['80', '9']Code language: JavaScript (javascript)Như vậy thì viết như thế này cũng hoàn toàn hợp lệ.
const emojis = ["😍","😂","😰"]
emojis.sort() // ["😂", "😍", "😰"]
const wtfJavaScript = [390, "😂", 1, "2325"]
wtfJavaScript.sort() // [1, "2325", 390, "😂"]Code language: JavaScript (javascript)Đúng là đứa con của trời đánh!
Muốn sort mảng số thì phải làm sao?
Bạn có thể khắc phục điều này bằng việc truyền tham số là một mảng so sánh:
- Nếu giá trị trả về của hàm
compareFunction(a,b)< 0, giá trị a sẽ đứng trước b - Nếu giá trị trả về = 0, a và b bằng nhau
- Giá trị trả về > 0, a đứng sau b
const myArray = [33, 2, 98, 25, 4]
myArray.sort((a, b) => a - b) // [2, 4, 25, 33, 98]Code language: JavaScript (javascript)Kết luận
ECMAScript không đưa ra chuẩn mực nào về thuật toán cho cách sort, nghĩa là JavaScript engine muốn áp dụng thuật toán nào thì tùy nó, Google’s V8 (Javascript Engine của Chrome) và NodeJS sử dụng thuật toán Quick sort và kết quả thì không hẳn là chính xác 100%.
Do đó nên nhớ là sort trên những trình duyệt khác nhau cũng có khả năng cho kết quả khác nhau nếu nó dùng khác Javascript Engine.
Và lúc đó, việc các bạn tự cài đặt một hàm sort sử dụng các thuật toán nói ở trên thì chắc chắn đưa ra kết quả theo ý muốn của bạn.
Các bạn có thể tham khảo các bài viết hay về thuật toán sắp xếp trong JavaScript tại đây.
Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.
