§10.1 Sorting Algorithms

Chapter 7 introduced lists in Prolog as the fundamental data structure

• and it emphasised recursive techniques

Details of many of the standard algorithms can be found in the book by Bratko, or in the other standard texts.

• but to emphasise the basic Prolog points we look at two sorting algorithms studied in second year (and in the class 52 344)

For generality, we use the (undefined!) predicate

which is true when the instantiated value of x is greater than that of y.

§10.1.1 Merge Sort

We can obtain a sorted version of some list by:

1. splitting it arbitrarily into two sub-lists

2. recursively sorting the sub-lists

3. merging the sorted sub-lists

Merge Sort: an efficient - O(n lgn) - if unstable algorithm.

Following the normal pattern of first giving a name to those things we can't yet do,

Splitting? Compare with append (in §7.1).

With clauses in optimum procedural order,

Note that, if you allow the middle of these clauses, so that lists can split unevenly, then you'll also need an additional first clause for merge_sort, namely merge_sort([X],[X]). Why?

Ideally, you also need a cut in that clause, to control backtracking behaviour. Again, why?

And merging? Again, two stopping clauses:

§10.1.2 Quick Sort

Worst case ... disappointing! Average case, good

• but likely to be hampered by the over simple selection we use here!

We can obtain a sorted version of some list by:

1. randomly selecting some element from it

2. using that to split the lists into two sub-lists, one of bigger elements and one of smaller elements

3. recursively sorting the sub-lists

4. concentrating [appending] the sorted sub-lists, with the splitter in between

Whence for Quick Sort we obtain the top-level code:

Note way in which splitting element is put back into the final result!

Select? For simplicity, and very crudely, quite ignoring the randomness of the selection,

Of course, this will fail for an empty list, but

1. that concept is senseless
2. in our context, it will never arise

Splitting (around the value of the splitting element)?

Notice how we have made use of clause ordering (and the cut) to excise from the last clause the test gt(Head, Splitter).

Appending is as previously given in Chapter 7, namely:

§10.2 Linear A.D.T's - Queues & Stacks

The desirability of solving problems through the use of Abstract Data Types

• collections of data and of the operations permitted on them

• doesn't alter as we change the programming paradigm

Of course in Prolog as in many other languages (object-oriented ones perhaps excepted) we can cheat and only partly implement a definition, but we don't need to

• although the flexibility of Prolog is such that we do need
  to exercise self-discipline

The key idea is that given at the end of Chapter 7, where we in effect adopted a (self-) reserved atom to link a name with some particular data set.

Let's implement a queue in this way, using, say,

What is a queue? As we know from second year or earlier, a data set which

• can be initialised to be empty
• can be empty or full
• if not full can have a data element added at the rear
• if not empty can have its first element removed or copied

So ...

Of course, the six procedures could have been more sophisticatedly named!

We can re-use this code for a stack

- with appropriate renaming

• say, new_stack for new

• and preferably a "reserved" stack/2

- provided we make one change in add:

• the append line becomes

Both for queues and for stacks, what we are doing is

• using queue/2 (or stack/2) to associate a name uniquely with some data

• hiding from the user the way we have implemented the data structure

The approach is, of course, extensible.

§10.3 Binary Trees

If we are not concerned with data hiding, we may still use the same sort of ideas, but in a simpler way.

For example, we might build a binary tree

• by defining a "reserved" atom, say nil, to represent an empty tree

• and for generality some function tree/3

Our concept of structures (start of Chapter 7), or knowledge of =.. (from §9.2), gives us confidence that what we have, is a four-fold thing linking together

• the concept of a binary tree; and
• its three sub-components (root and two sub-trees).

Trees are fully covered in many of the standard text books (including Bratko)

• but let's look at building, searching and displaying them

• in the context of a binary search tree

Building a tree means adding leaves; in the intended context add_leaf(+,+,-):

Searching something is much like adding to it; so, for our binary search tree, in the intended context in_tree(+,+):

To display a tree

• we can of course use write/1

• but that generates an unpleasant tangle of nodes and brackets
  (remember the parser-like 52 222 example?)

• or we can use an algorithm to show the shape of the tree,
  by rotating it 90° to the left.

This is simply an in-order traverse of the tree, printing each node

• but arranged so that sub-trees are printed "Step" spaces to the right of their roots

• and so that the root of the tree is printed "Inset" spaces from the print margin

Try it in the practical periods!

§10.4 Programming Approach

In a similar way we can handle more complex structures

• for example, graphs have a list of vertices together with a series of edge/2 structures

• hiding the data as may be appropriate

  The Prolog programming approach is constant:

  • select an appropriate, simple representation

  • think through all possible situations
    • normally defined recursively
    • with relevant stopping conditions

  • translate into Prolog style
    • for example, append([], Ans, Ans)
    • using repeated variables to match pattern

    • re-think your code from a procedural viewpoint.

    ---

    © Paul Goldfinch 1997

    Next Chapter

    Return to 52 349 Menu

    ---