Đánh giá thời gian quick sort năm 2024
Các thuật toán sắp xếp dữ liệu là một yếu tố quan trọng khá quan trọng trong lập trình, điển hình trong số đó là Quick Sort. Vậy Quick Sort là gì? Trong bài viết hôm nay, bạn hãy cùng Tino Group tìm hiểu về Quick Sort để xem cách thuật toán này triển khai và hoạt động như thế nào nhé! Show
Khái niệm Quick SortThuật toán Quick Sort (Sắp xếp nhanh) là một quy trình có hệ thống để sắp xếp các phần tử của một mảng. Giống như Merge Sort, QuickSort là một thuật toán sử dụng cách thức chia để trị (Divide and Conquer algorithm). Tên gọi “Quick Sort” ám chỉ thuật toán này có khả năng sắp xếp dữ liệu nhanh hơn nhiều so với bất kỳ thuật toán sắp xếp truyền thống nào khác. Tuy nhiên, Quick Sort không được ổn định vì thứ tự tương đối của các phần tử bằng nhau không được đảm bảo. Cách thức hoạt động của Quick SortThuật toán sẽ chọn ra một phần tử trong mảng để làm điểm đánh dấu gọi là pivot. Sau khi chọn được điểm đánh dấu, nó sẽ chia mảng đó thành hai mảng con bằng cách so sánh với pivot đã chọn. Một mảng sẽ bao gồm các phần tử nhỏ hơn hoặc bằng pivot và mảng còn lại luôn lớn hơn hoặc bằng pivot. Sau đó, quá trình này được lặp lại đủ số lần cho đến khi các mảng nhỏ có thể được sắp xếp một cách dễ dàng để tạo ra một tập dữ liệu được sắp xếp đầy đủ. Các nhiều phiên bản Quick Sort khác nhau chọn pivot theo những cách khác nhau. Tốc độ sắp xếp của thuật toán phải phụ thuộc vào việc lựa chọn pivot, có một số cách để chọn như sau:
Ứng dụng của thuật toán Quick SortQuick Sort cung cấp một cách tiếp cận nhanh chóng và có phương pháp để sắp xếp bất kỳ thứ gì. Sau đây là một số ứng dụng của Quick Sort
Độ phức tạp của Quick ShortKhi chọn một thuật toán sắp xếp, hiệu quả là một trong những yếu tố quan trọng nhất. Dưới đây là một số điểm hiệu quả của thuật toán Quicksort. Độ phức tạp về thời gian của Quick ShortTrong các trường hợp tốt nhất, trung bình và xấu nhất, thuật toán Quick Sort thực hiện với độ phức tạp O (n), O (n log n) và O (n ^ 2) tương ứng. Đây là một trong những thuật toán sắp xếp hiệu quả nhất khi nói đến độ phức tạp về thời gian. Độ phức tạp về không gian của Quick ShortĐộ phức tạp không gian trung bình của Quick Sort là O (log n) và độ phức tạp không gian trong trường hợp xấu nhất là O (n). Điều này ngang bằng với hầu hết các thuật toán sắp xếp phổ biến, nhưng bản chất của thuật toán đệ quy là chúng không tối ưu hóa việc sử dụng bộ nhớ. QUẢNG CÁO Tối ưu hóaVới bất kỳ thuật toán nào, thường có một số tối ưu hóa có thể được áp dụng cho các trường hợp khác. Để đảm bảo rằng không gian đã sử dụng được giới hạn ở O (log n), thuật toán có thể được thực hiện để đệ quy vào phía nhỏ hơn của phân vùng và cũng sử dụng đệ quy đuôi. Người ta cũng có thể triển khai một thuật toán sắp xếp kết hợp chuyển sang một thuật toán sắp xếp lặp đi lặp lại có thể hiệu quả hơn về thời gian cho các mảng nhỏ hơn. Thuật toán Quick Sort trong ngôn ngữ lập trình C++Mô tả thuật toánThuật toán sẽ có hai giai đoạn. Giai đoạn đầu là phân đoạn mảng (partition()) và giai đoạn sau là sắp xếp (quickSort()).
Code thuật toán Quick Sort trong C++Ở phần trên đã trình bài các bước viết thuật toán. Để chi tiết hơn, bạn hãy tham khảo các dòng code trong thuật toán dưới đây. Hàm partition()Hàm quicksort()Hàm swap()Ví dụ về Quick Sort trong mảngĐể minh họa cho hình ảnh ở trên, chúng ta hãy cùng làm một ví dụ áp dụng thuật toán sắp xếp nhanh (Quick Sort). Sắp xếp các phần tử trong mảng arr[] = {9, -3, 5, 2, 6, 8, -6, 1, 3} theo thứ tự tăng dần.
Kết quả ta được: Tại sao Quick Sort lại hiệu quả hơn Merge Sort?Về không gian phụ trợ: Quick Sort là một thuật toán sắp xếp tại chỗ trong khi Merge Sort phải sử dụng thêm không gian. Sắp xếp tại chỗ có nghĩa là không có dung lượng lưu trữ bổ sung nào được sử dụng để thực hiện sắp xếp (ngoại trừ ngăn xếp đệ quy). Merge Sort yêu cầu một mảng tạm thời để hợp nhất các mảng đã sắp xếp, vì vậy Quick Sort trở thành tùy chọn tốt hơn. Trường hợp xấu nhất: Trường hợp xấu nhất của Quick Sort là O (n2) có thể tránh được bằng cách sử dụng Quick Sort ngẫu nhiên. Lúc này sẽ có được trường hợp trung bình bằng cách chọn phần tử xoay ngẫu nhiên và cải thiện hiệu suất như Merge Sort Thân thiện với bộ nhớ cache: Quick Sort cũng là một thuật toán sắp xếp thân thiện với bộ nhớ cache vì thuật toán này có vị trí tham chiếu tốt khi được sử dụng cho các mảng. Tóm lại, Quick Sort là một thuật toán sắp xếp rất hữu ích trong nhiều trường hợp và được sử dụng phổ biến hiện nay. Bài viết trên đã cung cấp cho bạn một số thông tin liên quan đến Quick Sort, hy vọng bạn sẽ áp dụng thuật toán này hiệu quả để sắp xếp dữ liệu nhé! FAQs về Quick SortCó bao nhiêu loại thuật toán sắp xếp?Quick Sort là một loại thuật toán sắp xếp trong rất nhiều loại khác nhau, mỗi loại sẽ có những ưu điểm riêng. Các thuật toán sắp xếp phổ biến trong JavaScript gồm:
Quick Sort có phải là một thuật toán ổn định không?Quick Sort không phải là một thuật toán ổn định vì việc hoán đổi các phần tử được thực hiện theo vị trí của pivot (mà không xem xét vị trí ban đầu của chúng). Thuật toán sắp xếp được cho là ổn định nếu nó duy trì thứ tự tương đối của các bản ghi trong trường hợp các khóa bằng nhau. Quick Sort có phải là một thuật toán tại chỗ không?Quick Sort là một thuật toán tại chỗ, nghĩa là tất cả các số đều được sắp xếp trong chính mảng ban đầu. Tại sao nên sử dụng Quick Sort ngẫu nhiên?Đôi khi, việc chọn phần tử ngoài cùng bên phải có thể dẫn đến trường hợp xấu nhất. Trong những trường hợp như vậy, việc chọn một phần tử ngẫu nhiên làm trục xoay của bạn ở mỗi bước sẽ giảm xác suất dẫn đến hành vi trong trường hợp xấu nhất. Chúng ta sẽ có nhiều khả năng chọn các trục gần tâm của mảng hơn và khi điều này xảy ra, các nhánh đệ quy đồng đều hơn và do đó thuật toán kết thúc nhanh hơn rất nhiều. Độ phức tạp thời gian chạy dự kiến là O (n log n) vì các trục ngẫu nhiên đã chọn được cho là để tránh hành vi trong trường hợp xấu nhất. |