Sắp xếp Mọi thứ: Hướng dẫn Toàn diện về Sắp xếp Nhanh trong JavaScript

Tram Ho

Bạn đã bao giờ thấy mình có một đống đồ cần được sắp xếp, nhưng không biết bắt đầu từ đâu? Các thuật toán sắp xếp, chẳng hạn như Sắp xếp nhanh, có thể giúp chúng ta sắp xếp mớ bòng bong hỗn độn đó thành một sự sắp xếp ngăn nắp và có trật tự. Trong bài viết này, chúng ta sẽ đi sâu vào Sắp xếp Nhanh và cách nó hoạt động trong JavaScript, cũng như khám phá một số ví dụ thực tế về nơi có thể sử dụng nó.

Sắp xếp nhanh là gì?

Quick Sort là một thuật toán sắp xếp hiệu quả hoạt động bằng cách chọn một phần tử “trục” từ một mảng và phân vùng các phần tử khác thành hai mảng con tùy theo việc chúng nhỏ hơn hay lớn hơn trục. Sau đó, nó lặp lại quá trình này cho từng mảng con cho đến khi tất cả các phần tử được sắp xếp.

Đây là mã giả cơ bản cho Quick Sort:

Phần tử trục thường được chọn làm phần tử ở giữa của mảng, nhưng nó cũng có thể được chọn ngẫu nhiên hoặc dựa trên các tiêu chí khác. Điều quan trọng là chọn một trục sẽ chia mảng thành hai mảng con tương đối bằng nhau, giúp đảm bảo rằng Quick Sort chạy hiệu quả.

Cách sắp xếp nhanh hoạt động trong thực tế

Để hiểu rõ hơn về cách Quick Sort hoạt động, hãy xem qua một ví dụ sử dụng mã giả ở trên.

Giả sử chúng ta có một mảng các số nguyên sau đây mà chúng ta muốn sắp xếp theo thứ tự tăng dần:

Điều đầu tiên chúng ta làm là kiểm tra trường hợp cơ sở: nếu mảng có ít hơn 2 phần tử, hãy trả về nó (đã được sắp xếp). Vì mảng của chúng tôi có nhiều hơn 1 phần tử, chúng tôi tiến hành bước tiếp theo và chọn một phần tử trục. Trong trường hợp này, chúng tôi sẽ chọn phần tử ở giữa, là 5.

Tiếp theo, chúng tôi tạo hai mảng trống, leftright và phân chia phần còn lại của các phần tử thành các mảng này dựa trên việc chúng nhỏ hơn hay lớn hơn trục. Mảng bên trái của chúng ta sẽ chứa các phần tử nhỏ hơn 5 và mảng bên phải của chúng ta sẽ chứa các phần tử lớn hơn 5.

Bây giờ, chúng tôi thực hiện một cuộc gọi đệ quy trên các mảng con leftright , sử dụng cùng một thuật toán Sắp xếp Nhanh. Điều này sẽ lặp lại cho đến khi chúng ta đạt đến trường hợp cơ bản có một mảng có ít hơn 2 phần tử, tại thời điểm đó, mảng sẽ được trả về dưới dạng đã sắp xếp.

Đây là cách gọi đệ quy đối với mảng ví dụ của chúng ta:

Cuối cùng, chúng tôi nối các mảng con đã sắp xếp và phần tử trục để có được mảng được sắp xếp đầy đủ của chúng tôi:

Ví dụ

Bây giờ chúng ta đã hiểu rõ hơn về cách Quick Sort hoạt động, hãy khám phá một số ví dụ về nơi có thể sử dụng tính năng này.

Sắp xếp danh sách tên theo thứ tự bảng chữ cái:

Sắp xếp một mảng các đối tượng theo một thuộc tính cụ thể:

Sắp xếp danh sách các số nguyên theo thứ tự giảm dần:

Sắp xếp danh sách các ngày theo thứ tự thời gian:

Sắp xếp danh sách sản phẩm theo giá:

Khi nào nên sử dụng Sắp xếp nhanh

Quick Sort là thuật toán sắp xếp hiệu quả cao với độ phức tạp thời gian trung bình là O(n * log(n)) . Điều này có nghĩa là nó hoạt động tốt ngay cả với các tập dữ liệu lớn, làm cho nó trở thành một lựa chọn tốt để sắp xếp các mảng hoặc danh sách lớn.

Tuy nhiên, điều đáng chú ý là Quick Sort không phải là một thuật toán sắp xếp ổn định, có nghĩa là thuật toán này có thể không bảo toàn thứ tự tương đối của các phần tử được so sánh là bằng nhau. Nếu tính ổn định là quan trọng đối với trường hợp sử dụng của bạn, thì bạn có thể cân nhắc sử dụng một thuật toán sắp xếp khác, chẳng hạn như Sắp xếp hợp nhất.

Nhìn chung, Quick Sort là một công cụ mạnh mẽ để sắp xếp các mảng và danh sách trong JavaScript và nó có thể là một phần bổ sung hữu ích cho bộ công cụ của bạn với tư cách là một lập trình viên. Cho dù bạn đang sắp xếp tên, ngày tháng hoặc đối tượng theo một thuộc tính cụ thể, Quick Sort có thể giúp bạn đưa dữ liệu của mình vào trạng thái có tổ chức và dễ quản lý hơn.

Phần kết luận

Sắp xếp nhanh là thuật toán sắp xếp nhanh và hiệu quả có thể được sử dụng để sắp xếp dữ liệu trong JavaScript. Nó hoạt động bằng cách chọn một phần tử trục và phân vùng các phần tử còn lại thành hai mảng con dựa trên việc chúng nhỏ hơn hay lớn hơn trục. Sau đó, nó lặp lại quá trình này cho từng mảng con cho đến khi tất cả các phần tử được sắp xếp. Sắp xếp nhanh có độ phức tạp về thời gian trung bình là O(n * log(n)) và có thể là một lựa chọn tốt để sắp xếp các tập dữ liệu lớn. Tuy nhiên, nó không phải là thuật toán sắp xếp ổn định nên có thể không bảo toàn thứ tự tương đối của các phần tử được so sánh bằng nhau. Sắp xếp Nhanh có thể được sử dụng trong nhiều tình huống trong thế giới thực, chẳng hạn như sắp xếp tên, ngày hoặc đối tượng theo một thuộc tính cụ thể. Cho dù bạn đang muốn sắp xếp dữ liệu của mình hay chỉ đơn giản là muốn cải thiện các kỹ năng về thuật toán của mình, Quick Sort là một công cụ có giá trị cần có trong bộ công cụ lập trình của bạn.

Vì vậy, lần tới khi bạn cần sắp xếp một mảng trong mã JavaScript của mình, hãy cân nhắc thử Sắp xếp nhanh.

Như mọi khi, tôi hy vọng bạn thích bài viết này và học được điều gì đó mới. Xin cảm ơn và hẹn gặp lại các bạn trong những bài viết tiếp theo!

Nếu các bạn thích bài viết này thì hãy cho mình 1 like và subscribe để ủng hộ mình nhé. Cảm ơn bạn.

Giới thiệu

Chia sẻ bài viết ngay

Nguồn bài viết : Viblo