Hiểu về Sắp xếp nhanh qua JavaScript
Một vấn đề khi làm việc với sắp xếp hợp nhất là chúng cần tạo và lưu trữ rất nhiều mảng trong bộ nhớ với phần lớn là dữ liệu dư thừa. Nếu ta bị giới hạn về bộ nhớ, ta có thể sử dụng một sắp xếp nhanh để chạy nó “tại chỗ”, nghĩa là các thay đổi và kết quả đều xảy ra trực tiếp với những gì đang được sắp xếp, do đó tiết kiệm trên bộ nhớ.
Yêu cầu
Ta sẽ xem xét version đệ quy tiêu chuẩn, mặc dù bạn có thể thực hiện điều này lặp đi lặp lại, vì vậy việc hiểu cách hoạt động của đệ quy sẽ rất hữu ích, bạn có thể tìm hiểu thêm tại đây .
Ý tưởng
Sắp xếp nhanh chắc chắn là một trong những thuật toán kém trực quan, vì vậy đây là một cái nhìn tổng quan rất đơn giản.
Ta chọn một số, được gọi là pivot của ta , ta sẽ so sánh mọi số với khi ta lặp lại các mục của bạn . Mục đích là tổ chức lại mảng để nó được chia thành hai nửa, với mọi thứ trong mỗi nửa nhỏ hơn hoặc lớn hơn trục của ta . Khi trục ở vị trí cuối cùng, ta sẽ chuyển sang làm điều tương tự với một trục mới, với mọi trục được cố định tại chỗ cho đến khi mọi mục đã được làm trục ít nhất một lần.
Graphic / Animation nhờ VisuAlgo.net
Giống như sắp xếp hợp nhất, độ phức tạp trung bình là O (nlogn), vì vậy bạn muốn chọn loại nào tùy thuộc vào bạn.
Dữ liệu thực hành
Như mọi khi, đây là một mảng không được sắp xếp gồm 50 số ngẫu nhiên để chơi cùng. Tôi cũng khuyên bạn nên xem xét api hiệu suất của JavaScript để so sánh nó với các thuật toán khác và với các dữ liệu khác nhau.
const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2]; Trục
Đầu tiên, ta cần chức năng tiện ích xoay của ta . Có 4 phần chính của nó, swapper, vòng lặp, trục xoay và con trỏ của ta .
Con trỏ của ta chỉ là một trình giữ chỗ cho trục của ta . Mỗi khi vòng lặp của ta tiến triển, mỗi mục được so sánh với trục và nếu nó nhỏ hơn, nó sẽ được swap với con trỏ của ta . Mỗi khi ta làm điều này là đảm bảo rằng con trỏ đi trước mọi thứ nhỏ hơn trục và trước mọi thứ lớn hơn. Khi mọi thứ hoàn tất và mảng của ta được phân vùng, thì ta có thể gán trục xoay cho index của con trỏ làm vị trí cuối cùng của nó.
Swap của ta hoạt động bằng cách chỉ định lại các index của từng mục với index của nhau, không có gì quá điên rồ.
const pivot = (arr, start = 0, end = arr.length + 1) => { const swap = (list, a, b) => [list[a], list[b]] = [list[b], list[a]]; let pivot = arr[start], pointer = start; for (let i = start; i < arr.length; i++) { if (arr[i] < pivot ) { pointer++; swap(arr, pointer, i); } }; swap(arr, start, pointer); return pointer; } Sắp xếp nhanh chóng
Việc triển khai đồng thời khá đơn giản và hơi khó hiểu, vì xu hướng đệ quy. Ta sẽ sử dụng hàm pivot để lấy mục được sắp xếp đầu tiên từ mảng của ta . Như vậy, ta sẽ chạy đệ quy quickSort của quickSort để thực hiện quá trình tương tự trên nửa đầu của mảng được phân vùng, quá trình này sẽ lặp lại cho đến khi không còn gì để sắp xếp, sau đó thực hiện tương tự cho nửa còn lại. Khi cả hai được thực hiện xong, mảng được sắp xếp đầy đủ của ta có thể được trả về.
const quickSort = (arr, start = 0, end = arr.length) => { let pivotIndex = pivot(arr, start, end); if (start >= end) return arr; quickSort(arr, start, pivotIndex); quickSort(arr, pivotIndex + 1, end); return arr; }; console.log(quickSort(unsortedArr)); Kết luận
Sắp xếp nhanh chắc chắn là một trong những thuật toán sắp xếp khó nhất khiến tôi trăn trở. Giữa việc có 4 phần thay đổi và 2 ngăn xếp đệ quy, đây chắc chắn là điều mà bạn có thể không nên nhớ đến hoàn hảo và có thể cần đánh dấu để tham khảo sau.
Các tin liên quan
Hiểu bản đồ và thiết lập đối tượng trong JavaScript2020-02-12
Hiểu Hợp nhất Sắp xếp Thông qua JavaScript
2020-02-08
Tạo biểu mẫu tùy chỉnh bằng API dữ liệu biểu mẫu JavaScript
2020-02-06
Thuật toán sắp xếp cho người mới bắt đầu trong JavaScript: Bubble, Selection & Insertion Sort
2020-02-03
Tìm kiếm nhị phân tuyến tính Vs qua JavaScript
2020-01-29
Hiểu Đệ quy & Ghi nhớ qua JavaScript
2020-01-26
Đọc và xử lý tệp với API JavaScript FileReader
2020-01-23
Tìm hiểu ký hiệu Big O qua JavaScript
2020-01-20
Cách sử dụng API BroadcastChannel trong JavaScript
2020-01-13
Đa năng hóa chuỗi trong JavaScript bằng Simplur
2020-01-10
