name = 'quick_sort/2'
slug = 'sort a list using quicksort'

description = '''\
<p><code>quick_sort(L, SL)</code>: the list <code>SL</code> contains the elements of <code>L</code> sorted in non-decreasing order. Use the predicate <code>pivoting/4</code> to implement quicksort.</p>
<pre>
?- quick_sort([2,3,1,5,4], L).
  L = [1,2,3,4,5].
</pre>'''

plan = ['''\
<p>Divide and conquer! And use previous solutions, of course. :)</p>
''', '''\
<p>Take the head away, use it as a pivot, divide the tail into smaller and larger elements. Use recursion on
so obtained sublists since both are shorter (in the worst case scenario shorter by just the head element --
this also explains why quicksort works worst on already sorted lists). In the end simply combine the sublists.</p>
''', '''\
<p>If list <code>L</code> is composed of head <code>P</code> and tail <code>T</code> and if the tail is
split into sublists containing smaller and larger elements, respectively, based on pivot <code>P</code>, and if
we assume the recursion sorts these two sublists into lists <code>SortedSmallerElems</code> and
<code>SortedGreaterElems</code>, and if finally we concatenate these two lists and add in between pivot/head
<code>P</code>, then this results in correctly sorted initial list <code>L</code>.</p>
''']

hint = {
    'eq_instead_of_equ': '''\
<p>The operator <code>==</code> is "stricter" than operator <code>=</code> in the sense that
for the latter it is enough to be able to make the two operands equal (unification).</p>
<p>Of course, you can also solve the exercise without explicit use of either of these two operators, just
remember that unification is implicitly performed with the predicate's arguments (head of clause).</p>
''',

    'eq_instead_of_equ_markup': '''\
<p>Perhaps the operator for unification (=) would be better?</p>
''',

    'base_case': '''\
<p>Did you think of a base case? Which list can you sort without any effort whatsoever?</p>
''',

    'recursive_case': '''\
<p>The base case is ok. However, what about the general recursive case?</p>
''',

    'predicate_always_false': '''\
<p>It seems your predicate is <em>always</em> "false". Did you give it the correct name,
or is it perhaps misspelled?</p>
<p>If the name is correct, check whether something else is misspelled, perhaps there is a full stop instead of
a comma or vice versa, or maybe you typed a variable name in lowercase?</p>
<p>It is, of course, also possible that your conditions are too restrictive, or even impossible to satisfy
(as would be, for example, the condition that <code>X</code> is <em>simultaneously</em> smaller and greater than
<code>Y</code>, or something similarly impossible).</p>
''',

    'timeout': '''\
<p>Is there an infinite recursion at work here? How will it ever stop?</p>
<p>Or perhaps is there a missing, faulty, or simply incompatible (with the general recursive case) base case?</p>
''',

    'arbitrary_base_case': '''\
<p>How can the sorted list be anything whatsoever or a list with an arbitrary element? Did you use
a variable without an assigned value?</p>
''',

    'forgotten_pivot': '''\
<p>Did you, perhaps, forgot to put the pivot element back into the list when returning from recursion?</p>
''',
}