时间戳

首页 > 解决方案 > 如何快速排序序言中的列表列表？

sorting - 如何快速排序序言中的列表列表？

问题描述

我正在尝试在 Prolog 中使用列表列表实现快速排序，使用第 4 个元素作为键，但它不像我所做的那样工作。

例子：

?- qsort( [ [ a,b,c,5 ], [ d,e,f,10 ], [ g,h,i,5 ], [ j,k,l,1 ], [ m,n,o,25 ] ], Sort ).

预期结果：

[ [ j,k,l,1 ], [ a,b,c,5 ], [ g,h,i,5 ], [ d,e,f,10 ], [ m,n,o,25 ] ]

我得到的答案（我需要修正括号）：

Sort = [j, k, l, 1, [g, h, i, 5], [a, b, c, 5], [d, e, f, 10], m, n, o, 25]

这是目前最接近的方法：

last([Y],Y).
last([_|Xs],Y) :- last(Xs,Y).

qsort([],[]):- !.
qsort([X], [X]).
qsort([Head|Tail],Sorted):-
  last(Head,Pivot),
  separation(Pivot,Tail,Lesser,Greater),
  qsort(Lesser,LesserSorted),
  qsort(Greater,GreaterSorted),
  append(LesserSorted,[Head|GreaterSorted],Sorted).

separation(_,[],[],[]).
separation(Pivot,[X|T],[X|Lesser],Greater):-
  last(X,R), R =< Pivot, 
  separation(Pivot,T,Lesser,Greater).
separation(Pivot,[X|T],Lesser,[X|Greater]):-
  last(X,R), R > Pivot, 
  separation(Pivot,T,Lesser,Greater).

标签： sortingprologquicksortnested-lists

解决方案

这不是“枢轴”的意思。您的意思是使用列表的第 4 个元素作为比较键对列表进行排序。“枢轴”是您选择用作分隔符的元素，用于分区。您的元素恰好是 4 字段元组（巧合地编码为列表）。因此，您选择列表中的第一个元素作为枢轴，并使用元素的第 4 个字段将它们与枢轴元素的第 4 个字段进行比较。枢轴和键是不同的概念。

具体来说，这

qsort([Head|Tail],Sorted):-
  last(Head,Pivot),
   %% this:         vvvv
  separation(Pivot,[Head|Tail],Lesser,Greater),

一定是这个

  separation(Pivot, Tail, Lesser, Greater),
   %%               ^^^^
  qsort(Lesser,LesserSorted),
  qsort(Greater,GreaterSorted),

因为这里

  append(LesserSorted,[Head|GreaterSorted],Sorted).
   %%                  ^^^^

您假设它在分区之前已从列表中删除（确实应该如此）。

推荐阅读