了解序言中quicksort的运行轨迹 [英] understand the running trace of quicksort in prolog
本文介绍了了解序言中quicksort的运行轨迹的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我有以下用于快速排序的序言代码:
I have the following prolog code for quicksort:
gt(X,Y):- X @> Y.
conc([], List, List).
conc([Head|Tail], List1, [Head|List2]):- conc(Tail, List1, List2).
quicksort([], []).
quicksort([X|Tail], Sorted):-
split(X,Tail,Small,Big),
quicksort(Small,SortedSmall),
quicksort(Big, SortedBig),
conc(SortedSmall, [X|SortedBig], Sorted).
split(X,[],[],[]).
split(X,[Y|Tail],[Y|Small],Big):-
gt(X,Y),
!,
split(X,Tail,Small, Big).
split(X,[Y|Tail],Small,[Y|Big]):-
split(X,Tail,Small,Big).
例如,数组为[3,2,4,1,5]. quicksort([3,2,4,1,5],已排序).我需要了解程序的运行轨迹.我几乎做到了,但有一点我没有:(这只是跟踪的一部分):
The array for example is [3,2,4,1,5]. quicksort([3,2,4,1,5], Sorted). I need to understand the running trace of the program. I almost do but there is one point that I don't: (this is just a part of the trace):
Redo: (11) split(3, [5], _G3785, _G3782) ? creep
Call: (12) split(3, [], _G3785, _G3788) ? creep
Exit: (12) split(3, [], [], []) ? creep
Exit: (11) split(3, [5], [], [5]) ? creep
Exit: (10) split(3, [1, 5], [1], [5]) ? creep
Exit: (9) split(3, [4, 1, 5], [1], [4, 5]) ? creep
Exit: (8) split(3, [2, 4, 1, 5], [2, 1], [4, 5]) ? creep
我们为什么要退出:(11)split(3,[5],[],[5])?在第11行蠕变5从何而来? 有人可以帮我!我真的很感激.
Why do we have Exit: (11) split(3, [5], [], [5]) ? creep at the line 11, where does 5 come from? Someone could help me please!! I'd really appreciate that.
推荐答案
在对函数split的规则编号2进行比较之后,应该进行剪切:
There should be a cut after comparing at the rule number 2 of function split:
split(X,[Y|Tail],[Y|Small],Big):-
gt(X,Y),
!,
split(X,Tail,Small, Big).
这篇关于了解序言中quicksort的运行轨迹的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文