So sánh
Hoán đổi
Phân hoạch

  • Phần đang phân hoạch
  • Chốt
  • Đang so sánh
  • Vừa hoán đổi
  • Đã đúng chỗ

Tìm hiểu thêm về sắp xếp nhanh

Sắp xếp nhanh

Sắp xếp nhanh chọn một chốt, chuyển mọi giá trị nhỏ hơn lên trước nó và mọi giá trị khác ra sau nó, rồi sắp xếp hai bên theo cùng cách. Sau mỗi lần phân hoạch, chốt nằm ở vị trí cuối cùng của nó. Chọn cách lấy chốt, phát quá trình sắp xếp ở tốc độ bất kỳ hoặc đi từng phép so sánh, và xem vì sao một chốt tồi trên danh sách đã sắp xếp khiến sắp xếp nhanh chạy chậm. Nhấn Phát để xem quá trình sắp xếp, hoặc Bước và Lùi để đi từng phép so sánh. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Các ô đếm số phép so sánh, hoán đổi và phân hoạch. Chọn số cột, thứ tự ban đầu, hoặc tự nhập các số, và cách chọn chốt. Khi bảng được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.

Cách nó hoạt động

  1. Chọn số cột và thứ tự ban đầu: ngẫu nhiên, gần như đã sắp xếp, đảo ngược, hoặc ít giá trị khác nhau. Hoặc tự nhập các số.
  2. Nhấn Phát, hoặc dùng Bước và Lùi để đi từng phép so sánh. Kéo thanh trượt bước để nhảy đến bất kỳ đâu trong quá trình sắp xếp.
  3. Chọn quy tắc chọn chốt: giá trị cuối, giá trị giữa, giá trị ngẫu nhiên hoặc trung vị của ba. Thử từng cách trên danh sách đã sắp xếp.

Cách sắp xếp nhanh hoạt động

Chọn một giá trị của phần cần sắp xếp làm chốt và chuyển nó về cuối. Duyệt các giá trị còn lại từ trái sang phải; mỗi giá trị nhỏ hơn chốt được hoán đổi vào phần bên trái, phần này lớn dần từ đầu. Rồi hoán đổi chốt vào ngay sau phần bên trái. Mọi giá trị trước nó giờ đều nhỏ hơn và không giá trị nào sau nó nhỏ hơn, nên chốt đã ở vị trí cuối cùng. Sắp xếp phần trước và phần sau nó theo cùng cách, cho đến khi mỗi phần chỉ còn một giá trị.

Vì sao chốt quan trọng

Khi chốt rơi gần giữa, mỗi lần phân hoạch chia đôi bài toán, và số phép so sánh tăng như n log n: với 40 giá trị ngẫu nhiên, khoảng 190. Khi chốt là giá trị nhỏ nhất hoặc lớn nhất, một bên rỗng còn bên kia chứa mọi giá trị khác. Khi lấy giá trị cuối làm chốt, điều đó xảy ra ở mọi bước trên danh sách đã sắp xếp hoặc đảo ngược, và cần n(n − 1)/2 phép so sánh, tức 780 với 40 giá trị. Chốt ngẫu nhiên hoặc trung vị của giá trị đầu, giữa và cuối tránh được điều đó trong thực tế.

Câu hỏi thường gặp

Sắp xếp nhanh hoạt động thế nào?

Thuật toán chọn một chốt, phân hoạch danh sách để các giá trị nhỏ hơn đứng trước chốt và phần còn lại đứng sau, rồi sắp xếp hai bên bằng sắp xếp nhanh. Sau mỗi lần phân hoạch, chốt đã ở vị trí cuối cùng.

Vì sao sắp xếp nhanh chậm trên danh sách đã sắp xếp?

Khi lấy giá trị đầu hoặc cuối làm chốt, danh sách đã sắp xếp luôn cho chốt là giá trị nhỏ nhất hoặc lớn nhất. Khi đó một bên của phân hoạch rỗng, nên mỗi lần phân hoạch chỉ loại được một giá trị, và cần n(n − 1)/2 phép so sánh. Chốt ngẫu nhiên hoặc trung vị của ba khắc phục điều này trong thực tế.

Sắp xếp nhanh có nhanh hơn sắp xếp trộn không?

Thường là có, trong thực tế: nó sắp xếp tại chỗ, không cần bộ đệm, và vòng lặp trong rất đơn giản. Trung bình nó thực hiện nhiều phép so sánh hơn sắp xếp trộn một chút, và trường hợp xấu nhất là n², trong khi sắp xếp trộn luôn là n log n. Các hàm sắp xếp trong thư viện như introsort bắt đầu bằng sắp xếp nhanh và chuyển sang sắp xếp vun đống nếu các lần chia quá lệch.

Sắp xếp nhanh có ổn định không?

Không. Phân hoạch hoán đổi các giá trị qua khoảng cách xa, nên các giá trị bằng nhau có thể đổi thứ tự.

Các số của tôi có bị gửi đi đâu không?

Không. Việc sắp xếp chạy trong trình duyệt của bạn, và các cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Tới trình chỉnh sửa