How to sort the stack? – Part 8

[showmyiq]

Imagine the following task – you have a stack with some numbers inside followed by a marker.
For example:

1
2
3
4
8
19
29
marker
3
4
… (etc.)

We want to sort the numbers above the marker – descending.
Let’s first write down and plan how to resolve this problem. Let’s define our stack like that:

a
b
c
d
MARK
e
f (etc.)

Let’s say that c<b<d<a. How to sort them out?
We need to find a function sort.
/sort { } def

No matter what we are going to write in the block, we need to define on what condition the function will stop working (I mean such state in which we realize that the stack is sorted). In each step we are going to find the minimum element from the stack (above the marker), push it above the marker (with roll command) and finally restart the sort function with recursion. So the condition should be – “proceed until the marker is on top of the stack”. So we have:

/sort {
counttomark 0 gt { } if
} def

So far – so good. Now let’s create the source for the steps we highlighted above.

/sort {
counttomark 0 gt {
counttomark mark exch
1 add 1 roll
findmin
exch pop
counttomark
1 add 1 pop
sort
} if
} def

Now, findmin will be the function that will find us the minimum element from the stack. We are going to define it later. It will find the minimum element with recursion and again roll on each step, so at the end we are going to receive this:

minimum element
MARKER
value
value
etc..

So, let’s see what our source code will do when we plug in our stack:

a
b
c
d
MARK
e
f (etc.)

countomark 0 gt {} if – In our case counttomark is equal to 4. So we push in the stack 4 and then 0.

0
4
a
b
c
d
MARK
e
f (etc.)

Then the gt function applies. 4 is greater than 0, so the function-block will be triggered.
In the mean time gt function will destroy the top 2 elements 0 and 4, and push the binary value true. But the if statement will check that value and therefore it will be destroyed. So the function-blocked is triggered and we have again the same stack as the one – we started with.

a
b
c
d
MARK
e

counttomark mark exch – again we counttomark and push 4 as value in the stack. Then we push a marker. Then we proceed with function exch – it will exchange the top 2 elements from the stack. So we will have this stack:

4
MARK
a
b
c
d
MARK
e

1 add – we push 1 in the stack. Then the function add will add the top 2 elements from the stack and push in the result. In our case: 4+1 = 5, so 5 will be pushed in back in the stack.

5
MARK
a
b
c
d
MARK
e

1 roll – 1 will be pushed in the stack and the function roll will be launched. Roll will take the top 2 values from the stack (first will say how many elements to roll, the second will define in which direction and how many times to be rolled). In our case we will have 5 1 roll (you should see that the two values 5 and 1 will be destroyed/popped after the roll function). So we will have as a result:

a
b
c
d
MARK
MARK
e

Now we call the findmin function (which we are going to code later) and the result will be:

c
MARK
d
a
b
MARK

We don’t need the second marker so we need to destroy it with the command – exch pop.
So we will have this stack as a result:

c
d
a
b
MARK

counttomark 1 add 1 roll – again we counttomark which is equal to 4. Then we are adding 1 to the count, because when we roll – we want to roll the marker too. So we will have at the end this stack:

d
a
b
MARK
c

Can you see that below the marker we have the minimum element of the stack – c?
If we repeat this process again (by calling the sort function again) we will end up with this stack:

d
a
MARK
b
c

Just to recall you that c<b<d<a

So two more iterations and the stack will be sorted! I told you that PostScript is cryptic language. Now, I am sure you do agree

How to construct the findmin function?

/findmin {
counttomark 1 gt {
2 copy gt { exch } if
counttomark 1 add 1 roll
findmin } if
} def

Again we are using recursion. The idea here is almost the same as the main sort function. I am leaving the decoding to you. Just the third row – 2 copy gt { exch } if – it means that we are going to create the duplicate values of the top two elements on the stack. Then we compare them and we are going to exchange them if the first is greater than the second. We do that until the counttomark is greater than 1 (which means until above the marker to have only 1 element).
Let’s test now the source:

/findmin {
counttomark 1 gt {
2 copy gt { exch } if
counttomark 1 add 1 roll
findmin
} if
} def

/sort {
counttomark 0 gt {
counttomark mark exch
1 add 1 roll
findmin
exch pop
counttomark 1 add 1 roll
sort
} if
} def


mark 88 6 73 9 1 55
stack
sort
stack

When you compile the source at the beginning we have this stack:

55
1
9
73
6
88
--nostringval--
When we call the sort function and print the new stack - we have this:

--nostringval--
88
73
55
9
6
1

In next chapter we are going to take a look in the loop operators and solve the same task with loop function.