Trong JavaScript (phần nào có thể áp dụng ở nơi khác), nơi bạn không biết mã đang chạy đang triển khai đích nào, có cách nào để phát hiện nếu thuật toán sắp xếp cơ bản (của Array.sort) ổn định hay không, chỉ biết rằng sau the specification?Có phương pháp hộp đen nào để phát hiện xem thuật toán sắp xếp có ổn định không?
Tôi có thể tìm thấy 2 thử nghiệm trong webkit (1)(2), nhưng các thử nghiệm đó đáng tin cậy như thế nào? (Có thể kiểm tra này được thực hiện với một PCP?) Tôi đang tìm một giải pháp mà có thể là âm thanh toán học.
Đây là một vấn đề phức tạp, vì thuật toán sắp xếp nâng cao hơn có thể thay đổi thuật toán phụ tùy thuộc vào độ dài của mảng nguồn (như Timsort). Tôi đã nhầm lẫn vì mọi thử nghiệm tôi đã chạy cho thấy sắp xếp của Google Chrome ổn định, nhưng tất cả tài liệu tôi đã thấy đều cho biết rằng nó không ổn định (the source sẽ cho bạn biết lý do).
(Thông thường, tôi sử dụng this strategy để làm cho các loại của tôi ổn định, nó có nhỏ nhưng đôi khi đáng chú ý tác động hiệu suất)
Source code để phân loại trong việc triển khai khác nhau:
Bạn chỉ có thể thực hiện xác suất như vậy một cách xác thực: ví dụ: tôi có thể xác định thuật toán sắp xếp 'S' có đầu vào' I'. Thông thường, 'S' tạo ra công việc phân loại thực tế cho một số thuật toán ổn định' T', * nhưng * khi 'I' bằng một số giá trị đặc biệt' I'', nó sử dụng một loại không ổn định 'U'.Bạn sẽ không bao giờ chứng minh rằng 'S' là không ổn định trừ khi bạn may mắn ra và xảy ra để vượt qua' I'' như đầu vào. Thực tế hơn, có lẽ 'S' sử dụng các loại ổn định trừ khi' I' rất dài. Một lần nữa, bạn sẽ chỉ quan sát các loại không ổn định nếu bạn thử nghiệm trên đầu vào phù hợp dài. – apsillers
Nếu spec nói rằng nó không ổn định, điều đó không có nghĩa là bạn có thể mong đợi các mục để hoán đổi thứ tự khi bạn sắp xếp mảng, nhưng đúng hơn là bạn không thể dựa vào nó; không có lời hứa. Việc triển khai (hiện tại) diễn ra ổn định không có nghĩa là nó sẽ luôn luôn, hoặc cho tất cả các nền tảng mà Chrome chạy trên đó. – frozenkoi
Tôi đồng ý với @MarZab rằng đây là sự cố tạm dừng. Bạn có thể thấy một số sự chú ý nhiều hơn nếu bạn gắn thẻ nó '[computer-science]' và/hoặc '[computer-science-theory]'. – apsillers