Sắp xếp danh sách trong Prolog

Question

Prolog có cách xử lý độc đáo mọi thứ, đặc biệt là khi thực tế mọi thao tác đều liên quan đến đệ quy loại này hay cách khác.

Một trong những ví dụ cổ điển mà mọi ngôn ngữ có là sắp xếp danh sách các số nguyên thành thứ tự tăng dần.

Cách tối ưu (không sử dụng quá nhiều biến vị ngữ được tích hợp, loại trừ vị từ sắp xếp/2) để sắp xếp danh sách số nguyên ngẫu nhiên?

Answer 1

Trang web Lập trình Prolog của Roman Barták cung cấp examples of different sort algorithms, kết thúc bằng một quicksort được tối ưu hóa.

quick_sort2(List,Sorted):-q_sort(List,[],Sorted). 
q_sort([],Acc,Acc). 
q_sort([H|T],Acc,Sorted):- 
    pivoting(H,T,L1,L2), 
    q_sort(L1,Acc,Sorted1),q_sort(L2,[H|Sorted1],Sorted) 

Answer 2

Theo như tôi biết thuật toán sắp xếp tốt nhất được viết trực tiếp bằng Prolog, không tham chiếu đến bất kỳ cách sử dụng tích hợp đặc biệt nào đó.

Tối ưu hóa thường xuyên là bắt đầu hợp nhất không với danh sách độ dài 1 nhưng với các phân đoạn đã được sắp xếp.

Đó là, để sắp xếp danh sách [4,5,3,6,2,7,1,2], danh sách [4,5], [3,6], [2,7], [1,2] sẽ được sáp nhập.

Điều này có thể được tối ưu hóa hơn nữa bằng cách lắp ráp các danh sách được sắp xếp không chỉ theo hướng tăng dần mà còn theo hướng khác. Đối với ví dụ trên, điều này có nghĩa là phân đoạn được sắp xếp được tập hợp như sau:

[4,5|_] 
[3,4,5|_] 
[3,4,5,6|_] 
... 

Lưu ý rằng trong Prolog, bạn có thể mở rộng danh sách cả đầu và cuối.

Do đó, chúng tôi chỉ hợp nhất [1,2,3,4,5,6,7] và [2].

Hệ thống hiện tại sử dụng triển khai ban đầu (~ 1984) của Richard O'Keefe là Ciao-Prolog trong ciao-1.15/lib/sort.pl.